Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 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
02.01.2015, 00:44
Студворк — интернет-сервис помощи студентам
АААА
я понял. я очень сильно тупил все это время
спасибо что не отвернулись
1
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 00:46
Цитата Сообщение от _Ivana Посмотреть сообщение
Очередной раз предлагаю вам пробежаться 14-ю попытками из двух яиц до 105 этажа на бумажке - как я сделал еще в прошлом году! Бросаете первое с 14-го, потом с 27-го и т.д. Поймете почему сумма.

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

Добавлено через 10 минут
Вести с полей - для двух яиц oeis опознала очевидные , а уже для трех .
Думаю, в этой задаче такой формулы и нет. В случае для 2 яиц она уже не очень приятно выглядит, а дальше там (вроде бы) получаются многочлены большей степени, у них надо уметь искать корни, а это уже никак нельзя сделать с помощью формулы.

Я сейчас без листочка с ручкой, потому несколько тяжеловато думается про задачу с треугольниками. Но было б интересно попробовать сходу придумать нерекуррентную формулу.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 00:50
Dani, плюс вам за дохождение до конца а не бросание на полупонимании. Как, например, у меня в этой задаче со вторым кодом и неподвижной точкой - пока полупонимание. Но просто надо чуть усилий приложить. Если выложите вашего кота - количество полупонимания еще возрастет

Добавлено через 1 минуту
Цитата Сообщение от ltkj Посмотреть сообщение
Но было б интересно попробовать сходу придумать нерекуррентную формулу.
Сниму шляпу если выведете сами.
1
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
02.01.2015, 00:54
Цитата Сообщение от _Ivana Посмотреть сообщение
Если выложите вашего кота - количество полупонимания еще возрастет
Я очень хочу найти хорошее решение, которое пройдет ограничения
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 01:01
В случае для трех яиц надо посчитать что-то вроде такого (могу ошибаться на плюс-минус один где-нибудь):

https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{k=0}^{m-1} \frac{k(k+1)}{2} + 1 = \sum_{k=0}^{m-1} \frac{k^2}{2} + \sum_{k=0}^{m-1} \frac {k}{2}+ m = \frac{(m-1)\cdot m \cdot (2m-1)}{12} + \frac{m(m-1)}{2} + m

Корни многочлена 3-й степени ещё считаются, но наверно дальше будет 4 степень и т.д., их мы найти уже точно не сможем
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 01:08
ltkj, может я неправильно понимаю, но при подходе "имеем быструю h(n,m) а потом гоним ее в возрастающем цикле" нам не надо никаких корней - только оптимально свернутое суммирование. Мы же не сразу как Dani ищем попытки, а высоты считаем. Вот для них и вполне возможна красивая формула - мое очередное экстрасенсорное предположение.

Добавлено через 2 минуты
А вы пока честно разворачиваете этапы рекурсивных сумм и приводите подобные, может удастся вывести общую закономерность и аналитическую формулу от n, m.
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 01:14
Цитата Сообщение от _Ivana Посмотреть сообщение
ltkj, может я неправильно понимаю, но при подходе "имеем быструю h(n,m) а потом гоним ее в возрастающем цикле" нам не надо никаких корней - только оптимально свернутое суммирование. Мы же не сразу как Dani ищем попытки, а высоты считаем. Вот для них и вполне возможна красивая формула - мое очередное экстрасенсорное предположение.

Добавлено через 2 минуты
А вы пока честно разворачиваете этапы рекурсивных сумм и приводите подобные, может удастся вывести общую закономерность и аналитическую формулу от n, m.
Для h(2,m) формула n(n+1)/2.
Для h(3,m) я вроде бы написал выше.
Аналогичные формулы можно вывести для любого n (можно считать, что n ограничен 31 и полдня повыписывать формулы(ну или повбивать в вольфрам)), но проблема будет в том, что по полученной функции всё равно надо будет подбирать m, чтоб h(n,m) было рядом с k. Эта задача уже формулой не решится точно. Можно конечно как-то оптимизировать поиск, но явной формулы для ответа не будет.

Добавлено через 2 минуты
Цитата Сообщение от ltkj Посмотреть сообщение
В случае для трех яиц надо посчитать что-то вроде такого (могу ошибаться на плюс-минус один где-нибудь):

https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{k=0}^{m-1} \frac{k(k+1)}{2} + 1 = \sum_{k=0}^{m-1} \frac{k^2}{2} + \sum_{k=0}^{m-1} \frac {k}{2}+ m = \frac{(m-1)\cdot m \cdot (2m-1)}{12} + \frac{m(m-1)}{2} + m

Корни многочлена 3-й степени ещё считаются, но наверно дальше будет 4 степень и т.д., их мы найти уже точно не сможем
Да, там на 4 надо делить второе слагаемое, но всё равно сути не меняет
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 01:16
Цитата Сообщение от ltkj Посмотреть сообщение
но явной формулы для ответа не будет
Повторюсь что она и не нужна. Если будет условно красивая и компактная h(n,m) через многочлен, то потом просто прогоним. При ваших данных максимальное количество попыток у нас будет при 2 яйцах (одно тривиально) и максимальном этаже - а это квадратный корень из удвоенного этажа, т.е. 2^16=65536 - вполне можно за разумное время добежать с единицы в цикле
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 01:20
Цитата Сообщение от _Ivana Посмотреть сообщение
Повторюсь что она и не нужна. Если будет условно красивая и компактная h(n,m) через многочлен, то потом просто прогоним. При ваших данных максимальное количество попыток у нас будет при 2 яйцах (одно тривиально) и максимальном этаже - а это квадратный корень из удвоенного этажа, т.е. 2^16=65536 - вполне можно за разумное время добежать с единицы в цикле
Почти уверен, у этих многочленов общего вида нет. Но для каждого n, не большего 31, в вольфраме наверно можно посчитать этот многочлен. Тогда ваша задача будет выполнена - напишем 31 строчку с многочленам на каждый возможный случай
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 01:21
А бинарным поиском вообще быстро должно найтись - у нас же монотонная функция от m

Добавлено через 1 минуту
Цитата Сообщение от ltkj Посмотреть сообщение
Почти уверен, у этих многочленов общего вида нет.
А вот в этом то и весь вопрос. Мои темы с подсчетом количества треугольников в этом плане показательны - там я тоже даже не предполагал существование подобного многочлена, а он оказался.
1
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
02.01.2015, 01:29
У меня 2000 попыток и 2000 яиц считает 8 сек.
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 01:30
Цитата Сообщение от _Ivana Посмотреть сообщение
А бинарным поиском вообще быстро должно найтись - у нас же монотонная функция от m

Добавлено через 1 минуту
А вот в этом то и весь вопрос. Мои темы с подсчетом количества треугольников в этом плане показательны - там я тоже даже не предполагал существование подобного многочлена, а он оказался.
А можете проверить, то ли я посчитал для трех? Ибо в этом случае общая формула-то есть!
Upd: извиняюсь, я 1 не прибавлял с некоторого момента. Может, и нет такой формулы

Добавлено через 55 секунд
Цитата Сообщение от zer0mail Посмотреть сообщение
У меня 2000 попыток и 2000 яиц считает 8 сек.
Примерного такого я на самом деле и ждал но тут у людей вышло несколько быстрее

Upd: 2000 этажей может?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 01:38
Цитата Сообщение от zer0mail Посмотреть сообщение
У меня 2000 попыток и 2000 яиц считает 8 сек.
Рискну предположить что вы ошиблись. Ибо даже для 4 яиц 2000 попыток дадут огромное количество этажей.

ltkj, тогда напишите финальную формулу для n=3, а то вы ее уточняете и я не знаю какая правильная. Можно без латекса, прямо */^ но со скобками, чтобы было понятно.
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 01:39
Цитата Сообщение от _Ivana Посмотреть сообщение
Рискну предположить что вы ошиблись. Ибо даже для 4 яиц 2000 попыток дадут огромное количество этажей.

ltkj, тогда напишите финальную формулу для n=3, а то вы ее уточняете и я не знаю какая правильная. Можно без латекса, прямо */^ но со скобками, чтобы было понятно.
Да, общая формула рассыпалась, как я стал единицу всегда добавлять)
Для трех вроде получается m(m^2+5)/6
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 01:43
ltkj, m(m^2+5)/6 совпадает по крайней мере от 1 до нескольких сотен попыток, вы не ошиблись при выводе похоже. Значит, история задачи с треугольниками может нам помочь не отмахиваться сразу что такого многочлена нет?
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 01:44
Цитата Сообщение от _Ivana Посмотреть сообщение
ltkj, m(m^2+5)/6 совпадает по крайней мере от 1 до нескольких сотен попыток, вы не ошиблись при выводе похоже.
А дальше уже считал не я, а вольфрам) и там что-то не очень хорошее выходит
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 01:50
Ну, вполне возможно. Но может быть что-то хорошее как многочлен не одной переменной а нескольких, выражающихся через m? Там simplify есть? Может он свернет покомпактнее? Я в Матлабе не очень хорошо умею им пользоваться в символьных вычислениях.
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
02.01.2015, 02:03
Вот кажется решение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <map>
#include <utility>
#include <cmath>
 
using namespace std;
 
const int MAX_ATTEMPTS = 50;
 
int main()
{
    int n, k;
    cin >> n >> k;
    int x = ceil(log(k) / log(2)) + 1;
    if(x <= n)
        cout << x;
    else
    {
        int dp[MAX_ATTEMPTS + 1][MAX_ATTEMPTS + 1];
        for(int i = 0; i <= MAX_ATTEMPTS; ++i)
        {
            dp[0][i] = 0;
            dp[i][0] = 0;
        }
 
        for(int i = 1; i <= n; ++i)
        {
            dp[i][i] = dp[i-1][i] + dp[i-1][i-1] + 1;
            for(int j = 0; j <= MAX_ATTEMPTS; ++j)
            {
                if(j == 0)
                    dp[i][j] = dp[i][j];
                else if(i == 1)
                    dp[i][j] = j;
                else if (i > j)
                    dp[i][j] = dp[j][j];
                else
                    dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + 1;
            }
        }
        int ans = 0;
        while(dp[n][++ans] < k);
        cout << ans;
    }
}
Добавлено через 42 секунды

Не по теме:

неужели можно идти спать :)

0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 02:06
Dani, до 50 яиц и до 50 попыток, я не ошибся? А вроде звучали ограничения в 2^31 на количество яиц. И мы точно уложимся в 50 попыток при 2 яйцах и 2^31 этажах?
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
02.01.2015, 02:16
Цитата Сообщение от _Ivana Посмотреть сообщение
Dani, до 50 яиц и до 50 попыток, я не ошибся? А вроде звучали ограничения в 2^31 на количество яиц. И мы точно уложимся в 50 попыток при 2 яйцах и 2^31 этажах?
есть ошибки в коде, позже доработаю
смысл в том, что если логарифм двоичный от числа этажей меньше, чем число яиц, то - ответ этот самый логарифм + 1.
в противном случае (когда уже яиц <= 31) просчитываем динамикой.
но в коде я опять в типы не влезаю.
может я и неправ, позже разберусь

Добавлено через 1 минуту
Вот, это не только я заметил
Задача про яйца

Добавлено через 1 минуту
Вот самая акутальная на данный момент программа
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <map>
#include <utility>
#include <cmath>
 
using namespace std;
 
typedef unsigned long long ull;
const int MAX_ATTEMPTS = 50;
 
int main()
{
    int n, k;
    cin >> n >> k;
    int x = ceil(log(k) / log(2)) + 1;
    if(x <= n)
        cout << x;
    else
    {
        ull dp[MAX_ATTEMPTS + 1][MAX_ATTEMPTS + 1];
        for(int i = 0; i <= MAX_ATTEMPTS; ++i)
        {
            dp[0][i] = 0;
            dp[i][0] = 0;
        }
 
        for(int i = 1; i <= n; ++i)
        {
            dp[i][i] = dp[i-1][i] + dp[i-1][i-1] + 1;
            for(int j = 0; j <= MAX_ATTEMPTS; ++j)
            {
                if(j == 0)
                    dp[i][j] = dp[i][j];
                else if(i == 1)
                    dp[i][j] = j;
                else if (i > j)
                    dp[i][j] = dp[j][j];
                else
                    dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + 1;
            }
        }
        int ans = 0;
        while(dp[n][++ans] < k);
        cout << ans;
    }
}
Спокойной ночи.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
02.01.2015, 02:16

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

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

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

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

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


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

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