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

Сто этажное здание и 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 получены именно из этих рассуждений. Вернее, обоснованы ими. |
|
Сообщ.
#16
,
|
|
|
|
MIF, что то я не понял твою формулу k*(k + 1)/2 >= n не мог бы ты разъяснить? Например у нас n=100 этажей и k=3 шаров как тогда найти мин количество этажей?
|
|
Сообщ.
#17
,
|
|
|
|
Формула Мифа это другая запись моей (11 сообщение) формулы. Следует из того, что:
1 + 2 + 3 + ... + k Можно представить как сумму крайних элементов: 1 + k; 2 + (k - 1); 3 + (k - 2) 1 + k; 1 + k... которая повторяется k/2 раз. С тремя шарами посложнее будет... |
|
Сообщ.
#18
,
|
|
|
|
Теперь понятно, а то я думал это как раз ответ на общий вариант n этажей и k шаров. Я вот думаю в общем случае для k шаров можно делать примерно так : сначала найти разбиение на этажи как для 2 шаров, а потом в каждом промежутке не проходить по одному этажу как это было при одном оставшемся шаре, а использовать метод золотого сечения, либо до того момента как найдется нужный этаж, либо до того момента как останется один шар, и им уже пройти по-одному оставшиеся этажи. Логично ли что это и будет нужным алгоритмом или можно лучше?
|
|
Сообщ.
#19
,
|
|
|
|
С тремя шарами вроде двойная формула:
y=(x-1)Sy=0 (k=ySk=0 k) + 1>= 100 . Вроде 1 там нужна (?). Хотя формулы так и не пишут Получается х = 9. (9) -> (8) + 1 -> 36 + 1 (8) -> (7) + 1 -> 28 + 1 Кидаем: 37, 66, 88, 104 (100). Если на 37 разбивается: 8, 15, 21, 26, 30, 33, 35, 36. Если на 66 разбивается: 44, 50, 55, 59, 62, 64, 65. Добавлено Цитата int0x25 @ использовать метод золотого сечения Забудь ты про золотое сечение! Тут это не катит. От количества шаров будет зависеть количество вложенных сумм, по принципу: k - шаров, (k - 1) сумм. Осложняется еще все этой вылезшей вдруг единицей. |
|
Сообщ.
#20
,
|
|
|
|
_lcf_ спасибо за формулу и за подробное описание того, как она работает!
|