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

спасибо



Последнее исправление: verilog (всего исправлений: 1)

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

hippi90 ★★★★★
()

В job.
Задачки с тупых собеседований\контрольных бесплатно не решаются.

Deleted
()
Ответ на: комментарий от hippi90

Что самое смешное - решение есть для двух яиц.

Deleted
()

Сводится к решению уравнения:

x+(x-1)+(x-2)+....+1=k, где к - число этажей

Bobby_
()

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

Решение Пусть мы знаем, что минимальное число бросков в худшем случае 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 ★★★★★
()
Ответ на: комментарий от i-rinat

Точно, это ж математическая задача, не учитывающая «износ» скорлупы и микротрещины :)

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

Интересно, где это SML преподают

anonymous
()

Standart

Чё за слово новое?

anonymous
()

Я извиняюсь, но может кто-нибудь заодно решение задачи с двумя стульями на SML посоветует?

hateyoufeel ★★★★★
()

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

dave ★★★★★
()
Ответ на: комментарий от dave

Это олимпиадная задача по информатике для 9-го класса.

aedeph_ ★★
()

А если яйца бросать с небоскреба в снег, например???

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.