Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 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
01.01.2015, 19:51
Студворк — интернет-сервис помощи студентам
_Ivana, если честно, у меня до сих пор смутное понимание задачи, но в вашем коде h(n, m) - ответ для n яиц и m этажей, как я понял. А дальше вы перебираете этаж и суммируете ответ. И тут вопрос: почему сумма? Мы же в конечном итоге какой-то 1 этаж должны выбрать, и для наихудшего случая это должно быть max(h(n-1, i)), нет?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 19:55
Dani, у меня постепенно растет и понимание задачи и понимание моего кота в ней. Функция h(n,m) - это максимальная высота дома, который мы можем гарантированно проверить имея n яиц и m бросков. А в основном коде я гоняю ее в цикле с нуля бросков, пока ее результат меньше необходимой высоты дома.
1
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 20:01
Предположим. А почему мы эти высоты суммируем тогда? Нам же попытки надобно найти.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 20:14
Давайте по шагам. Если у нас есть допустим 10 яиц. И ноль попыток. Какую высоту мы сможем проверить? Правильно, ноль. Если те же 10 яиц и одна попытка? Правильно, 10. Если 10 яиц и 2 попытки? Тут на приходит на помощь функция h(10,2), она вернет какой-то результат. И если у нас задача найти количество попыток для дома в 100500 этажей, я вызываю свою функцию этажей от постоянного заданного количества яиц 10 с увеличивающимися количеством попыток - пока результат функции не станет больше или равен желаемым 100500. Но это все тривиальщина, главная соль - в самой функции h(n,m). А она получилась на редкость элегантна, при любых условиях, даже при огромном количестве яиц и малом количестве попыток.

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

Не по теме:

ЗЫ все спасибы и впечатления, незаслуженно адресованные моему предыдущему ошибочному коту, прошу записывать на счет последнего правильного кота :)

1
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 20:15
Цитата Сообщение от _Ivana Посмотреть сообщение
Если те же 10 яиц и одна попытка? Правильно, 10.
10? Один же раз можем кинуть.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 20:16
Если те же 10 яиц и одна попытка? Правильно, 10
Я опечатался и вас запутал - конечно же 1 Но думаю вы поняли.

Добавлено через 1 минуту
Не успел написал до вашего комментария. Просто проверьте h(10,1). Я впопыхах вам сказал глупость, но функцию правильно написал.
1
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 20:17
Все равно не могу понять, почему сумма. Может быть это поможет: почему s += h(n - 1, i) + 1?
0
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
01.01.2015, 20:23
У меня вроде сошлось в условием 10, 780000 -> 21.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
 
int max_floor (int n, int m) {
  if (n == 1) return m;
  if (m < n) return max_floor (m, m);
  return max_floor (n, m-1) + max_floor (n-1, m-1) + 1;
}
 
int main() {
  int n, k, m;
  scanf ("%d %d", &n, &k);
  for (m= n; m < k; m++) {
    if (max_floor (n, m) >= k) break;
  }
  printf ("%d\n", m);
  return 0;
}
И сошлось с тупым перебором
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
int egges (int n, int k) {
  if (k <= 1 || n == 1) return k;
  int i, r, r1, r2, res= k;
  for (i= 1; i <= k; i++) {
    r1 = egges (n-1, i-1);
    r2 = egges (n, k-i);
    r= r1 > r2 ? r1 : r2;
    if (res > r) res= r;
  }
  return res + 1;
}
 
int main() {
  int n, k, i;
  scanf ("%d %d", &n, &k);
  printf ("%d\n", egges (n, k));
  return 0;
}
Правда не сошлось с резльтатом вышеприведенного кода.

Добавлено через 5 минут
PS. т.е не сошлось с кодом _Ivana
1
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 20:30
gng, все сошлось. Просто замените функцию h(n,m) на мою последнюю правильную.

Добавлено через 4 минуты
Цитата Сообщение от Dani Посмотреть сообщение
почему s += h(n - 1, i) + 1?
Потому что кинув яйцо с i-го этажа мы оставляем непроверенными i-1, и нам надо чтобы за минус одну попытку мы все их проверили. Зайдя с другой стороны, мы можем запросить, сколько этажей мы проверим за меньшее на 1 количество попыток и прибавить к ним 1 - тот этаж с которого скинули текущую попытку. Может путанно объясняю, но распишите на бумажке 2 яйца и 3 попытки например.
2
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 20:35
Цитата Сообщение от _Ivana Посмотреть сообщение
за меньшее на 1 количество попыток
i - это тоже число, что и в h(n-1, i) + 1 ?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 20:41
Возьмите 2 яйца и 3 попытки. Первый бросок с 3 этажа, т.к. за две оставшиеся попытки мы сбросим с 1 и 2 этажей второе яйцо. То есть, за один бросок первого яйца мы проходим 3 этажа. Второй бросок - я пятого. Т.к. за один оставшийся мы пройдем 4 этаж. И третий - с 6-го, т.к. за 0 оставшихся мы пройдем 0 этажей. Итого за каждый очередной бросок первого яйца мы можем пройти количество этажей, проходимых за меньшее на 1 количество бросков меньшего на 1 количества яиц плюс один этаж - с которого мы бросили первое яйцо.
1
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 20:44
_Ivana но количество бросков не на 1 то уменьшается а все-равно + 1 остается
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 20:47
Dani, с каждым очередным броском первого яйца количество оставшихся бросков уменьшается именно на 1 и никак иначе. И именно один дополнительный этаж мы и проверяем каждым броском первого яйца. Ну распишите на бумажке, я вас третий раз прошу уже Мне еще надо волшебный код gng понять, похоже, там тоже красота!
1
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 20:50
_Ivana, так for (int i=0; i<m; i++) s += h(n-1,i)+1; --> n-1 уменьшаем яйца на 1, i - уменьшаем броски на (m - i)
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 20:50
Dani, я так понимаю, вас ввёл в ступор этот цикл. Сумма там идёт по i от 0 до m-1, а в математических рассуждениях цикл будет наоборот - от m-1 до 0. Результат же будет таким же
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 20:55
Правильно, яйца уменьшаем на 1 (считая каждый раз что первое разбилось на очередном броске), а попытки суммируем по убывающему количеству оставшихся.
Подробно:
h(2,3) = h(1,2) (=2 - первый и второй этажи) + 1 (третий этаж) : если первое яйцо разбилось в первой попытке
+ h(1,1) (=1 - четвертый этаж) + 1 (пятый этаж) : если первое яйцо разбилось во второй попытке
+ h(1,0) (=0 - никакой этаж) + 1 (шестой этаж) : и неважно уже разбилось первое яйцо или нет

Добавлено через 42 секунды
ltkj, правильно, я просто поменял порядок суммирования для простоты кода, воспользовался коммутативностью моноида sum
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 20:56
Цитата Сообщение от gng Посмотреть сообщение
У меня вроде сошлось в условием 10, 780000 -> 21.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
 
int max_floor (int n, int m) {
  if (n == 1) return m;
  if (m < n) return max_floor (m, m);
  return max_floor (n, m-1) + max_floor (n-1, m-1) + 1;
}
 
int main() {
  int n, k, m;
  scanf ("%d %d", &n, &k);
  for (m= n; m < k; m++) {
    if (max_floor (n, m) >= k) break;
  }
  printf ("%d\n", m);
  return 0;
}
И сошлось с тупым перебором
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
int egges (int n, int k) {
  if (k <= 1 || n == 1) return k;
  int i, r, r1, r2, res= k;
  for (i= 1; i <= k; i++) {
    r1 = egges (n-1, i-1);
    r2 = egges (n, k-i);
    r= r1 > r2 ? r1 : r2;
    if (res > r) res= r;
  }
  return res + 1;
}
 
int main() {
  int n, k, i;
  scanf ("%d %d", &n, &k);
  printf ("%d\n", egges (n, k));
  return 0;
}
Правда не сошлось с резльтатом вышеприведенного кода.

Добавлено через 5 минут
PS. т.е не сошлось с кодом _Ivana
Правильно ли я понимаю, что у вас теоретически не может получиться ответ, в котором кол-во попыток меньше кол-ва яиц?
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 20:57
Цитата Сообщение от _Ivana Посмотреть сообщение
попытки суммируем
Так этажи же суммируем!
Цитата Сообщение от _Ivana Посмотреть сообщение
Функция h(n,m) - это максимальная высота дома
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 20:59
Цитата Сообщение от Dani Посмотреть сообщение
Так этажи же суммируем!
Правильно! Три этажа за первый бросок первого яйца (2+1), 2 за второй (1+1) и 1 за третий (0+1)! Так и нагребаем 105 этажей за 14 попыток при 2 яйцах
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 21:00
Ладно, забуду все, попробую свое решение написать.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
01.01.2015, 21:00

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

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

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

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

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


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

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