Сто этажное здание и 2 мячика. Алгоритм нахождения этажа.
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [18.97.9.169] |
|
|
правила раздела Алгоритмы

| Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сто этажное здание и 2 мячика. Алгоритм нахождения этажа.
|
Сообщ.
#1
,
|
|
|
|
Здравствуйте, форумчане! По дескретной математике нам задали интересную задачу, может быть кто то уже сталкивался с ней или просто сможет дать ответ. Условие задачи следующее:
есть сто этажный дом и 2 мячика нужно найти алгоритм(с наименьшим количеством бросков) для поиска того этажа, с которго сброшенный мячик расколется. Пробовал найти алгоритм, но нашел тока тривиальный - сбрасывать через каждые 10 этажей. И в худшем случае(если окажется что этаж с которого надо сбросить - это 99) придется потратить 10+9=19 попыток. Но препод сказал что должно получиться 14. Подкиньте плиз идейку |
|
Сообщ.
#2
,
|
|
|
|
Ну раз 14 - наименьшее количество бросков, то надо поднятся на четырнадцать етажей и сбросить мяч, потом тодняться ешё на 13 етажей, потом ешё на 12 и .т.д.
|
|
Сообщ.
#3
,
|
|
|
|
Цитата int0x25 @ в худшем случае(если окажется что этаж с которого надо сбросить - это 99) придется потратить 10+9=19 попыток Считаете плохо... зачем с сотого-то пробовать? |
|
Сообщ.
#4
,
|
|
|
|
|
Сообщ.
#5
,
|
|
|
|
Бинарный поиск. Проверяем 50-й этаж, если разбился - 25-й, если не разбился - 75-й. И так далее.
|
|
Сообщ.
#6
,
|
|
|
|
Цитата Pacific @ Бинарный поиск. Проверяем 50-й этаж, если разбился - 25-й, если не разбился - 75-й. И так далее. А если с 50-го разбился, и с 25-го разбился, то дальше мы остались без мячиков |
|
Сообщ.
#7
,
|
|
|
|
Что-то я не понял условия
. Для того, чтобы опредилить ПРОИЗВОЛЬНЫЙ этаж, с которого разобъётся шарик - достаточно одной попытки. А именно залезть на сотый этаж и кинуть оттуда, если разобъется - ответ готов. Если нет - то у нас неразбиваемые шарики . Ведь вряд ли ж если после этого мы скинем, скажем, с 50 этажа - то шарик разобъётся.А если надо определить МИНИМАЛЬНЫЙ этаж - то надо примерно 50 попыток. Начинать кидать с 1 этажа, и продолжать через один. Так как, из условия получается, что у нас 2 попытки. Или может быть int0x25 ты что пропустил из условия, считая это маловажным |
|
Сообщ.
#8
,
|
|
|
|
Нет, задачка-то известная. Надо определить минимальный этаж. Но 50 попыток - это слишком. Правильный ответ - действительно 14.
|
|
Сообщ.
#9
,
|
|
|
|
Сначала кидаешь с 14 этажа, если не разбился-с 27. Дальше сам...
|
|
Сообщ.
#10
,
|
|
|
|
Задача может быть решена методом подбора. Покажу на примере.
Допустим, мы хотим проверить, хватит ли 16 бросков. Первым шагом считаем, что первый шарик сразу разобьется, и по 1 этажу придется искать вторым, потратив максимум 15 бросков. Следовательно первый бросок будет сделан с 16 этажа. Далее считаем что первый шарик разобьется на 2 броске, а вторым придется сделать 14 оставшихся бросков. Второй бросок тогда будет с 31 этажа (16+15)... и так далее... Алгоритмизируя, приходим к поиску такого наименьшего X, что сумма чисел от 1 до Х больше заданного количества этажей. Это 14, сумма равна 105. Первые броски производятся соответственно с 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 этажей. |
|
Сообщ.
#11
,
|
|
|
|
А зачем подбором? Можно и мат. последовательность считать:
k = xСуммаk = 1k >= 100. На интересует значение k. Получаем 14. |
|
Сообщ.
#12
,
|
|
|
|
Всем спасибо за помощь, особенно _lcf_ за конкретную формулу, а то я все таки догадался сегодня до 14,13,12... но не мог понять почему именно,начиная с 14, будет минимальное количество шагов. А как будет выглядеть формула в общем случае если n этажей и k шаров,причем о соотношении n и k ничего неизвестно,т.е. метод золотого сечения по-прежнему не применить?
|
|
Сообщ.
#13
,
|
|
|
|
Цитата int0x25 @ т.е. метод золотого сечения по-прежнему не применить? попыток мало. |
|
Сообщ.
#14
,
|
|
|
|
Цитата int0x25 @ n этажей и k шаров Минимальное k, удовлетворяюшее условию: k*(k + 1)/2 >= n |
|
Сообщ.
#15
,
|
|
|
|
Цитата _lcf_ @ А зачем подбором? Чтобы понять, как составить формулу. Не зря я именно после подбора перешел к алгоритмизации, а не сразу. Твоя формула и формула MIF получены именно из этих рассуждений. Вернее, обоснованы ими. |