LINUX.ORG.RU

Standart ML - Два яйца и небоскрёб

 


0

3

есть такая загадка:

У вас есть доступ в k-этажный небоскрёб и 2 идентичных яйца неизвестной птицы. Никаких данных о прочности скорлупы нет: яйцо может разбиться, упав с первого этажа, а может остаться целым, упав с сотого.

Ваша задача - определить, начиная с какого этажа яйца начинают разбиваться, за минимальное (в худшем случае) число бросков. В ходе эксперимента Вы можете разбить оба яйца, но запасных яиц нет.

у меня есть функция check которая получает аргумент высоту этажа который с него кинули яйцо и возвращает true если яйцо разбилось.

val check = fn : int -> bool

мне надо написать функцию minimalFloor в ML которая получает функцию check и возвращает минимальный этаж которы с него яйцо сломается.

val minimalFloor = fn : (int -> bool) -> int

например:

- minimalFloor check; val it = 37 : int

спасибо

Либо задача как-то не так сформулирована, либо я что-то не понял. Чтобы найти этаж, начиная с которого яйца разбиваются, тебе понадобится log₂k бросков. Двух яиц тебе не хватит.

hippi90 ★★★★ ()

С тебя пиво/сок:

Решение Пусть мы знаем, что минимальное число бросков в худшем случае K.

Очевидно, что для того, чтобы сделать не более K бросков, первый бросок должен быть не выше чем с K-го этажа. В самом деле, если мы сбросим первое яйцо с этажа M>K, и оно разобьётся, у нас не будет иного выхода кроме как методично проверять все этажи подряд начиная с первого и заканчивая M-1. В худшем случае мы проверим M-1 этажей, что в сумме с первым броском даст M>K бросков. Очевидно также, бросать в первый раз ниже чем с K-го этажа нет смысла.

Итак, в первый раз мы бросаем с этажа K. Если яйцо разбилось, то за K-1 попыток мы проверим все K-1 нижних этажей. Если же нет, у нас останется K-1 бросок в запасе на верхние этажи.

Рассуждая аналогично, мы должны будем совершить второй бросок с этажа K+(K-1). Если яйцо разобьётся, нам нужно будет проверить этажи с K+1 по 2*K-2, которых всего K-2, что в сумме с двумя первыми бросками даст искомые K бросков.

Понятно, что если первое яйцо не разобьётся, третий бросок мы будем делать с этажа K+(K-1)+(K-2), четвёртый - с K+(K-1)+(K-2)+(K-3) и так далее. Самый последний бросок мы можем сделать с этажа K*(K+1)/2.

Следовательно, для того чтобы небоскрёб из N этажей можно было проверить за K бросков, должно выполняться условие K*(K+1)/2>=N. В случае N=100 получается K>=14.

Таким образом, нам нужно сделать в худшем случае 14 бросков. До тех пор, пока первое яйцо не разбивается, мы бросаем его с этажей 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100. Если оно разбивается, например, на 69-м этаже, мы начинаем бросать второе яйцо со всех этажей начиная с 61-го, т.е. с первого непроверенного.

I-Love-Microsoft ★★★★★ ()

Задача звучит так, будто есть только два яйца и только два и можно кинуть, а третьего нет. Но в решениях пишут, что надо сделать не менее 14 бросков. Но яйца всего два?

I-Love-Microsoft ★★★★★ ()
Ответ на: комментарий от I-Love-Microsoft

Но яйца всего два?

Упало яйцо, не разбилось. Можно же его снова бросать.

Сначала разреженные проверки, пока не разобьётся первое яйцо. Потом более тщательные проверки вторым.

i-rinat ★★★★★ ()

А это не задача оптимальной остановки, которой еще наш бывший олигарх Березовский занимался и даже книгу написал, когда еще был математиком, а не бизнесменом?

dave ★★★★★ ()