Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 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
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
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
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
05.01.2015, 13:36
А я вам все время говорил что дело не в языке а в алгоритмах Например, судя по временам наших предыдущих алгоритмов, не через биномиальные коэффициенты, а которые вы называете "диагональные, у меня он был оптимальнее реализован, раз на Haskell считал вдвое быстрее.
1
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
05.01.2015, 14:40
Согласен - неэффективный алгоритм может замедлить на порядки, никаким процем не вытянешь Зато я улучшил свою библиотеку длинных чисел, "прикоснулся" к haskell, почитал про функциональное программирование.
Для h(10000,20000) ) диагональный алгоритм у меня просчитывал массив из 10000 элементов 10000 раз. Может, на haskell был другой алгоритм?
Последний алгоритм "на лету" просчитывает h(10000,20000) за 0.3сек и мне очень нравится Хотя и его можно улучшить для n близких к m, но зачем?
1
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
05.01.2015, 14:51
Ну на фоне текущей эффективности последнего алгоритма это уже действительно не актуально наверное Массив у меня был такой же и я точно так же просчитывал, но это уже не принципиально. Видите как удачно получилось с этой задачкой - и для вас ее решение/обсуждение оказалось интересным и полезным: и библиотеку улучшили, и к новым парадигмам прикоснулись. Жаль остальные участники потеряли интерес на этапе диагонального циклического перебора. Побольше бы таких интересных задач и обсуждений на форуме.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
05.01.2015, 15:33
Задачка - это повод, который может всплыть и дать толчок интересному обсуждения, а может и утонуть

Надеюсь, другие участники дочитали обсуждение до этого момента и получили пользу от него (как и те читатели, которые "просто смотрели")

Добавлено через 13 минут
Вот код "на лету" без библиотеки длинных чисел.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{   int i,k,n;
    k=10000; // яиц
    n=20000; // попыток
    // коэффициент C(n,k)=C(n,k-1)*l/u
    int u=0;    // растет, на него делим
    int l=n;    // убывает, на него умножаем
    int j=k;
    BigI m(40000,1);    // рассчитываемый биномиальный коэффициент, 40000 - столько слов выделяем под "длинное число"
    BigI s(40000,1);    // сумма коэффициентов с C(n,1) по текущий
    m+=1;               // С(n,0)=1;
    // ВОТ ОН, РАСЧЕТ БИНОМИАЛЬНЫХ КОЭФФИЦИЕНТОВ через умножение/деление
    for (i=1;i<=j;++i) 
    {  // для класса длинных чисел переопределены операторы
        m*=l--;    // умножения на целое
        m/=++u;    // деления на целое
        s+=m;      // прибавления другого длинного
    }
    s.print();
    return 0;
}
Добавлено через 6 минут
0
 Аватар для castorsky
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,353
05.01.2015, 15:53
Я весь тред не читал, только первые 4 ветки. Постановка задачи такая же или изменилась?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
05.01.2015, 15:57
Постановка такая же - по высоте и числу яиц найти минимальное количество бросков. Только при решении исходной задачи была выделена подзадача, обратная исходной - по числу яиц и бросков найти максимальную высоту, через решение которой предлагалось решение исходной в большинстве кодов.
0
 Аватар для castorsky
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,353
05.01.2015, 16:06
В первоначальном виде без дополнительных ограничений задача однозначного решения не имеет. Для любых алгоритмов найдутся такие этажи (с которого яйцо разбивается) https://www.cyberforum.ru/cgi-bin/latex.cgi?m \in \{1, 2, ..., k\} для которых данный алгоритм не даст минимального колличества попыток x. И наоборот, всегда найдутся такие https://www.cyberforum.ru/cgi-bin/latex.cgi?m \in \{1, 2, ..., k\} для которых один и только один алгоритм даст минимальное решение.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
05.01.2015, 16:19
Действительно, мы уже отошли от исходной задачи и теперь ее, возможно, не стоит считать через обратную
Для первоначальной задачи вполне достаточно "диагонального алгоритма".
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
05.01.2015, 16:25
castorsky, не понял, вы хотите сказать, что в строго возрастающей последовательности нельзя найти два ее элемента, между которыми заключено любое заданное число?

zer0mail, не успел вчитаться в формулу, как она исчезла
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
05.01.2015, 16:29
castorsky, достаточно очевидно, что если яйцо разбивается с этажа k, то оно разбивается со всех этажей выше k

_Ivana, Формула считает один элемент, а нужен весь ряд. Поэтому лучше брать "диагональный алгоритм".
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
05.01.2015, 16:40
Цитата Сообщение от zer0mail Посмотреть сообщение
достаточно очевидно, что если яйцо разбивается с этажа k, то оно разбивается со всех этажей выше k
Да, это единственное неявное предположение, которое не следует напрямую из условия задачи, об этом уже упоминал выше, как и о том, что не обязательно присутствует этаж с которого яйцо разбивается.
0
 Аватар для castorsky
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,353
05.01.2015, 16:55
Цитата Сообщение от zer0mail Посмотреть сообщение
достаточно очевидно, что если яйцо разбивается с этажа k, то оно разбивается со всех этажей выше k
Прямо капитан очевидность Я говорю что для каждого https://www.cyberforum.ru/cgi-bin/latex.cgi?m \in {1,2,...,k} разные алгоритмы дадут разные минимумы. Допустим для m = m1, m2, m3, m4 первый алгоритм даст 5 попыток при n и k, а для m = m10, m14, m56 другой алгоритм даст минимум при тех же n и k. В математической нотации постановка задачи выглядит так: https://www.cyberforum.ru/cgi-bin/latex.cgi?Z = f \( n, m\) \rightarrow min, m = \langle 1, 2, ..., k \rangle; m, k \in \mathbb{N} а это значит что для ее однозначного решения требуется ввести дополнительные ограничения. Вы же нестанете отрицать что любой алгоритм для какого-то m даст одну попытку, а для другого m другой алгоритм даст тоже одну попытку.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
05.01.2015, 16:58
Какое-то новое видение задачи. Детально в ваших формулах не разбирался, но я стану отрицать. И если
Цитата Сообщение от castorsky Посмотреть сообщение
разные алгоритмы дадут разные минимумы
, то правильный алгоритм даст единственный и минимальный минимум из всех минимумов остальных алгоритмов.
0
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
05.01.2015, 17:00
Цитата Сообщение от castorsky Посмотреть сообщение
а это значит что для ее однозначного решения требуется ввести дополнительные ограничения.
Почему?
0
 Аватар для castorsky
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,353
05.01.2015, 17:06
Цитата Сообщение от _Ivana Посмотреть сообщение
то правильный алгоритм даст единственный и минимальный минимум из всех минимумов остальных алгоритмов
Вы мыслите в верном направлении. И может быть разобрав мат нотацию смогли бы увидеть типовую задачу Но постановка задачи состоит в поиске минимума, а не оптимального решения.
Цитата Сообщение от S_el Посмотреть сообщение
Почему?
Потому что постановка задачи размыта, или сформулирована с ошибками.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
05.01.2015, 17:09
castorsky, чем рисовать "вумные формулы", лучше напишите этажность дома и количество яиц, для которых диагональный алгорим неправильно посчитает максимальное количество попыток m
Вполне возможно, что в некоторых конкретных ситуациях при бросании из окон дома высоты h их потребуется меньше... В общем, нужно среди максимальных mi (зависит от алгоритма) надо найти минимальное m. Что касается размытости, то на любую формулировку может найтись тот, кто ее не поймет.
0
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
05.01.2015, 17:10
Цитата Сообщение от castorsky Посмотреть сообщение
Потому что постановка задачи размыта, или сформулирована с ошибками.
Тогда приведите пример,когда 2 алгоритма,правильных по постановке задачи,дадут разный результат.
9 страниц меня убедили в корректности задачи
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
05.01.2015, 17:13
Я тоже считаю что мыслю в верном направлении, но не вижу ничего размытого. Я говорю - я угадаю эту мелодию с семи нот. Оппонент говорит - а я угадаю с шести. И если он будет угадывать все 20-ти секундные мелодии с шести нот, то моя оценка в 7 нот завышена.
Речь не про конкретные ситуации, а про общие. В конкретной ситуации можно и с двух попыток угадать этаж.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
05.01.2015, 17:17
Или даже с одной
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
05.01.2015, 17:17

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

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

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

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

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


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

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