Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 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
01.01.2015, 21:05
Студворк — интернет-сервис помощи студентам
А вообще идея у gng верная, только m надо от 1 брать. По производительности пока не знаю, она зависит от порядка ответа, а его ещё прикинуть надо. но явно лучше динамикой переделать.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 21:13
ТС-у плюс за хорошую задачу. Осталось понять и проверить на слабые места алгоритм gng и реализовать свой в fix концепции.
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 21:20
Ваши алгоритмы ничем почти не отличаются, только он чуть лучше считает в случае динамической записи (то есть если не пересчитывать заново предыдущие результаты).

Это видно из соотношения
https://www.cyberforum.ru/cgi-bin/latex.cgi?h(n,m) = \sum_{i=0}^{m-1}( h(n-1,i)  + 1) = \sum_{i=0}^{m-2} (h(n-1,i) + 1) + h(n-1, m-1) + 1 = h(n, m-1) + h(n - 1, m - 1) + 1
То есть вы считаете длинную сумму, а он вместо этого складывает 3 числа.

В случае же рекурсии вроде вообще всё одинаково.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 21:23

Не по теме:

А вот и те самые более способные участники о которых я говорил на предыдущей странице! :)


ltkj, спасибо, постараюсь осознать эквивалентность. Хотя еще действительно хочу переписать через неподвижную точку, причем не просто тупо применив правило, а с осознанием сути происходящего
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 21:24
_Ivana, а как правильно запускать то вашу функцию?
так?
C++
1
for(int i = 0; i < 100; ++i) if(h(n, i) >= k) return i;
т.е. n - кол-во яиц, k - кол-во этажей в доме, h(i, j) - максимальная высота дома, которую можно определить если есть i яиц и j бросков.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 21:25
Dani, так, только мне не нравится волшебное число 100 и много символов, я написал то же самое как
C++
1
while (h(n, i)<k) i++;
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 21:31
Могу даже без этих сумм попробовать пояснить, что у него за формула. Первым броском мы должны выбрать этаж, равный h(n-1,m-1) + 1. Вы вроде это тоже используете, но если надо пояснить, почему он оптимальный, могу написать ниже. Далее, если яйцо не разбилось, остается на одну меньше попыток и столько же яиц. Максимальный этаж для них равен h(n,m-1) - уже считали. Из этого и получается ответ. Вы же просто заново считали h(n,m-1), прикидывая, какой этаж выбрать следующим и т.д.
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 21:32
А при 1 1 ответ разве 1?
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 21:33
Цитата Сообщение от Dani Посмотреть сообщение
А при 1 1 ответ разве 1?
А вы заранее знаете, разобьётся ли с первого этажа яйцо или нет?
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 21:37
Цитата Сообщение от ltkj Посмотреть сообщение
А вы заранее знаете, разобьётся ли с первого этажа яйцо или нет?
А если разобьется что тогда? Неизвестно что, вот что
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 21:39
ltkj, почему-то я не могу ставить вам плюсы (нет кнопки под вашими постами), но как только она появится - с меня пара как минимум
Dani, как раз известно что - мы нашли предел прочности самолетов яиц
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 21:39
Цитата Сообщение от Dani Посмотреть сообщение
А если разобьется что тогда? Неизвестно что, вот что
Варианта 2 - наименьший этаж, с которого разбивается, равен 1 или с любого этажа дома не разбивается.
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 21:43
Цитата Сообщение от ltkj Посмотреть сообщение
Варианта 2 - наименьший этаж, с которого разбивается, равен 1 или с любого этажа дома не разбивается.
И что же вы будете делать в случае, когда разобьется? Такого этажа ведь нету. В условии не слова.
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Какое наименьшее число попыток потребуется для того, чтоб узнать наивысший этаж, упав с которого, яйцо не разобьется?
Может предполагается, что этаж существует.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
01.01.2015, 21:47
Цитата Сообщение от Dani Посмотреть сообщение
Может предполагается, что этаж существует.
Как раз этого не предполагается. Предполагается за кадром только монотонность безобразия - если яйцо не разбилось с i-го этажа, значит не разобьется и со всех что ниже. Хотя это действительно неочевидно из формальной постановки и надо выжимать из так называемого "здравого смысла".

ЗЫ вот как мой кот выглядит в другой парадигме
Haskell
1
2
3
4
maxfloor 1 m = m
maxfloor n m = sum.map ((+1).maxfloor (n-1)) $ [0..m-1]
 
task n k = until ((>=k).maxfloor n) (+1) 0
Считает долго, во-первых в интерпретаторе, а во-вторых рекурсия экспоненциальная в цикле, неоптимально.
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 21:47
Цитата Сообщение от Dani Посмотреть сообщение
И что же вы будете делать в случае, когда разобьется? Такого этажа ведь нету. В условии не слова.
Может предполагается, что этаж существует.
Надо знать полное точное условие задачи. Обычно такие мелкие случаи оговариваются.
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 21:53
_Ivana, ltkj, я подумал вот что: пусть F(i, j) -- наименьшее кол-во попыток если есть i этажей и j яиц. Вот такие у меня варианты:
i == 0: F(i, j) = 0
иначе: F(i, j) = [кидаем с этажа номер x, 1 <= x <= i]
max(
[яйцо разбивается]F(x - 1, j - 1)
[яйцо не разбивается]F(i - x, j)
);
Правильно мыслю?
0
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
01.01.2015, 21:55
Цитата Сообщение от ltkj Посмотреть сообщение
Правильно ли я понимаю, что у вас теоретически не может получиться ответ, в котором кол-во попыток меньше кол-ва яиц?
Да, чтобы считало в этом случае, цикл в главной программе нужно начать от 1, а не с n.
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= 1; m < k; m++) {
    if (max_floor (n, m) >= k) break;
  }
  printf ("%d\n", m);
  return 0;
}
Кто
0
122 / 24 / 6
Регистрация: 31.12.2014
Сообщений: 164
01.01.2015, 21:57
Цитата Сообщение от Dani Посмотреть сообщение
_Ivana, ltkj, я подумал вот что: пусть F(i, j) -- наименьшее кол-во попыток если есть i этажей и j яиц. Вот такие у меня варианты:
i == 0: F(i, j) = 0
иначе: F(i, j) = [кидаем с этажа номер x, 1 <= x <= i]
max(
[яйцо разбивается]F(x - 1, j - 1)
[яйцо не разбивается]F(i - x, j)
);
Правильно мыслю?
Max надо брать по всем x, а там брать сумму 2 тех f, которые вы написали. Только алгоритм этот очень долгий будет. Для 780000 этажей он не сможет посчитать
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
01.01.2015, 22:00
Цитата Сообщение от ltkj Посмотреть сообщение
Только алгоритм этот очень долгий будет
Это понятно, я хочу постепенно придти к быстрому алгоритму
Цитата Сообщение от ltkj Посмотреть сообщение
Max надо брать по всем x, а там брать сумму 2 тех f, которые вы написали
В смысле? Я перебираю все x и беру (максимум из функций (2х случаев, если разобьется или нет)) + 1 (забыл написать в прошлом сообщении). Какая тут сумма все никак не пойму...
0
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
01.01.2015, 22:02
Цитата Сообщение от ltkj Посмотреть сообщение
Max надо брать по всем i, а там брать сумму 2 тех f, которые вы написали. Только алгоритм этот очень долгий будет. Для 780000 этажей он не сможет посчитать
Этот алгоритм (тупым перебором) у меня был приведен. Считает очень долго уже для 30 яиц. Если кэшировать промежуточные результаты, то может считать примерно до 100 тыс. Потом всё равно тормозит.

Добавлено через 1 минуту
Цитата Сообщение от gng Посмотреть сообщение
для 30 яиц
прошу прощения, до 30 этажей.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
01.01.2015, 22:02

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

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

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

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

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


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

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