4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
1

Бросание яиц n яиц с балкона k-го этажа

01.01.2015, 04:41. Показов 1666. Ответов 10
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Очередная интересная тема с плюсовом разделе нарисовалась. Там решили, теперь хочу предложить ее здесь. но чур не подсматривать
Собственно, условие: У вас есть n яиц и вы живете в k-этажном доме. Какое наименьшее число попыток потребуется для того, чтоб узнать наивысший этаж, упав с которого, яйцо не разобьется?

Если кому опять будет непонятно нестрого сформулированное условие, готов пояснить что будет непонятно.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.01.2015, 04:41
Ответы с готовыми решениями:

Количество яиц.
Женщина шла на базар продавать яйца. Ее случайно сбил с ног всадник, в результате чего все яйца...

Сколько яиц было у крестьянки?
Крестьянка несла на базар яйца. Проезжавший всадник толкнул ее, и все яйца разбились. На вопрос...

Лотки для яиц в холодильнике
Не обращала внимание раньше, а вот когда родители купили холодильник, то заметила, что лоток для...

Сколько яиц могло быть в корзине?
Необxодимо решить задачу чикличским оператором repeat until Женщина шла на базар и разбила...

10
Модератор
Эксперт функциональных языков программированияЭксперт Python
36357 / 20236 / 4211
Регистрация: 12.02.2012
Сообщений: 33,514
Записей в блоге: 13
01.01.2015, 13:10 2
Непонятно, как проводить испытания. Можно бросить яйцо с любого этажа? И какую роль играет чиcло n?
0
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
01.01.2015, 13:29 3
Цитата Сообщение от Catstail Посмотреть сообщение
И какую роль играет чиcло n?
Чем больше яиц, тем, до некоторого предела, меньше необходимое количество попыток. Всегда можно обойтись и одним яйцом, но тогда всегда (в худшем случае) будет (k-1) попытка.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
36357 / 20236 / 4211
Регистрация: 12.02.2012
Сообщений: 33,514
Записей в блоге: 13
01.01.2015, 13:35 4
Цитата Сообщение от Somebody Посмотреть сообщение
Всегда можно обойтись и одним яйцом
- начинаем с первого этажа и идем вверх. Как только яйцо разобьется - этаж найден (макс. 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
Модератор
5042 / 3271 / 526
Регистрация: 01.06.2013
Сообщений: 6,800
Записей в блоге: 9
01.01.2015, 15:11 6
Я так понял: 10-ти этажный дом, если есть 4 яйца, то метод бисекции - бросаем с 5-го (разбилось), с 3-го (разбилось), со 2-го (разбилось), с 1-го (разбилось). -4 попытки. (Методом золотого сечения тут, кстати, столько же 6,4,2,1). Но если яиц меньше придётся бросать начиная с меньших этажей увеличивая число попыток.

Не по теме:

Малолетние террористы такие задачки придумывают - яйцами из окон бросаться.

1
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
01.01.2015, 17:33  [ТС] 7
Цитата Сообщение от KolodeznyDiver Посмотреть сообщение
4 попытки.
Подсказка - я угадаю этот этаж за 3 попытки.

Добавлено через 4 минуты
ЗЫ если я не ошибся, конечно
0
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
01.01.2015, 17:55 8
Похоже, золотое сечение тут лучше бисекции. Например, 11 этажей, 2 яйца, начинаем с 5-го этажа - 5 попыток; если начать с 6-го - будет 6.

Добавлено через 6 минут
И обратный пример - 15 этажей, много яиц. Золотое сечение экономит яйца, бисекция экономит попытки.

Добавлено через 4 минуты
Цитата Сообщение от _Ivana Посмотреть сообщение
Подсказка - я угадаю этот этаж за 3 попытки.
По-моему, за менее чем ⌈log2(k+1)⌉ попыток узнать невозможно при любом количестве яиц...
0
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
01.01.2015, 19:36  [ТС] 9
Я вот тоже засомневался. Похоже, мой код меня подвел Сейчас попробую разобраться где он ошибается, выведу отладочную печать... (Это же на Си, там легко )

Добавлено через 50 минут
Исправил своего кота, теперь результаты больше похожи на правду. (Вчерашний новогодний вариант был сделан наспех необдуманно) При 4 яйцах и 10 этажах 4 попытки. Можно протестировать на других данных.

Добавлено через 7 минут
Цитата Сообщение от Somebody Посмотреть сообщение
Всегда можно обойтись и одним яйцом, но тогда всегда (в худшем случае) будет (k-1) попытка
Некоторое буквоедство - на всякий случай, чтобы не было недопониманий условия - будет k попыток. Ибо никто не гарантирует, что в доме существует этаж, упав с которого яйцо обязательно разобьется.
0
Catstail
01.01.2015, 19:38
  #10

Не по теме:

Цитата Сообщение от _Ivana Посмотреть сообщение
Ибо никто не гарантирует, что в доме существует этаж, упав с которого яйцо обязательно разобьется.
- если оно стальное, то безусловно!

0
_Ivana
01.01.2015, 19:39  [ТС]     Бросание яиц n яиц с балкона k-го этажа
  #11

Не по теме:

Если под бросанием яиц понимать испытания самолетов на прочность, то еще и титановые бывают вроде.

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.01.2015, 19:39

Запрос в access: среднее количество яиц
Есть таблица Курицы. В этой таблице есть поле Количество_яиц, Работник, Порода. Необходимо...

Самодельный инкубатор на 10000 яиц. Стоимость?
Здравствуйте. У меня родные занимаются фермерством. Встаёт вопрос, у них, о приобретении...

Перевод с С++ - определить, сколько было снесено яиц
Перевод С++ на Си #include <iostream> using namespace std; typedef struct { char...

Количество вариантов расположения количества V яиц по N корзинам
Есть общая корзина яиц, пускай их буте 1000 штук, примеме это за V. При транспортировке яйца решают...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru