|
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 дня, третья Запутался в задаче про старуху и яйца Логическая задача на измерение высоты разбивания яйца |
|
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
|
||
| 02.01.2015, 02:18 | ||
ну можно просто long long воспользоваться) а можно и в условии поменять 2^31-1 на 10^9, чтоб проще было но всё равно надо будет проверить h[n-1][m] перед сложением)
0
|
||
|
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
|
|
| 02.01.2015, 02:23 | |
|
0
|
|
| 02.01.2015, 02:26 | |
|
Хорошо что я написал аккуратно и в предположительном тоне... Скажете идею вашего алгоритма?
Добавлено через 1 минуту ltkj, может это не в С++. У меня например в Haskell бесплатная длинная арифметика на борту.
0
|
|
| 02.01.2015, 06:16 | |||||||||||
|
zer0mail, похоже вы порвали задачу в клочья. Моя рекурсия скромно жует жвачку в сторонке...
Добавлено через 41 минуту ltkj, спасибо на словах (кнопки все нет) - понял и равенство формул, которое вы писали на прошлой странице (просто выделил пару минут на вдумчивое прочтение а не по верхам в запарке темы), и сделал через неподвижную точку, начиная с нуля. Конечно не 600 знаков за 8 секунд, но концептуально хочу все осознать. Добавлено через 5 минут Сейчас попробую придумать через не экспоненциальную хвостовую рекурсию если получится. Добавлено через 1 час 16 минут Пожевал я тут жвачку в сторонке, подумал, и решил тоже порвать в клочья эту задачу ![]()
Результат: Не по теме: h (2000,2000) = ![]() ЗЫ я немножко удовлетворен ![]() Добавлено через 1 час 33 минуты Особой оптимизации по скорости не получилось, новая функция выполняется на тех же данных в полтора раза дольше, зато зажал ее в одну строчку Вот теперь можно и поспать...
2
|
|||||||||||
| 02.01.2015, 12:28 | ||
|
zer0mail, если не скромничать, то я понял и написал штуку поинтереснее чем "рекурсия в лоб". И вообще, я немножко поглубже понял эту задачу. Если будет интерес у участников форума - могу выпендриться и рассказать
А пока реализую все-таки функцию поиска минимального количества бросков - есть некоторые идеи.Добавлено через 1 минуту Но если честно это конечно заслуга алгоритма, на С он должен еще быстрее выполняться.Добавлено через 2 часа 17 минут UPD цикл поиска m при k = 2^31-1 и n от 1 до 32 и бонусом n = 2^100 - все вместе занимает 0.02 секунды и требует очень немного памяти - http://ideone.com/13SeV3 И можно еще думаю убыстрить в 6 раз минимум (не стал оптимизировать уже), а если длинную арифметику заменить на ограниченные инты - то еще неизвестно во сколько раз быстрее будет.
0
|
||
|
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
|
||||||
| 02.01.2015, 14:37 | ||||||
|
_Ivana, если вопрос в производительности, то без рекурсии считается практически мгновенно (в диапазоне int)
2
|
||||||
| 02.01.2015, 17:29 | |
|
gng, именно. Но я не сразу додумался до этого нерекурсивного алгоритма, решающего задачу мгновенно и без особых запросов памяти. А вы оказывается знали, а писали со мной медленную прожорливую экспоненциальную рекурсию
Чтож, теперь уже можно сказать что задача решена на достаточном уровне для учебной или олимпиадной.
0
|
|
|
|
|
| 02.01.2015, 19:13 | |
|
0
|
|
|
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
|
||
| 02.01.2015, 19:24 | ||
|
0
|
||
|
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
|
|||||||
| 02.01.2015, 19:43 | |||||||
|
Извиняюсь перед всеми. Мной была допущена ошибка, влияющая на результат.
Ниже испавленный код.
Нерукурсивную я написал по тому же алгоритму после того, как были озвучены требования к производительности.
0
|
|||||||
|
|
|
| 02.01.2015, 19:59 | |
|
gng, можешь добавить коментарий к строкам с 13 по 16 ?
0
|
|
| 02.01.2015, 21:07 | ||
|
0
|
||
|
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
|
||
| 02.01.2015, 22:53 | ||
|
H[n,m]= H[n-1,m-1] + H[n, m-1] +1 Идея проста и наглядна (уважаемые авторы её уже пояснили выше немного другими словами): Имея n яиц и m попыток выбираем для первой попытки такой этаж, чтобы внизу осталось максимальное количество этажей, которое можно разрешить с одним разбитым яйцом H[n-1,m-1], а вверху - с полным количеством яиц H[n,m-1] плюс сам выбранный этаж. При решении без рекурсии вместо двумерного массива используется диагональ ; (1,m-n+1)...(n-2,m-2),(n-1,m-1),(n,m). Значение первого элемента равно m, остальные считаются последовательно. Добавлено через 40 минут
1
|
||
|
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
|
|||||||||||||
| 03.01.2015, 13:02 | |||||||||||||
PS. Диагональным массив был назван по отношению к таблице (n,m). Его, конечно, можно нарисовать и подобно биному.
1
|
|||||||||||||
|
|
|||
| 03.01.2015, 13:07 | |||
|
0
|
|||
| 03.01.2015, 20:24 | |
|
_Ivana, сколько времени на Haskell считаются 50000 яиц и 100000 попыток? На C++ диагональный алгоритм считает <6 сек...
Добавлено через 21 минуту Упс - не там точку останова поставил. Сейчас пересчитаю...Добавлено через 1 час 59 минут Пришлось уменьшить аппетиты 20000 попыток и 10000 яиц считал ~33 мин. Число этажей содержит 6021 знак.
0
|
|
| 03.01.2015, 20:24 | |
|
Задача про взлом кода из книги Эрика Фримена про основы 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
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|