Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.80/104: Рейтинг темы: голосов - 104, средняя оценка - 4.80
17 / 17 / 6
Регистрация: 10.12.2013
Сообщений: 740

Задача про яйца

31.12.2014, 21:41. Показов 24927. Ответов 228
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Привет всем. Дана такая задача.

У вас есть n яиц и вы живете в k-этажном доме. Какое наименьшее число попыток потребуется для того, чтоб узнать наивысший этаж, упав с которого, яйцо не разобьется?

Вообще не понимаю, как ее решить? Что от меня требуется? Да яйцо с 10-15 см разобьется.
3
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
31.12.2014, 21:41
Ответы с готовыми решениями:

Написать программу, которая решает следующую задачу: было куплено 3 курицы за 46 гривен. Первая несет 3 яйца за 4 дня, вторая 2 яйца за 3 дня, третья
Написать программу, которая решает следующую задачу: было куплено 3 курицы за 46 гривен. Первая несет 3 яйца за 4 дня, вторая 2 яйца за 3...

Запутался в задаче про старуху и яйца
Старуха принесла на рынок кошелку яиц. Не успела разложить их, как богатый купец ненароком зацепил кошелку, и все яйца разбились. Прибежал...

Логическая задача на измерение высоты разбивания яйца
Добрый день. Хочу сразу оговориться - математикой занимался давно, многое уже позабыл. Мне интересно решение данной задачки: ...

228
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 23:52
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от _Ivana Посмотреть сообщение
7800000, k = 780000 : res = 20
7800000 = 7 800 000
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 23:54
Цитата Сообщение от Dani Посмотреть сообщение
7800000 = 7 800 000
Там n и k разные
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 23:54
Dani, это яйца а k - этажи. Сохраняя обозначения стартового поста.
0
01.01.2015, 23:55

Не по теме:

Не мой день сегодня явно :)

0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 23:58
Dani, лучше кота выставите, можно нечищенного Он же у вас без последующего цикла сразу попытки считает, минимизируя варианты внутри рекурсии?
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 23:59
Господа, какие у нас будут ограничения к задаче?
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 00:02
Цитата Сообщение от Dani Посмотреть сообщение
Господа, какие у нас будут ограничения к задаче?
Ну я б сделал https://www.cyberforum.ru/cgi-bin/latex.cgi?1 \le k,n \le 2^{31}-1, время 1 секунда, память 64 мб)
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 00:03
Вы опять в типы не влезаете?
Отрицательные яйца, этажи и попытки предлагаю не рассматривать, а там без ограничений. Правда, при больших этажах или рекурсия долгая или ДП таблица огромная...
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
02.01.2015, 00:05
Тогда надо думать, как тут быстро все сделать...

Добавлено через 1 минуту
Я не математик, но вы ничего не думали по поводу того, что max_floor (n, m-1) + max_floor (n-1, m-1) + 1; похоже на биномиальные коэффициенты.
0
117 / 121 / 42
Регистрация: 25.08.2012
Сообщений: 1,294
02.01.2015, 00:08
Нашел в интернете подобную задачу, только про сто этажей и два яйца, которые могут быть либо очень крепкими, либо хрупкими ( при этом оба одинаковые). Цель та же. Там вроде как решение есть. Выкладывать (вы все равно про реализации алгоритмов пишите)?
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 00:09
Цитата Сообщение от tnk500 Посмотреть сообщение
Нашел в интернете подобную задачу, только про сто этажей и два яйца, которые могут быть либо очень крепкими, либо хрупкими ( при этом оба одинаковые). Цель та же. Там вроде как решение есть. Выкладывать (вы все равно про реализации алгоритмов пишите)?
В случае 2 яиц ответ руками считается. Ну если хочется, я не против
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 00:10
Что тут думать - кэшировать надо А на треугольник Паскаля похоже много всего, но далеко не все из этого выражается в простой алгебраической форме. Например, задача с олимпиады моего сына - есть рекурсивное решение, а есть и явная формула от аргумента. Но додуматься до нее нетривиально, мне во всяком случае. могу найти ссылку если интересно - тоже кто-то говорил "треугольник Паскаля"
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 00:10
Цитата Сообщение от _Ivana Посмотреть сообщение
Что тут думать - кэшировать надо А на треугольник Паскаля похоже много всего, но далеко не все из этого выражается в простой алгебраической форме. Например, задача с олимпиады моего сына - есть рекурсивное решение, а есть и явная формула от аргумента. Но додуматься до нее нетривиально, мне во всяком случае. могу найти ссылку если интересно - тоже кто-то говорил "треугольник Паскаля"
Было б интересно посмотреть
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 00:13
Цитата Сообщение от tnk500 Посмотреть сообщение
про сто этажей и два яйца
еще на первой странице этой темы руками расписано.

Добавлено через 2 минуты
Цитата Сообщение от ltkj Посмотреть сообщение
Было б интересно посмотреть
раз Сколько квазисерпинских треугольников?
два Сколько квазисерпинских треугольников?

ЗЫ но я так и не понял, кто-то сам вывел страшную прямую формулу или подсмотрел в OEIS
0
117 / 121 / 42
Регистрация: 25.08.2012
Сообщений: 1,294
02.01.2015, 00:16
_Ivana, да, видел. Но долго не мог понять, зачем рассчитывать количество попыток, если как указано в первом сообщении, яйцо разбивается с 10-15 см. Смысла, в общем, не мог постичь). Поэтому решил загуглить

Если интересно, вот ссылка (задача в конце). И да, есть вероятность баянизма
Ладно, там по сути, повторяются.
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 00:17
Цитата Сообщение от tnk500 Посмотреть сообщение
_Ivana, да, видел. Но долго не мог понять, зачем рассчитывать количество попыток, если как указано в первом сообщении, яйцо разбивается с 10-15 см. Смысла, в общем, не мог постичь). Поэтому решил загуглить

Если интересно, вот ссылка (задача в конце). И да, есть вероятность баянизма
Это был комментарий от автора про 10-15 см - он начал в задаче по программированию искать жизненный смысл, что не всегда полезно делать.
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
02.01.2015, 00:18
_Ivana, до меня почти дошло ваше решение. Можете еще раз описать его пожалуйста? Мне кажется его можно соптимизировать.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 00:23
Dani, скорее всего это и сделал уже gng, во всяком случае очень похоже на то.
Давайте еще раз - максимальную высоту я считаю как сумму последовательно уменьшающихся высот: сколько этажей проверим n-1 яйцом и m-1 бросками, то же для n-1 и m-2 броска и т.д. до n-1 и 0 бросков. К каждому слагаемому прибавляю 1, как проверку этажа первым яйцом.
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
02.01.2015, 00:25
_Ivana, почти все понял за исключением: почему сумма? Вы же сами написали "максимальную". Я похоже не понимаю чего-то очевидного
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 00:42
Очередной раз предлагаю вам пробежаться 14-ю попытками из двух яиц до 105 этажа на бумажке - как я сделал еще в прошлом году! Бросаете первое с 14-го, потом с 27-го и т.д. Поймете почему сумма.

Добавлено через 4 минуты
ЗЫ ltkj, пока вы (надеюсь) читаете мои ссылки, хочу сказать, что если вывести такую же волшебно-аналитическую формулу для этажей в этой задаче, то требования ко времени выполнения и памяти можно жестко сузить

Добавлено через 10 минут
Вести с полей - для двух яиц oeis опознала очевидные
Triangular numbers: a(n) = C(n+1,2) = n(n+1)/2
, а уже для трех
Извините, последовательность отсутствует в базе данных
Your sequence appears to be: + 1/6 x3 + 5/6 x
.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
02.01.2015, 00:42

Задача про взлом кода из книги Эрика Фримена про основы javascript в конце 5 главы.
читаю книгу Эрика Фримена про основы javascript.В конце 5 главы есть задачка про взлом кода.Никак не могу понять как ее решить.НЕ понимаю...

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он уплатил по 31 талеру, а за каждого быка по...

Где хранить яйца?
Вот так не усмотрели мы, но купили сестре холодильник без отсека для яиц, и любопытно, как быть и что теперь делать? Куда их складывать и...

Сколько стоят яйца?
Две соседки по коммунальной квартире на общей кухне решили устроить небольшой ужин из яичницы. Одна принесла 3 яйца, другая 5. На вкусный...

Четыре яйца поэтапно бросают до 5000-го этажа
Здравствуйте! Помогите, пожалуйста, вывести простую и понятную математическую формулу — зависимость числа бросков от количества яиц и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
120
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №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
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru