|
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 дня, третья Запутался в задаче про старуху и яйца Логическая задача на измерение высоты разбивания яйца |
| 03.01.2015, 21:35 | |
|
zer0mail, я не компилирую в экзешник а балуюсь в интерпретаторе, а он конечно любую задачу считает дольше, нередко на несколько порядков. Есть возможность запустить код в Ideone, но там ограничение времени 5 секунд.
В этой задаче меня больше интересует не сравнение скорости кода различных компиляторов, а принципы и алгоритмы вычислений. Добавлено через 1 час 2 минуты ЗЫ но если интересно, можем посоревноваться в рамках этих пяти секунд, как предыдущий вариант с 2000/2000. Только мне моего кота надо оптимизировать под скорость еще.
0
|
|
| 04.01.2015, 00:27 | ||
|
Есть, и плагины к Эклипсу и другим тоже есть. Но с этими вопросами действительно лучше в другой раздел.
![]() Добавлено через 17 минут UPD пока 2000 яиц и 2800 попыток считает 4.75 секунд. Причем, варианты реализации, выглядящие менее оптимально, считает примерно столько же. Может встроенный оптимизатор так хорошо работает. Добавлено через 14 минут PS вообще эта задачка мне очень напоминает вычисление чисел Фибоначчи. А там, как известно, есть 3 алгоритма: 1) экспоненциальная рекурсия (аналог первых двух рекурсивных кодов в этой теме) 2) циклическое преобразование специального объекта - пары (предыдущее, следующее) - аналог двух последующих нерекурсивных кодов 3) супер кунг-фу с экспоненциальным преобразованием или с другой стороны - возведением матрицы в степень - считает за секунды миллионные по порядку Фибоначчи! Вот если для этих яиц существует такое же кунг-фу, то это будет уже не в клочья, а просто в пыль. Добавлено через 5 минут А у меня очередное предчувствие/ощущение что он существует ![]() Добавлено через 1 час 54 минуты Немножко подрихтовал свой алгоритм в рамках той же концепции, теперь h(2000, 2800) считает 2.5 секунд а h(2000, 2000) - ноль целых ноль сотых секунд Но надо конечно степенные преобразования искать.Добавлено через 2 минуты zer0mail, давайте побалуемся тривиальными фокусами, рассчитаем h(20000, 20000) и сравним результаты и время ![]() Добавлено через 1 минуту 6021 десятичных разряда, если что
0
|
||
| 04.01.2015, 00:42 | |
|
h(20000,20000) считает 0.6 сек. А вот h(2000,2800) 4.6, т.е. C++ уступает haskell... То ли длинные числа у меня тормозные, то ли процессор (блин, проц только одной буквой
отличается: haswell 4590 ).Все же интерсно, за сколько haskell посчитает h(10000,20000)... Почему haskell не тормознее "на несколько порядков", а быстрее C++? Может, он умеет распараллеливать задачу?
0
|
|
| 04.01.2015, 00:46 | |
|
Думаю в нем бортовая длинная арифметика не самая медленная. А еще может у нас просто алгоритмы разные
Например, сколько ваш считает h (20000,20030)? Мой 4.25 секунды. Но теперь я уже хочу найти степенной алгоритм этой задачи.
0
|
|
| 04.01.2015, 05:25 | |||
![]() Добавлено через 5 минут Волшебная пропорция в 2 раза остается. Но не на порядки различие. Значит алгоритмы эквивалентны. Добавлено через 54 секунды Осталось победить h(10000,20000) Добавлено через 4 часа 26 минут zer0mail, если продолжать шутить, то могу вам предложить только
Можете проверить начальные и конечные цифры (все 6021 приводить не стал). Но для общего случая пока не придумал алгоритм.
0
|
|||
| 04.01.2015, 10:08 | |
|
Ну я тут немножко лукавлю и шучу, я же предупреждал
Я всю ночь расписывал таблицы на бумажке и обнаружил некоторые закономерности, в частности h(n,2*n+1) считается тривиально через аналитическую формулу - степень двойки. Но интереснее другое - я написал новый алгоритм, который на сравнимых данных считает существенно быстрее предыдущего, только пока не могу запустить его на h(10000,20000), т.к. он все-таки вылезает за 5 секунд для Ideone а в интерпретаторе...... а пока писал этот пост, у меня в интепретаторе (!) посчиталось h(5000,10000) В скомпилированном экзешнике должно быть еще быстрее.Добавлено через 2 минуты Надеюсь вы сохранили в текст h(10000,20000)? Чтобы сравнить и не ждать полчаса. Добавлено через 7 минут В общем, h(2500,5000) уже безо всяких фокусов на любых данных такого порядка считается в Ideone меньше 4 секунд Кот - полтора десятка символов. Я второй раз удовлетворен. И если я не ошибся, то это то самое "в пыль".
0
|
|
| 04.01.2015, 12:05 | |||||
|
Я сейчас в интерпретаторе уже давно жду на тех же данных. Понятно что время растет экспоненциально... Но я не ожидал что так долго будет. Хотя у меня еще есть задел для оптимизации.
Добавлено через 1 минуту Из 146 поста медленный код очень - у меня с тех пор два варианта лучше появились, прерывайте тот код. Добавлено через 2 минуты А тем временем последний кот досчитал в интерпретаторе
Добавлено через 1 час 6 минут Ну конечно же я был дурак. А теперь, если конечно я фатально не ошибся, то точно в пыль.
Haskell - страшная сила. Но и на С должно быть также, если нормальный алгоритм реализовать. Под катом все 6021 разряда - проверьте, если вам не сложно.
Кликните здесь для просмотра всего текста
Не по теме: h (10000,20000) = Добавлено через 4 минуты Чуть-чуть не уложился в 5 секунд для Ideone. А h (9000,20000) уже укладываются ![]() Добавлено через 14 минут Вот теперь уже и можно ответить на ваш вопрос
1
|
|||||
| 04.01.2015, 13:04 | ||||||
|
Код из 146 поста прервал через 2 часа. Для интереса запустил его на более мощном компе - отъел 20Гиг памяти и я его тоже прервал.
Пробую на ideon самые простые примеры типа:
0
|
||||||
| 04.01.2015, 13:14 | |
|
У вас ошибки в синтаксисе. Попробуйте мой код с предыдущих ссылок открыть и посмотреть если интересно. А про код из поста 146 я вам уже писал, что сейчас у меня есть гораздо лучше.
Добавлено через 1 минуту Цифры то h(10000, 20000) совпадают с вашими? Я конечно проверял сравнительно с другими алгоритмами на меньших данных, но на всякий случай уточнить.
0
|
|
| 04.01.2015, 15:16 | ||
Но дело не в языке а больше в алгоритме. Который сейчас у меня до безобразия тривиален и прост (а до этого я сменил их несколько штук разной степени быстродействия), но я все равно продолжаю его дошлифовывать, чтобы он был еще немножко быстрее при определенных входных данных. Вот код: http://ideone.com/bCAPoP , можете поиграться в самом низу с цифрами, только задавайте n меньше m, я в функции заглушку не поставил.Добавлено через 1 час 30 минут Доработал еще код, прошлый вариант выполнялся дольше при приближении n к m, текущий примерно одинаковое короткое время. Осталось только визуальную красоту навести.
1
|
||
| 04.01.2015, 19:56 | |
|
Может кому-то это очевидно, а я всю ночь с Матлабом и рисунками просидел чтобы найти эту закономерность! Но зато теперь полная аналогия с Фибоначчами - есть прожорливая рекурсия, циклическое преобразование и волшебное кунг-фу
И идейный момент есть - если мы долго в цикле/рекурсии что-то складываем, то может получится заменить это частично умножением или возведением в степень - что собственно и произошло. И вот теперь действительно задачу можно считать более-менее решенной ![]() Dani, там можно соптимизировать, пойти с другого конца сложив меньше коэффициентов и вычесть их из степени двойки. Но я по-другому нормально соптимизировал - если на нужно сложить больше половины коэффициентов, то я считаю их только до первой половины (где факториалы меньше), а вторая симметричная - делю список на 2 части - хвост который складываю один раз и дублирующуюся часть, которую считаю половину и удваиваю результат.
1
|
|
| 04.01.2015, 19:56 | |
|
Задача про взлом кода из книги Эрика Фримена про основы 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
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|