Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 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
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
03.01.2015, 21:35
Студворк — интернет-сервис помощи студентам
zer0mail, я не компилирую в экзешник а балуюсь в интерпретаторе, а он конечно любую задачу считает дольше, нередко на несколько порядков. Есть возможность запустить код в Ideone, но там ограничение времени 5 секунд.
В этой задаче меня больше интересует не сравнение скорости кода различных компиляторов, а принципы и алгоритмы вычислений.

Добавлено через 1 час 2 минуты
ЗЫ но если интересно, можем посоревноваться в рамках этих пяти секунд, как предыдущий вариант с 2000/2000. Только мне моего кота надо оптимизировать под скорость еще.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
03.01.2015, 21:45
Для диагонального алгоритма пары (n,n) - быстросчитаемый случай, а пары (n,n/2) посложнее будут. Интересно, для haskell есть IDE типа VS ?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
04.01.2015, 00:27
Есть, и плагины к Эклипсу и другим тоже есть. Но с этими вопросами действительно лучше в другой раздел.

Цитата Сообщение от zer0mail Посмотреть сообщение
Для диагонального алгоритма пары (n,n) - быстросчитаемый случай
Для моего алгоритма они не быстросчитаемы а такие же как и другие. Конечно, если число яиц больше числа попыток, то можно вызвать функцию с уменьшенным до количества попыток числом яиц. А если попыток больше чем яиц, то да, уже интереснее. Но я пока не умею хорошо угадывать повадки Haskell компилятора/оптимизатора, и то что мне кажется будет быстрее на деле медленнее и наоборот. Поэтому с ускорением кота есть сложности

Добавлено через 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
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
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
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
04.01.2015, 00:46
Думаю в нем бортовая длинная арифметика не самая медленная. А еще может у нас просто алгоритмы разные Например, сколько ваш считает h (20000,20030)? Мой 4.25 секунды. Но теперь я уже хочу найти степенной алгоритм этой задачи.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
04.01.2015, 00:51
h(20000,20030) считает 9.4 сек (изменил размер порции длинных чисел с 10^4 на 10^9)
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
04.01.2015, 05:25
Цитата Сообщение от zer0mail Посмотреть сообщение
8шщгш
Простите, в каком смысле?

Добавлено через 5 минут
Волшебная пропорция в 2 раза остается. Но не на порядки различие. Значит алгоритмы эквивалентны.

Добавлено через 54 секунды
Осталось победить h(10000,20000)

Добавлено через 4 часа 26 минут
zer0mail, если продолжать шутить, то могу вам предложить только
h (10000,20001) =
3980276840337966592354307206191202453704 7727804924259387134268656523863597493005 7042....
1882521258021803535775105198695706752348 92321663406309375
As it was mentioned - 6021 digits
- вычисляется за ноль секунд Можете проверить начальные и конечные цифры (все 6021 приводить не стал). Но для общего случая пока не придумал алгоритм.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
04.01.2015, 09:42
Это та же программа, что написана выше? Получается, у haskell либо длинная арифметика эффективней на 3+ порядка, либо он находит более эффективный метод, чем просчет диагоналей 10тыс раз.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
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
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
04.01.2015, 10:32
Я скомпилировал программу из 146 поста, запустил на 10000, 20000.
Минут 10 уже считает, но главное не это - она заняла 6 гиг памяти (никогда столько не видел).
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
04.01.2015, 12:05
Я сейчас в интерпретаторе уже давно жду на тех же данных. Понятно что время растет экспоненциально... Но я не ожидал что так долго будет. Хотя у меня еще есть задел для оптимизации.

Добавлено через 1 минуту
Из 146 поста медленный код очень - у меня с тех пор два варианта лучше появились, прерывайте тот код.

Добавлено через 2 минуты
А тем временем последний кот досчитал в интерпретаторе
h (10000,20000) =
As it was mentioned - 6021 digits
Elapsed time - 1433.9930197s
23 минуты... Причем неоптимизированный. Сколько в экзешнике будет - не знаю. Но оооочень подозреваю, что основное время занимает на таких числах уже длинная арифметика.

Добавлено через 1 час 6 минут
Ну конечно же я был дурак. А теперь, если конечно я фатально не ошибся, то точно в пыль.
h (10000,20000) = ......
As it was mentioned - 6021 digits
Elapsed time - 5.4583122s
В интерпретаторе Haskell - страшная сила. Но и на С должно быть также, если нормальный алгоритм реализовать. Под катом все 6021 разряда - проверьте, если вам не сложно.
Кликните здесь для просмотра всего текста

Не по теме:

h (10000,20000) =
2001366433482715023884911450276390542590 3350750751123605748169849865550809762682 5544060240887634728913629385200674151199 7162973997638275908012979797616792077165 2297735375296594117832821586263730652143 1628390532268921568253635956714821715690 6271104699817448744513084116177391980350 4772169596828182346466527938048332694175 5408019220100082523487664328810992073514 3178997396844516363449353099629408721234 3925472820954849113230351537681719765271 5112026875210155059549533557882786697268 8722200822947561242933151097740364032968 9521380249102528365758219272276626464118 6188910273492775214583379984751493604097 4202660471591626455200974438206989507034 2850905708069753708086873127018621235442 8282591822938730400291413338710114146869 3162837837942092941366355034268600230992 3050766536909853239765548391665501987558 1667804408481419502896434887145068329668 5908123695838548258835665212792610468433 4277878717339806409477826995267531292738 1954660133587330141509403919408487338696 3736599367204762640793336290179202450720 6150528602485001558720727763594591171167 6343518150740877258595633979138377385349 1347495023846846025168730032571298256865 5177093710042261634864113688555995334327 5334379797121066147921372919816978408384 2843872957811231751608195279203905688530 2631362883570588587165364635758246934388 7565389963970284411537981961887838825606 3283363959631139417557938388972424568501 6621673420457235348735795274654550904312 0001912598247378077094975441204754975717 9662192319330822180752313677966790167127 3752703144566513523429374170301037869908 5717432195378138584190363335201398522218 9559112360573236293823478180861446397471 3535817909353774883123435864210092090463 7685465801852636506349494592699633489091 1556132852731444422399213335532462426459 5383085728867663589660201527918374371131 4760297974201544962906034089651463797259 1960662960391121951807962721586649438438 5874431281097716722035508247810870823138 8463327598451394236257667605930275616070 9017807921026713187652446631377993491718 2190399368917699873122641059373823574838 5332365283640540615585572313290260458317 0909034024178196543318662430134911544371 0877890934903580091035487659156254936470 7956370517066636129356541819863737971949 4083449179363302498357671639493783143182 0027034279066398672393340108852985712537 6464599135191538048217766297965717955740 9668214198053708919855019001097802557598 0766349768982621327036753002154382756785 3527514339255365475307243628047121692164 8051401595816561331309551076437424681035 1375258084670240370233797024816687528415 2691449380948137796715766956982957839948 2150519656838155425553940236831919644143 9685338606971761262898850279387919943582 3123161790745907092630050628184470916146 7008179367403676671968734280435361797081 1380709029952015746921244371159536689729 2729600661296708548454012230321697751554 0693271288752218155877677721050085944902 7284267227030303513176211984159374633375 3406517730680490344574266229142529624380 7971485903998807881583110027153661746735 6242688722538178231662044527796085829259 2189476370259412470213371153511901618932 0175425373464816731571141829908127326407 1355926355938682980884213841479104155799 3356313403490290276268882640338596254873 2233031397672592521799606781940865350013 5592242751523050986717964390371036661809 2459099727951065770896637621913691208398 0803144595520661155651902282568486175923 5827006162893044792223134808727939290691 6314773877416088554644383127209850497912 3314138098847614622737227187458980060273 6009962110463469465735392143626210127880 6109023587022582961561552577060415375448 5830454528709590049640031116689160968545 8090565463385045601295458611491572445198 7791926435717617646958663459867020926405 5307118156085916094931446375170146765365 0672423920636234229333157679030494641634 2140054004069747850282089486608605154988 9361993677824124404139413543783022862279 3468187236994165000974246467318423481917 9301553683145193200151953530937449594886 7696752904219713950670132466156214273840 3873048388179187154397877958033839268681 4275952511382651231505370164484066357095 1270305791279320060549391059405733164866 9035689160794456571641254053910816529515 1784124153606099532528852446928208779829 3658509832603557788891282470542534761667 4021372692327970998743636295423280056922 8116584416264319916943444253047778943496 7344529694203749466656701613967785570802 1047009809772359941026356899437955427050 1004176240695216454303347006809208213450 5623549918340750083100981250049334775246 6175622097376658978501539775200711677851 5803063423385653536496118553904542963046 4078892174521395673230721323633507817311 3707076177267018226721482467639092734917 6337468224951789424073762812064392377908 0770010685355222344294895388059999659675 8860035552505289279639596619379127229248 3142258860310513357350110935667477425437 5764508861854473382473584685130723047172 3108025984072418333665119153850979597760 7678735660250407985933421314098687200362 1123485137287826934565977072965064330895 2775046087925997540848765036745965886472 0455519323645147001781184984642471628937 0243160801801731334495931090404615737481 0383450452901256135778322742358103144130 1570100261169974376250963162615502807902 8608071208025044963919755713992145602810 4601567280872084689826096725158733300867 9003960178665726121659798079332660967432 2751261294189861383521721474872996884435 1298241294468192228529818089451741918504 2682856276415581865779344120245035860341 9785392090308330547942812528990206773589 8918457557201790926590537943748489713020 5254692542499687147552038025292358476851 6295505125268607302689650558728653372856 9933542983251329952380588509320459772340 2091363179591946644584806565967308439262 5102638108922872138663859206314440170635 8065854129764330943375709086868304329333 1359334419062695375759651788829930844070 3568155700979802341200096452433548884421 1906945544997224490888886621288005174955 4459120001212089056193501327250770369803 1205763188402031654758928286692204910437 6250850408055598391829275187164087416503 9801792833988719100466901544367841376220 8692533123880180098906972717767024080684 4202574286544138842275822369338428480551 0842119563705282364950535798854614535758 326659490574930113007



Добавлено через 4 минуты
Чуть-чуть не уложился в 5 секунд для Ideone. А h (9000,20000) уже укладываются

Добавлено через 14 минут
Вот теперь уже и можно ответить на ваш вопрос
Цитата Сообщение от zer0mail Посмотреть сообщение
_Ivana, сколько времени на Haskell считаются 50000 яиц и 100000 попыток?
h (50000,100000) =
As it was mentioned - 30103 digits
Elapsed time - 257.7987452s
ЗЫ просто замечательная задача! Столько раз доставила мне радость и удовольствие!
1
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
04.01.2015, 13:04
Код из 146 поста прервал через 2 часа. Для интереса запустил его на более мощном компе - отъел 20Гиг памяти и я его тоже прервал.
Пробую на ideon самые простые примеры типа:
Haskell
1
2
3
4
head [1,2,3]
или 
main = do
    head [1,2.3]
Выскакивает ошибка: No instance for (Num (IO t0)) arising from the literal `1' Чего-то не хватает...
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
04.01.2015, 13:14
У вас ошибки в синтаксисе. Попробуйте мой код с предыдущих ссылок открыть и посмотреть если интересно. А про код из поста 146 я вам уже писал, что сейчас у меня есть гораздо лучше.

Добавлено через 1 минуту
Цифры то h(10000, 20000) совпадают с вашими? Я конечно проверял сравнительно с другими алгоритмами на меньших данных, но на всякий случай уточнить.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
04.01.2015, 13:22
Все 6021 разряд совпали с расчетом на С++, но как haskell сделал это за <6 сек? Можете привести код, попробую в нем разобраться
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
04.01.2015, 15:16
Цитата Сообщение от zer0mail Посмотреть сообщение
но как haskell сделал это за <6 сек?
Если честно, то я ожидал подобных впечатлений Но дело не в языке а больше в алгоритме. Который сейчас у меня до безобразия тривиален и прост (а до этого я сменил их несколько штук разной степени быстродействия), но я все равно продолжаю его дошлифовывать, чтобы он был еще немножко быстрее при определенных входных данных. Вот код: http://ideone.com/bCAPoP , можете поиграться в самом низу с цифрами, только задавайте n меньше m, я в функции заглушку не поставил.

Добавлено через 1 час 30 минут
Доработал еще код, прошлый вариант выполнялся дольше при приближении n к m, текущий примерно одинаковое короткое время. Осталось только визуальную красоту навести.
1
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
04.01.2015, 17:06
Прикольно - h(n,m) равно https://www.cyberforum.ru/cgi-bin/latex.cgi? \sum_{k=1}^{n} C_m^k, а https://www.cyberforum.ru/cgi-bin/latex.cgi?C_m^k последовательно считаются через умножение/деление.
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
04.01.2015, 17:13
Сумма m-той строки в треугольнике Паскаля равна 2m
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
04.01.2015, 18:08
Цитата Сообщение от Dani Посмотреть сообщение
Сумма m-той строки в треугольнике Паскаля равна 2m
Я в курсе И чё?
Перевел C++ на этот алгоритм - h(50000,100000) просчиталось за <12 сек, а h(10000,20000) за <0.8
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
04.01.2015, 18:31
Цитата Сообщение от zer0mail Посмотреть сообщение
Я в курсе И чё?
Когда писал, я думал что это может помочь соптимизровать. Ну да ладно
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
04.01.2015, 19:56
Может кому-то это очевидно, а я всю ночь с Матлабом и рисунками просидел чтобы найти эту закономерность! Но зато теперь полная аналогия с Фибоначчами - есть прожорливая рекурсия, циклическое преобразование и волшебное кунг-фу И идейный момент есть - если мы долго в цикле/рекурсии что-то складываем, то может получится заменить это частично умножением или возведением в степень - что собственно и произошло. И вот теперь действительно задачу можно считать более-менее решенной

Dani, там можно соптимизировать, пойти с другого конца сложив меньше коэффициентов и вычесть их из степени двойки. Но я по-другому нормально соптимизировал - если на нужно сложить больше половины коэффициентов, то я считаю их только до первой половины (где факториалы меньше), а вторая симметричная - делю список на 2 части - хвост который складываю один раз и дублирующуюся часть, которую считаю половину и удваиваю результат.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
04.01.2015, 19:56

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

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

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

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

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


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

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