1 | |
Бросание яиц n яиц с балкона k-го этажа01.01.2015, 04:41. Показов 1666. Ответов 10
Метки нет (Все метки)
Очередная интересная тема с плюсовом разделе нарисовалась. Там решили, теперь хочу предложить ее здесь. но чур не подсматривать
Собственно, условие: У вас есть n яиц и вы живете в k-этажном доме. Какое наименьшее число попыток потребуется для того, чтоб узнать наивысший этаж, упав с которого, яйцо не разобьется? Если кому опять будет непонятно нестрого сформулированное условие, готов пояснить что будет непонятно.
0
|
01.01.2015, 04:41 | |
Ответы с готовыми решениями:
10
Количество яиц. Сколько яиц было у крестьянки? Лотки для яиц в холодильнике Сколько яиц могло быть в корзине? |
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
|
01.01.2015, 13:29 | 3 |
Чем больше яиц, тем, до некоторого предела, меньше необходимое количество попыток. Всегда можно обойтись и одним яйцом, но тогда всегда (в худшем случае) будет (k-1) попытка.
0
|
Модератор
|
|
01.01.2015, 13:35 | 4 |
- начинаем с первого этажа и идем вверх. Как только яйцо разобьется - этаж найден (макс. k шагов). Если к-во яиц неограниченно, то двоичный поиск ~ log2(k) должно хватить. Так?
0
|
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
|
01.01.2015, 13:51 | 5 |
Да, одним яйцом за k попыток. В общем случае - сначала (n-1) яйцом уменьшаем диапазон этажей, потом последним ищем. Диапазон уменьшается как k -> (k-1) / 2, не просто деление.
0
|
Модератор
|
|
01.01.2015, 15:11 | 6 |
Я так понял: 10-ти этажный дом, если есть 4 яйца, то метод бисекции - бросаем с 5-го (разбилось), с 3-го (разбилось), со 2-го (разбилось), с 1-го (разбилось). -4 попытки. (Методом золотого сечения тут, кстати, столько же 6,4,2,1). Но если яиц меньше придётся бросать начиная с меньших этажей увеличивая число попыток.
Не по теме: Малолетние террористы такие задачки придумывают - яйцами из окон бросаться.
1
|
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
|
01.01.2015, 17:55 | 8 |
Похоже, золотое сечение тут лучше бисекции. Например, 11 этажей, 2 яйца, начинаем с 5-го этажа - 5 попыток; если начать с 6-го - будет 6.
Добавлено через 6 минут И обратный пример - 15 этажей, много яиц. Золотое сечение экономит яйца, бисекция экономит попытки. Добавлено через 4 минуты По-моему, за менее чем ⌈log2(k+1)⌉ попыток узнать невозможно при любом количестве яиц...
0
|
01.01.2015, 19:36 [ТС] | 9 |
Я вот тоже засомневался. Похоже, мой код меня подвел Сейчас попробую разобраться где он ошибается, выведу отладочную печать... (Это же на Си, там легко )
Добавлено через 50 минут Исправил своего кота, теперь результаты больше похожи на правду. (Вчерашний новогодний вариант был сделан наспех необдуманно) При 4 яйцах и 10 этажах 4 попытки. Можно протестировать на других данных. Добавлено через 7 минут Некоторое буквоедство - на всякий случай, чтобы не было недопониманий условия - будет k попыток. Ибо никто не гарантирует, что в доме существует этаж, упав с которого яйцо обязательно разобьется.
0
|
Catstail
|
01.01.2015, 19:38
#10
|
0
|
_Ivana
|
01.01.2015, 19:39
[ТС]
Бросание яиц n яиц с балкона k-го этажа
#11
|
Не по теме: Если под бросанием яиц понимать испытания самолетов на прочность, то еще и титановые бывают вроде.
0
|
01.01.2015, 19:39 | |
Запрос в access: среднее количество яиц Самодельный инкубатор на 10000 яиц. Стоимость? Перевод с С++ - определить, сколько было снесено яиц Количество вариантов расположения количества V яиц по N корзинам Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |