|
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740
|
|
Задача про яйца31.12.2014, 21:41. Показов 24927. Ответов 228
Метки нет (Все метки)
Привет всем. Дана такая задача.
У вас есть n яиц и вы живете в k-этажном доме. Какое наименьшее число попыток потребуется для того, чтоб узнать наивысший этаж, упав с которого, яйцо не разобьется? Вообще не понимаю, как ее решить? Что от меня требуется? Да яйцо с 10-15 см разобьется.
3
|
|
| 31.12.2014, 21:41 | |
|
Ответы с готовыми решениями:
228
Написать программу, которая решает следующую задачу: было куплено 3 курицы за 46 гривен. Первая несет 3 яйца за 4 дня, вторая 2 яйца за 3 дня, третья Запутался в задаче про старуху и яйца Логическая задача на измерение высоты разбивания яйца |
| 01.01.2015, 19:51 | |
|
_Ivana, если честно, у меня до сих пор смутное понимание задачи, но в вашем коде h(n, m) - ответ для n яиц и m этажей, как я понял. А дальше вы перебираете этаж и суммируете ответ. И тут вопрос: почему сумма? Мы же в конечном итоге какой-то 1 этаж должны выбрать, и для наихудшего случая это должно быть max(h(n-1, i)), нет?
0
|
|
| 01.01.2015, 19:55 | |
|
Dani, у меня постепенно растет и понимание задачи и понимание моего кота в ней. Функция h(n,m) - это максимальная высота дома, который мы можем гарантированно проверить имея n яиц и m бросков. А в основном коде я гоняю ее в цикле с нуля бросков, пока ее результат меньше необходимой высоты дома.
1
|
|
| 01.01.2015, 20:14 | |
|
Давайте по шагам. Если у нас есть допустим 10 яиц. И ноль попыток. Какую высоту мы сможем проверить? Правильно, ноль. Если те же 10 яиц и одна попытка? Правильно, 10. Если 10 яиц и 2 попытки? Тут на приходит на помощь функция h(10,2), она вернет какой-то результат. И если у нас задача найти количество попыток для дома в 100500 этажей, я вызываю свою функцию этажей от постоянного заданного количества яиц 10 с увеличивающимися количеством попыток - пока результат функции не станет больше или равен желаемым 100500. Но это все тривиальщина, главная соль - в самой функции h(n,m). А она получилась на редкость элегантна, при любых условиях, даже при огромном количестве яиц и малом количестве попыток.
Добавлено через 7 минут Не по теме: ЗЫ все спасибы и впечатления, незаслуженно адресованные моему предыдущему ошибочному коту, прошу записывать на счет последнего правильного кота :)
1
|
|
| 01.01.2015, 20:16 | ||
Но думаю вы поняли.Добавлено через 1 минуту Не успел написал до вашего комментария. Просто проверьте h(10,1). Я впопыхах вам сказал глупость, но функцию правильно написал.
1
|
||
|
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
|
|||||||||||
| 01.01.2015, 20:23 | |||||||||||
|
У меня вроде сошлось в условием 10, 780000 -> 21.
Добавлено через 5 минут PS. т.е не сошлось с кодом _Ivana
1
|
|||||||||||
| 01.01.2015, 20:30 | ||
|
gng, все сошлось. Просто замените функцию h(n,m) на мою последнюю правильную.
Добавлено через 4 минуты
2
|
||
| 01.01.2015, 20:41 | |
|
Возьмите 2 яйца и 3 попытки. Первый бросок с 3 этажа, т.к. за две оставшиеся попытки мы сбросим с 1 и 2 этажей второе яйцо. То есть, за один бросок первого яйца мы проходим 3 этажа. Второй бросок - я пятого. Т.к. за один оставшийся мы пройдем 4 этаж. И третий - с 6-го, т.к. за 0 оставшихся мы пройдем 0 этажей. Итого за каждый очередной бросок первого яйца мы можем пройти количество этажей, проходимых за меньшее на 1 количество бросков меньшего на 1 количества яиц плюс один этаж - с которого мы бросили первое яйцо.
1
|
|
| 01.01.2015, 20:47 | |
|
Dani, с каждым очередным броском первого яйца количество оставшихся бросков уменьшается именно на 1 и никак иначе. И именно один дополнительный этаж мы и проверяем каждым броском первого яйца. Ну распишите на бумажке, я вас третий раз прошу уже
Мне еще надо волшебный код gng понять, похоже, там тоже красота!
1
|
|
|
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
|
|
| 01.01.2015, 20:50 | |
|
Dani, я так понимаю, вас ввёл в ступор этот цикл. Сумма там идёт по i от 0 до m-1, а в математических рассуждениях цикл будет наоборот - от m-1 до 0. Результат же будет таким же
0
|
|
| 01.01.2015, 20:55 | |
|
Правильно, яйца уменьшаем на 1 (считая каждый раз что первое разбилось на очередном броске), а попытки суммируем по убывающему количеству оставшихся.
Подробно: h(2,3) = h(1,2) (=2 - первый и второй этажи) + 1 (третий этаж) : если первое яйцо разбилось в первой попытке + h(1,1) (=1 - четвертый этаж) + 1 (пятый этаж) : если первое яйцо разбилось во второй попытке + h(1,0) (=0 - никакой этаж) + 1 (шестой этаж) : и неважно уже разбилось первое яйцо или нет Добавлено через 42 секунды ltkj, правильно, я просто поменял порядок суммирования для простоты кода, воспользовался коммутативностью моноида sum
0
|
|
|
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
|
||
| 01.01.2015, 20:56 | ||
|
0
|
||
| 01.01.2015, 21:00 | |
|
Ладно, забуду все, попробую свое решение написать.
0
|
|
| 01.01.2015, 21:00 | |
|
Задача про взлом кода из книги Эрика Фримена про основы javascript в конце 5 главы. Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника Где хранить яйца? Сколько стоят яйца? Четыре яйца поэтапно бросают до 5000-го этажа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|