Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 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
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 22:02
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от gng Посмотреть сообщение
Этот алгоритм (тупым перебором) у меня был приведен. Считает очень долго уже для 30 яиц. Если кэшировать промежуточные результаты, то может считать примерно до 100 тыс. Потом всё равно тормозит.

Добавлено через 1 минуту
прошу прощения, до 30 этажей.
Да, извиняюсь. Единицу прибавить надо, да. Но брать надо минимум по всем x из этих максимумов.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 22:20
Сравнение неоптимизированных и даже некомпилированных котов в интерпретаторе:
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
maxfloor 1 m = m
maxfloor n m = sum.map ((+1).maxfloor (n-1)) $ [0..m-1]
 
maxfloor' n m
    | m <= 0     = 0
    | n <= 0     = 0
    | n == 1     = m
    | m < n      = maxfloor' m m
    | otherwise  = maxfloor' n (m-1) + maxfloor' (n-1) (m-1) + 1
 
task f n k = until ((>=k).f n) (+1) 0
 
testtask s f n k = do
    begT <- getCurrentTime
    putStrLn $ s ++ ": n = " ++ show n ++ ", k = " ++ show k ++ " : res = " ++ show (task f n k)
    endT <- getCurrentTime
    putStrLn $ show $ diffUTCTime endT begT
 
main = do
    testtask "Ivana" maxfloor 10 780000
    testtask "gng" maxfloor' 10 780000
Ivana: n = 10, k = 780000 : res = 21
5.054289s
gng: n = 10, k = 780000 : res = 21
7.797446s
Без кэширования промежуточных значений, просто рекурсии в лоб. Мой вышел чуть покороче. Хотя такое сравнение не показательно конечно.
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 22:23
Цитата Сообщение от _Ivana Посмотреть сообщение
Сравнение неоптимизированных и даже некомпилированных котов в интерпретаторе:
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
maxfloor 1 m = m
maxfloor n m = sum.map ((+1).maxfloor (n-1)) $ [0..m-1]
 
maxfloor' n m
    | m <= 0     = 0
    | n <= 0     = 0
    | n == 1     = m
    | m < n      = maxfloor' m m
    | otherwise  = maxfloor' n (m-1) + maxfloor' (n-1) (m-1) + 1
 
task f n k = until ((>=k).f n) (+1) 0
 
testtask s f n k = do
    begT <- getCurrentTime
    putStrLn $ s ++ ": n = " ++ show n ++ ", k = " ++ show k ++ " : res = " ++ show (task f n k)
    endT <- getCurrentTime
    putStrLn $ show $ diffUTCTime endT begT
 
main = do
    testtask "Ivana" maxfloor 10 780000
    testtask "gng" maxfloor' 10 780000
Без кэширования промежуточных значений, просто рекурсии в лоб. Мой вышел чуть покороче. Хотя такое сравнение не показательно конечно.
Да, наверно это даже логично. ведь у него стек из рекурсий в 2 раза длиннее. Но вообще если динамикой делать, то у него получше.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 22:33
Ivana: n = 10, k = 7800000 : res = 26
44.5535483s
gng: n = 10, k = 7800000 : res = 26
73.2931922s
Соотношение сохраняется, не увеличивается с увеличением k. Я поверхностно понял объяснение второго кода, действительно наши варианты очень похожи. С динамикой у меня цикл все равно будет гоняться, а во втором коде может некоторые из двух слагаемых будут браться из кэша. Хотя надо еще посмотреть сколько раз нам этот кэш поможет, может и ни разу не будет обращение в рекурсию с теми же параметрами.
0
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
01.01.2015, 22:45
Цитата Сообщение от _Ivana Посмотреть сообщение
gng: n = 10, k = 7800000 : res = 26
73.2931922s
Интересно, у меня на нетбуке селерон-700 c одним ядром.
Тот же результат за 1.2s ?
Ваша - 2.5s.
В других условиях, конечно, может всё поменяться.
Вариантов для оптимизации в обоих случаях - море. Но, думаю, что и этого для учебной или олимпиадной задачи достаточно.
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 22:50
Цитата Сообщение от _Ivana Посмотреть сообщение
Соотношение сохраняется, не увеличивается с увеличением k. Я поверхностно понял объяснение второго кода, действительно наши варианты очень похожи. С динамикой у меня цикл все равно будет гоняться, а во втором коде может некоторые из двух слагаемых будут браться из кэша. Хотя надо еще посмотреть сколько раз нам этот кэш поможет, может и ни разу не будет обращение в рекурсию с теми же параметрами.
Там будет ВСЁ браться из кэша, если заполнять правильно.

Кликните здесь для просмотра всего текста
По сути значения же можно так записывать с табличку - в строчке n = кол-ву яиц столбце m = кол-ву попыток будет стоять h(n,m). Вычислять можно начиная со второй стороки(первую заполнить вручную), увеличивая число попыток в каждой строке(то есть записывать слева направо) и потом переходя на след строку по достижению k. Размер таблицы будет такой: в первой строке k элементов, во второй примерно https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{k}, дальше ещё меньше. Каждый элемент вычисляется с помощью соседа слева и элемента слева-снизу от него, которые уже посчитаны (см его алгоритм) Сложность такого алгоритма = https://www.cyberforum.ru/cgi-bin/latex.cgi?O(\sqrt{k}*n), так как табличка будет
не более соответствующих размеров. А на практике видно, что оценку можно сильно ещё уменьшить.


Добавлено через 3 минуты
Цитата Сообщение от gng Посмотреть сообщение
Интересно, у меня на нетбуке селерон-700 c одним ядром.
Тот же результат за 1.2s ?
Ваша - 2.5s.
В других условиях, конечно, может всё поменяться.
Вариантов для оптимизации в обоих случаях - море. Но, думаю, что и этого для учебной или олимпиадной задачи достаточно.
Для олимпиадной 2,5 секунды очень плохо.. И ведь тесты наверняка есть и побольше.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 23:07
Цитата Сообщение от ltkj Посмотреть сообщение
Для олимпиадной 2,5 секунды очень плохо
Ну я же нолик дописал к этажам В скомпилированном виде мой подольше, но оба в районе 1.8 сек на Haskell http://ideone.com/20fHVW На С должно быть не медленнее точно.

ЗЫ а про кэш и ДП весьма интересно.
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 23:20
Цитата Сообщение от _Ivana Посмотреть сообщение
Ну я же нолик дописал к этажам В скомпилированном виде мой подольше, но оба в районе 1.8 сек на Haskell http://ideone.com/20fHVW На С должно быть не медленнее точно.

ЗЫ а про кэш и ДП весьма интересно.
Для олимпиадиадных задач весьма часто бывает ограничение в 1 секунду (для этой я бы сделал такое). И эта секунда является в некотором смысле формальностью - решения обычно работают раза в 2 быстрее. Так что тут есть что улучшать. Могу ещё 1 улучшение по времени предложить. При https://www.cyberforum.ru/cgi-bin/latex.cgi?log_2{k} < n, можно сразу выводить ответ как логарифм (если яиц много, то можно обычным делением пополам выяснить нужный этаж). (В случае обоих ваших алгоритмов и моего примерного 7800000 780000 будет работать очень долго без этой проверки).
0
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
01.01.2015, 23:25
ltkj, у тебя почему-то в личку нельзя написать. Ты есть на топкодер и кодфорсес? скажешь ники?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 23:27
Цитата Сообщение от ltkj Посмотреть сообщение
В случае обоих ваших алгоритмов и моего примерного 7800000 780000 будет работать очень долго без этой проверки
Зря вы так моего кота недооцениваете
Ivana: n = 7800000, k = 780000 : res = 20
0.293998s
Если я конечно правильно вас понял. У меня то волшебный цикл если ни разу не прогонится - то и вхождения в следующие уровни рекурсии не будет, просто выдаст 0 для этой ветки. Во втором коде не знаю, но подозреваю что то же самое. А вот таблицу ДП заполнять - это дело. Правда, каждую строку заполнять до k не знаю надо ли, может можно меньше столбцов. И там что по моему коду просто в цикле пробежать и сложить значения из строки таблицы, что по другому - сложить только 2 соседние - все будет быстро. Но сам принцип понятен, прост и эффективен!
1
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 23:30
Написал свое решение, вроде работает
Цитата Сообщение от gng Посмотреть сообщение
max_floor (n, m-1) + max_floor (n-1, m-1) + 1;
это же почти треугольник Паскаля
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 23:32
Dani, так представьте вашего альтернативного кота
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 23:35
Чуть позже наверно - я в ходе экспериментов его замусорил весь - быстро не раскопать.
0
01.01.2015, 23:35

Не по теме:

SlavaSSU, не надо уводить ценного кадра и переносить интересные разговоры в другие места, кто в лавке то останется тогда? :)

0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 23:41
Цитата Сообщение от SlavaSSU Посмотреть сообщение
ltkj, у тебя почему-то в личку нельзя написать. Ты есть на топкодер и кодфорсес? скажешь ники?
В личку мне написать нельзя, так как я только вчера зарегистрировался тут.
На этих сайтах меня нет - в школьные годы сделал упор на олимпиадную математику, на информатику вполне осознанно забил, так как не хотел в дальнейшем заниматься программированием Но тексты регионального и заключительного этапов всероссийских олимпиад по информатике просматривал - интересно было. В университете уже как-то больше стал программированием заниматься, разочаровавшись в математике.

Добавлено через 3 минуты
Цитата Сообщение от _Ivana Посмотреть сообщение
Зря вы так моего кота недооцениваете Если я конечно правильно вас понял. У меня то волшебный цикл если ни разу не прогонится - то и вхождения в следующие уровни рекурсии не будет, просто выдаст 0 для этой ветки. Во втором коде не знаю, но подозреваю что то же самое. А вот таблицу ДП заполнять - это дело. Правда, каждую строку заполнять до k не знаю надо ли, может можно меньше столбцов. И там что по моему коду просто в цикле пробежать и сложить значения из строки таблицы, что по другому - сложить только 2 соседние - все будет быстро. Но сам принцип понятен, прост и эффективен!
подозрительно быстро, кстати. Может, там и 780 000 число маленькое, но всё равно мне казалось, дольше будет.
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 23:43
Цитата Сообщение от _Ivana Посмотреть сообщение
20
20? Это же дает 23:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int _IvanaSolution(int n, int m)
{
    if (n==1) return m;
    else {
        int s=0;
        for (int i=0; i<m; i++) s += _IvanaSolution(n-1,i)+1;
        return s;
    }
}
 
 
int IvanaSolution(int n, int m)
{
    int i;
    for(i = 1; _IvanaSolution(m, i) < n; ++i);
    return i;
}
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 23:46
Цитата Сообщение от Dani Посмотреть сообщение
20? Это же дает 23:
При 10 яйцах значит обойдемся 21 попыткой, а при 7800000 нужны будут 23? Напоминает ситуацию "за сколько дней починишь карету" Просто вы лишние нолики где-то набрали, но суть не в этом, а что наши 2 кота не мучаются от обилия яиц на входе, оба выдают решения быстро. http://ideone.com/20fHVW
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 23:49
log2(7800000) https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx 22.8 https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx 23
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 23:51
Цитата Сообщение от Dani Посмотреть сообщение
log2(7800000) https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx 22.8 https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx 23
У вас 7 800 000, в примерах 780 000
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 23:51
Ivana: n = 7800000, k = 7800000 : res = 23
2.337251s
gng: n = 7800000, k = 7800000 : res = 23
1.690847s
Я и говорю, с моей легкой руки приписавшей нолик для теста пошла путаница.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
01.01.2015, 23:51

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
100
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №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