|
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 дня, третья Запутался в задаче про старуху и яйца Логическая задача на измерение высоты разбивания яйца |
| 05.01.2015, 01:46 | |
|
Попробовал посчитать h(100000,200000), но столкнулся с проблемой памяти для консольного приложения. Это haskell влегкую "отъел" 20Гиг, а C++ берет только ~2Гиг. Пришлось модифицировать код, и расчет закончился за 44 сек (60206 знаков).
Кто-нибудь знает, как на VS 2010 для c++ построить 64-битное консольное приложение? Хочу на миллион попыток замахнуться... Добавлено через 46 минут Есть h(500000,1000000) за 871 сек! Отказался от массивов, коэффициенты и сумму считал "на лету". Кстати, "на лету" h(50000,100000) считает за 8.6 сек.Уф-ф-ф, C++ реабилитирован вместе с моей "длинной арифметикой"...
0
|
|
| 05.01.2015, 13:36 | |
|
А я вам все время говорил что дело не в языке а в алгоритмах
Например, судя по временам наших предыдущих алгоритмов, не через биномиальные коэффициенты, а которые вы называете "диагональные, у меня он был оптимальнее реализован, раз на Haskell считал вдвое быстрее.
1
|
|
| 05.01.2015, 14:40 | |
|
Согласен - неэффективный алгоритм может замедлить на порядки, никаким процем не вытянешь
Зато я улучшил свою библиотеку длинных чисел, "прикоснулся" к haskell, почитал про функциональное программирование. Для h(10000,20000) ) диагональный алгоритм у меня просчитывал массив из 10000 элементов 10000 раз. Может, на haskell был другой алгоритм? Последний алгоритм "на лету" просчитывает h(10000,20000) за 0.3сек и мне очень нравится Хотя и его можно улучшить для n близких к m, но зачем?
1
|
|
| 05.01.2015, 14:51 | |
|
Ну на фоне текущей эффективности последнего алгоритма это уже действительно не актуально наверное
Массив у меня был такой же и я точно так же просчитывал, но это уже не принципиально. Видите как удачно получилось с этой задачкой - и для вас ее решение/обсуждение оказалось интересным и полезным: и библиотеку улучшили, и к новым парадигмам прикоснулись. Жаль остальные участники потеряли интерес на этапе диагонального циклического перебора. Побольше бы таких интересных задач и обсуждений на форуме.
0
|
|
| 05.01.2015, 15:33 | ||||||
|
Задачка - это повод, который может всплыть и дать толчок интересному обсуждения, а может и утонуть
![]() Надеюсь, другие участники дочитали обсуждение до этого момента и получили пользу от него (как и те читатели, которые "просто смотрели") ![]() Добавлено через 13 минут Вот код "на лету" без библиотеки длинных чисел.
0
|
||||||
|
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,353
|
|
| 05.01.2015, 15:53 | |
|
Я весь тред не читал, только первые 4 ветки. Постановка задачи такая же или изменилась?
0
|
|
| 05.01.2015, 15:57 | |
|
Постановка такая же - по высоте и числу яиц найти минимальное количество бросков. Только при решении исходной задачи была выделена подзадача, обратная исходной - по числу яиц и бросков найти максимальную высоту, через решение которой предлагалось решение исходной в большинстве кодов.
0
|
|
|
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,353
|
|
| 05.01.2015, 16:06 | |
|
В первоначальном виде без дополнительных ограничений задача однозначного решения не имеет. Для любых алгоритмов найдутся такие этажи (с которого яйцо разбивается)
0
|
|
| 05.01.2015, 16:25 | |
|
castorsky, не понял, вы хотите сказать, что в строго возрастающей последовательности нельзя найти два ее элемента, между которыми заключено любое заданное число?
zer0mail, не успел вчитаться в формулу, как она исчезла
0
|
|
| 05.01.2015, 16:29 | |
|
castorsky, достаточно очевидно, что если яйцо разбивается с этажа k, то оно разбивается со всех этажей выше k
![]() _Ivana, Формула считает один элемент, а нужен весь ряд. Поэтому лучше брать "диагональный алгоритм".
0
|
|
| 05.01.2015, 16:40 | ||
|
0
|
||
|
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,353
|
||
| 05.01.2015, 16:55 | ||
Я говорю что для каждого
0
|
||
| 05.01.2015, 16:58 | ||
|
Какое-то новое видение задачи. Детально в ваших формулах не разбирался, но я стану отрицать. И если
0
|
||
|
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
|
|
| 05.01.2015, 17:00 | |
|
0
|
|
|
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,353
|
|||
| 05.01.2015, 17:06 | |||
Но постановка задачи состоит в поиске минимума, а не оптимального решения.
0
|
|||
| 05.01.2015, 17:09 | |
|
castorsky, чем рисовать "вумные формулы", лучше напишите этажность дома и количество яиц, для которых диагональный алгорим неправильно посчитает максимальное количество попыток m
![]() Вполне возможно, что в некоторых конкретных ситуациях при бросании из окон дома высоты h их потребуется меньше... В общем, нужно среди максимальных mi (зависит от алгоритма) надо найти минимальное m. Что касается размытости, то на любую формулировку может найтись тот, кто ее не поймет.
0
|
|
|
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
|
||
| 05.01.2015, 17:10 | ||
|
9 страниц меня убедили в корректности задачи
0
|
||
| 05.01.2015, 17:13 | |
|
Я тоже считаю что мыслю в верном направлении, но не вижу ничего размытого. Я говорю - я угадаю эту мелодию с семи нот. Оппонент говорит - а я угадаю с шести. И если он будет угадывать все 20-ти секундные мелодии с шести нот, то моя оценка в 7 нот завышена.
Речь не про конкретные ситуации, а про общие. В конкретной ситуации можно и с двух попыток угадать этаж.
0
|
|
| 05.01.2015, 17:17 | |
|
Или даже с одной
0
|
|
| 05.01.2015, 17:17 | |
|
Задача про взлом кода из книги Эрика Фримена про основы 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
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|