Стеклянные шарики

2 +1 -1
theasder Админ. спросил 2 года назад

У вас есть два одинаковых стеклянных шарика. Вы можете бросать их с любого этажа 100-этажного дома.
Вопрос: Какое наименьшее количество бросков понадобится, чтобы определить этаж, начиная с которого шарик разобьётся?

kolesnik ответил 2 года назад

Обычный бинарный поиск. Количество шагов: log(100) = 7 (округляем до большего).

immelnikoff ответил 2 года назад

Бинарный поиск тут не подходит!
http://hkar.ru/N67s

forketyfork ответил 7 месяцев назад

Решение автора правильное, но задача поставлена не совсем корректно. На вопрос «какое наименьшее количество бросков…» ответ простой — один бросок (при линейном поиске снизу вверх, если искомый этаж — первый).
Более корректная постановка вопроса — «найдите этаж за минимальное количество бросков». Т.е. задача в том, что в *худшем* случае ваш алгоритм должен давать *лучший* результат среди всех возможных алгоритмов.

Al Mol ответил 2 недели назад

Задача поставлена корректно. Ответ — один бросок. Остальное извращения, никому не нужных ботанов

11 ответ
2 +1 -1
theasder Админ. ответил 2 года назад

У нас есть возможность разбить два шарика. Тогда оптимальная процедура состоит в том, чтобы разделить все этажи на неравные интервалы, отличающиеся друг от друга на 1.
Первое шарик бросаем с 14 этажа, затем / если шарик не разбился / с 27-го, то есть, каждый раз уменьшаем интервал на 1
Интервалы между бросками первого шарика, если он не разбивается, таковы: 14, 13, 12, 11, 10, 9, 8 и т.д.
Если шарик разбивается, у нас есть возможность начиная с этажа, который на один выше последней удачной попытки, бросать второй шарик, каждый раз поднимаясь на один этаж, пока оно не разобьется. И в любом случае количество бросков не превысит 14.

sergosar ответил 2 года назад

Кажется приведено неправильное решение. тк делением на два и выбором наихудших вариантов задача сводится к 7ми ходам
50 этаж разбился — этажи 1-45 — не разбился 51- 100 , пусть разбился , далее 25 этаж и тп…

sergosar ответил 2 года назад

Кажется приведено неправильное решение. тк делением на два и выбором наихудших вариантов задача сводится к 7ми ходам
50 этаж разбился — этажи 1-45 — не разбился 51- 100 , пусть разбился , далее 25 этаж и тп…

kolesnik ответил 2 года назад

Обычный бинарный поиск. Количество шагов: log(100) = 7 (округляем до большего).

atri24 ответил 2 года назад

Чет не понял про бинарный поиск…
Кидаю с 25-го — разбился
кидаю с 12-го — разбился
и с какого тогда этажа?

eugene_babichenko ответил 2 года назад

При использовании бинарного поиска в худшем случае мы разбиваем шарик на середине и нам приходится вторым подряд проверять 50 этажей.

Pavel Tkalenko ответил 2 года назад

Решение в семь шагов возможно, при условии что у нас 7 шаров. Если у нас 2 шара разобьется, то и попыток больше не будет.
Решение с изменением интервала, считаю самым оптимальным.

0 +1 -1
eugene_babichenko ответил 2 года назад

Обычный бинарный поиск НЕ подходит, на эту задачу в принципе с трудом натягиваются стандартные алгоритмы. Решение может быть в том, чтобы проверять первый шарик с каким-то интервалом, к примеру, 10 этажей, и, возможно, этот интервал постепенно увеличивать. Как только шарик разбился, вторым проверяем весь пропущенный интервал снизу вверх. Вот здесь есть один из вариантов такого решения.

atri24 ответил 2 года назад

Согласен. И похоже, что 10 — это оптимально. И не надо интервал менять. Получается максимум 10 попыток.

atri24 ответил 2 года назад

а нет… поторопился 🙂

eugene_babichenko ответил 2 года назад

Чтобы решить, какой шаг оптимален, можно решить несложную задачку математической оптимизации, можно даже делать это для разного количества этажей. Тут попыток максимум 18 стабильно, но это явно лучше, чем 50. Получается O(n), а не O(lg n), но ничего лучше в голову не пришло пока. Да и с бинарным поиском по итогам не получается честного O(lg n), всё равно O(n) худший случай, потому что придётся пройти половину этажей.

0 +1 -1
Ivan Tsarinsky ответил 2 года назад

С помощью двух шариков определить точный этаж нельзя! С первого раза, бросив с 100-го этажа можно сказать разобьется он или нет, соответственно утверждать что 100-й этаж — этаж с которого шарики разбрасываться или нет!

0 +1 -1
immelnikoff ответил 2 года назад
0 +1 -1
Shuma ответил 2 года назад

Если бросать одновременно по два шарика — то нужно 5 бросков