Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 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
02.01.2015, 02:18
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Dani Посмотреть сообщение
есть ошибки в коде, позже доработаю
смысл в том, что если логарифм двоичный от числа этажей меньше, чем число яиц, то - ответ этот самый логарифм + 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;
    }
}
Спокойной ночи.
Ой, границы выбирал так, чтоб не вылезти и вот, что из этого получилось ну можно просто long long воспользоваться)

а можно и в условии поменять 2^31-1 на 10^9, чтоб проще было но всё равно надо будет проверить h[n-1][m] перед сложением)
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
02.01.2015, 02:22
Цитата Сообщение от _Ivana Посмотреть сообщение
Ибо даже для 4 яиц 2000 попыток дадут огромное количество этажей.
2000 попыток и 2000 яиц дают число с 603 знаками за 8 сек
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 02:23
Цитата Сообщение от zer0mail Посмотреть сообщение
2000 попыток и 2000 яиц дают число с 603 знаками за 8 сек
Вы не поленились написать длинную арифметику для этой задачи?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 02:26
Хорошо что я написал аккуратно и в предположительном тоне... Скажете идею вашего алгоритма?

Добавлено через 1 минуту
ltkj, может это не в С++. У меня например в Haskell бесплатная длинная арифметика на борту.
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
02.01.2015, 02:34
Цитата Сообщение от ltkj Посмотреть сообщение
Вы не поленились написать длинную арифметику для этой задачи?
У меня была длинная арифметика + "длинные" биномиальные коэффициенты. Пришлось допилить чуть-чуть.
Алгоритм - треуголник Паскаля с кэшированием.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 06:16
zer0mail, похоже вы порвали задачу в клочья. Моя рекурсия скромно жует жвачку в сторонке...

Добавлено через 41 минуту
ltkj, спасибо на словах (кнопки все нет) - понял и равенство формул, которое вы писали на прошлой странице (просто выделил пару минут на вдумчивое прочтение а не по верхам в запарке темы), и сделал через неподвижную точку, начиная с нуля. Конечно не 600 знаков за 8 секунд, но концептуально хочу все осознать.

Добавлено через 5 минут
Сейчас попробую придумать через не экспоненциальную хвостовую рекурсию если получится.

Добавлено через 1 час 16 минут
Пожевал я тут жвачку в сторонке, подумал, и решил тоже порвать в клочья эту задачу
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import System.IO
import Data.Time
 
h n m = l!!m where
    l = ntimes n step $ replicate (max 1 (m-n+1)) 0
    ntimes n f = foldl (.) id $ replicate n f
    step = reverse.foldl (\aa@(a:as) x -> (a+x+1):aa) [0]
 
test n m = do
    begT <- getCurrentTime
    let k = show (h n m)
    putStrLn $ "h (" ++ show n ++ "," ++ show m ++ ") = "
    putStrLn $ k
    putStrLn $ "As it was mentioned - " ++ show (length k) ++ " digits ;)"
    endT <- getCurrentTime
    putStrLn $ "Elapsed time - " ++ show (diffUTCTime endT begT)
 
main = do
    test 2000 2000
Сама функция - три строчки кода Результат:

Не по теме:

h (2000,2000) =
1148130695274254524232833201177681984022 3177020886952004776427368257662613923703 138566
5948631650626991844596463898746277344711 8960863055331425931356166653185391299891 453122
8000068877914824004487142892699006348624 4781615463646388363947317026040466353970 904996
5581623988089446296056233116495361642219 7033268134416890898445850560237948480791 405890
0934776500429002716706625830522008132236 2812917612678833172065989953964181270217 798584
0404215985318325154088943390209192055495 7783589672039160081957216630582755380425 583726
0155283487864194320545089152757838826251 7543552880082284277081796545376218485114 9029375
As it was mentioned - 603 digits ;)
Elapsed time - 2.396712s

И это я еще не занимался оптимизацией. Сейчас займусь и тогда посмотрим на цифры
ЗЫ я немножко удовлетворен

Добавлено через 1 час 33 минуты
Особой оптимизации по скорости не получилось, новая функция выполняется на тех же данных в полтора раза дольше, зато зажал ее в одну строчку Вот теперь можно и поспать...
Haskell
1
h n m=(\x->iterate(\l->let g s(x:t)=(x+s):g(s+x+1)t in 0:g 0 l)x!!n)(repeat 0)!!(m+1)
2
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
02.01.2015, 09:17
Хм, интересная штука этот Haskell. Может, стоит присмотреться нему
Пробовал на Maple- не дождался результата. Я написал рекурсию "в лоб", возможно, есть лучший способ.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 12:28
zer0mail, если не скромничать, то я понял и написал штуку поинтереснее чем "рекурсия в лоб". И вообще, я немножко поглубже понял эту задачу. Если будет интерес у участников форума - могу выпендриться и рассказать А пока реализую все-таки функцию поиска минимального количества бросков - есть некоторые идеи.

Добавлено через 1 минуту
Цитата Сообщение от zer0mail Посмотреть сообщение
Хм, интересная штука этот Haskell. Может, стоит присмотреться нему
Не то слово! Вы же видите, одна строчка кода заменяет вашу программу и выполняется в несколько раз быстрее Но если честно это конечно заслуга алгоритма, на С он должен еще быстрее выполняться.

Добавлено через 2 часа 17 минут
UPD цикл поиска m при k = 2^31-1 и n от 1 до 32 и бонусом n = 2^100 - все вместе занимает 0.02 секунды и требует очень немного памяти - http://ideone.com/13SeV3
И можно еще думаю убыстрить в 6 раз минимум (не стал оптимизировать уже), а если длинную арифметику заменить на ограниченные инты - то еще неизвестно во сколько раз быстрее будет.
0
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
02.01.2015, 14:37
_Ivana, если вопрос в производительности, то без рекурсии считается практически мгновенно (в диапазоне int)
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <malloc.h>
 
int main() {
  int n, k, m, i;
  scanf ("%d %d", &n, &k);
 
  int *h = malloc (n * sizeof (*h));
  h[0]= 1;
  for (i=1; i < n; i++) h[i]= h[i-1] * 2 +  1;
 
  for (m= 1; m <= k; m++) {
    if (m > n) {
      h[0]= m-n+1;
      for (i= 1; i < n; i++) h[i] += h[i-1] + 1;
    }
    else h[n-1]= h[m-1];
    if (h[n-1] >= k) break;
  }
  printf ("Result: %d\n", m);
  return 0;
}
2
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 17:29
gng, именно. Но я не сразу додумался до этого нерекурсивного алгоритма, решающего задачу мгновенно и без особых запросов памяти. А вы оказывается знали, а писали со мной медленную прожорливую экспоненциальную рекурсию Чтож, теперь уже можно сказать что задача решена на достаточном уровне для учебной или олимпиадной.
0
 Аватар для Algoritmer
159 / 98 / 25
Регистрация: 07.03.2013
Сообщений: 513
Записей в блоге: 1
02.01.2015, 19:13
Цитата Сообщение от ltkj Посмотреть сообщение
В случае для трех яиц надо посчитать что-то вроде такого (могу ошибаться на плюс-минус один где-нибудь):
Корни многочлена 3-й степени ещё считаются, но наверно дальше будет 4 степень и т.д., их мы найти уже точно не сможем
Не совсем понял, откуда знаменатель 12 ?
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
02.01.2015, 19:24
Цитата Сообщение от Algoritmer Посмотреть сообщение
Не совсем понял, откуда знаменатель 12 ?
Сумма квадратов от 1 до n равна n(n+1)(2n+1)/6 - можно по индукции проверить. А ещё двойка осталась, ведь сумма была квадратов пополам. Там где-то ниже преобразованный ответ был уже
0
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
02.01.2015, 19:43
Извиняюсь перед всеми. Мной была допущена ошибка, влияющая на результат.
Ниже испавленный код.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <malloc.h>
 
int main() {
  int n, k, m, i, max_h;
  scanf ("%d %d", &n, &k);
 
  int *h = malloc (n * sizeof (*h));
  h[0]= 1;
  for (i=1; i < n; i++) h[i]= h[i-1] * 2 +  1;
 
  for (m= 1; m <= k; m++) {
    if (m > n) {
      h[0]= m-n+1;
      for (i= 1; i < n; i++) h[i] += h[i-1] + 1;
      max_h= h[n-1];
    }
    else max_h= h[m-1];
    if (max_h >= k) break;
  }
  printf ("Result: %d\n", m);
  return 0;
}
Цитата Сообщение от _Ivana Посмотреть сообщение
А вы оказывается знали, а писали со мной медленную прожорливую экспоненциальную рекурсию
Рекурсивная более наглядна.
Нерукурсивную я написал по тому же алгоритму после того, как были озвучены требования к производительности.
0
 Аватар для Algoritmer
159 / 98 / 25
Регистрация: 07.03.2013
Сообщений: 513
Записей в блоге: 1
02.01.2015, 19:59
gng, можешь добавить коментарий к строкам с 13 по 16 ?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.01.2015, 21:07
Цитата Сообщение от gng Посмотреть сообщение
Рекурсивная более наглядна.
А представление ее в виде композиции преобразования зато идейно содержательно и вдобавок на порядки эффективнее. Это как раз то, что я хотел, когда говорил о решении через неподвижную точку.
0
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
02.01.2015, 22:53
Цитата Сообщение от Algoritmer Посмотреть сообщение
gng, можешь добавить коментарий к строкам с 13 по 16 ?
Всё строится вокруг того же алгоритма, что и приведенное ранее рекурсивное решение, описываемое рекуррентной формулой:
H[n,m]= H[n-1,m-1] + H[n, m-1] +1
Идея проста и наглядна (уважаемые авторы её уже пояснили выше немного другими словами):
Имея n яиц и m попыток выбираем для первой попытки такой этаж, чтобы внизу осталось максимальное количество этажей, которое можно разрешить с одним разбитым яйцом H[n-1,m-1], а вверху - с полным количеством яиц H[n,m-1] плюс сам выбранный этаж.

При решении без рекурсии вместо двумерного массива используется диагональ ; (1,m-n+1)...(n-2,m-2),(n-1,m-1),(n,m).
Значение первого элемента равно m, остальные считаются последовательно.

Добавлено через 40 минут

Не по теме:

Цитата Сообщение от _Ivana Посмотреть сообщение
А представление ее в виде композиции преобразования зато идейно содержательно и вдобавок на порядки эффективнее
С рекурсией "математичнее". :)
Помните как математик решал задачу с кипячением чайника?

1
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
03.01.2015, 11:34
Пара вопросов:
1. Какая формула для следующего диагонального элемента?
2. Интересно, можно ли придумать диагональную формулу для биномиальных коэффициентов (рекурсивные ведь очень похожи).
0
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
03.01.2015, 13:02
Цитата Сообщение от zer0mail Посмотреть сообщение
1. Какая формула для следующего диагонального элемента?
Приведена выше
C
1
2
h[0]= m-n+1;
for (i= 1; i < n; i++) h[i] += h[i-1] + 1;
Цитата Сообщение от zer0mail Посмотреть сообщение
2. Интересно, можно ли придумать диагональную формулу для биномиальных коэффициентов (рекурсивные ведь очень похожи).
Безусловно, только её уже нельзя назвать диагональной, скорее - построчной.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#define N 16
 
main() {
  int b[N];
  int i, j;
  for (i= 0; i< N; i++)  b[i]= 1;
  printf ("%5d\n", b[0]);
  printf ("%5d%5d\n", b[0], b[1]);
  for (i= 2; i < N; i++) {
    for (j= i-1; j > 0; j--)  b[j]+= b[j-1];
    for (j= 0; j<= i; j++)  printf ("%5d", b[j]);
    printf ("\n");
  }
}
Добавлено через 28 минут
PS. Диагональным массив был назван по отношению к таблице (n,m). Его, конечно, можно нарисовать и подобно биному.
1
 Аватар для Algoritmer
159 / 98 / 25
Регистрация: 07.03.2013
Сообщений: 513
Записей в блоге: 1
03.01.2015, 13:07
Цитата Сообщение от gng Посмотреть сообщение
Всё строится вокруг того же алгоритма, что и приведенное ранее рекурсивное решение, описываемое рекуррентной формулой:
H[n,m]= H[n-1,m-1] + H[n, m-1] +1
Это то я понял, как только увидел первую версию кода _Ivana ...

Цитата Сообщение от gng Посмотреть сообщение
без рекурсии вместо двумерного массива используется диагональ ; (1,m-n+1)...(n-2,m-2),(n-1,m-1),(n,m).
А вот этот момент я не сразу просёк... спасибо
0
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
03.01.2015, 20:24
_Ivana, сколько времени на Haskell считаются 50000 яиц и 100000 попыток? На C++ диагональный алгоритм считает <6 сек...

Добавлено через 21 минуту
Упс - не там точку останова поставил. Сейчас пересчитаю...

Добавлено через 1 час 59 минут
Пришлось уменьшить аппетиты 20000 попыток и 10000 яиц считал ~33 мин. Число этажей содержит 6021 знак.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
03.01.2015, 20:24

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

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

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

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

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


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

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