|
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
|
|
| 01.01.2015, 21:05 | |
|
А вообще идея у gng верная, только m надо от 1 брать. По производительности пока не знаю, она зависит от порядка ответа, а его ещё прикинуть надо. но явно лучше динамикой переделать.
0
|
|
|
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
|
|
| 01.01.2015, 21:20 | |
|
Ваши алгоритмы ничем почти не отличаются, только он чуть лучше считает в случае динамической записи (то есть если не пересчитывать заново предыдущие результаты).
Это видно из соотношения То есть вы считаете длинную сумму, а он вместо этого складывает 3 числа. В случае же рекурсии вроде вообще всё одинаково.
0
|
|
| 01.01.2015, 21:23 | |
|
Не по теме: А вот и те самые более способные участники о которых я говорил на предыдущей странице! :) ltkj, спасибо, постараюсь осознать эквивалентность. Хотя еще действительно хочу переписать через неподвижную точку, причем не просто тупо применив правило, а с осознанием сути происходящего
0
|
|
| 01.01.2015, 21:24 | ||||||
|
_Ivana, а как правильно запускать то вашу функцию?
![]() так?
0
|
||||||
|
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
|
|
| 01.01.2015, 21:31 | |
|
Могу даже без этих сумм попробовать пояснить, что у него за формула. Первым броском мы должны выбрать этаж, равный h(n-1,m-1) + 1. Вы вроде это тоже используете, но если надо пояснить, почему он оптимальный, могу написать ниже. Далее, если яйцо не разбилось, остается на одну меньше попыток и столько же яиц. Максимальный этаж для них равен h(n,m-1) - уже считали. Из этого и получается ответ. Вы же просто заново считали h(n,m-1), прикидывая, какой этаж выбрать следующим и т.д.
0
|
|
|
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
|
|
| 01.01.2015, 21:33 | |
|
0
|
|
| 01.01.2015, 21:39 | |
|
ltkj, почему-то я не могу ставить вам плюсы (нет кнопки под вашими постами), но как только она появится - с меня пара как минимум
![]() Dani, как раз известно что - мы нашли предел прочности
0
|
|
|
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
|
||
| 01.01.2015, 21:39 | ||
|
0
|
||
| 01.01.2015, 21:47 | |||||||
|
ЗЫ вот как мой кот выглядит в другой парадигме
0
|
|||||||
|
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
|
||
| 01.01.2015, 21:47 | ||
|
0
|
||
| 01.01.2015, 21:53 | |
|
_Ivana, ltkj, я подумал вот что: пусть F(i, j) -- наименьшее кол-во попыток если есть i этажей и j яиц. Вот такие у меня варианты:
i == 0: F(i, j) = 0 иначе: F(i, j) = [кидаем с этажа номер x, 1 <= x <= i] max( [яйцо разбивается]F(x - 1, j - 1) [яйцо не разбивается]F(i - x, j) ); Правильно мыслю?
0
|
|
|
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
|
|||||||
| 01.01.2015, 21:55 | |||||||
0
|
|||||||
|
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
|
||
| 01.01.2015, 21:57 | ||
|
0
|
||
| 01.01.2015, 22:00 | |||
![]()
0
|
|||
|
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
|
|||
| 01.01.2015, 22:02 | |||
|
Добавлено через 1 минуту
0
|
|||
| 01.01.2015, 22:02 | |
|
Задача про взлом кода из книги Эрика Фримена про основы 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
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|