Главное меню

Задача. Как определить минимальное количество сбрасываний шаров, если?

Автор Nder, Март 14, 2024, 21:22

« назад - далее »

Nder

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

YuraU

По моим подсчетам достаточно 14 сбрасываний. При чем надо действовать по следующему алгоритму: первый бросок с 10 этажа, затем с 23, 35, 46, 56, 65, 73, 80, 86, 91, 95, 98, 100 до разбития первого шара, а затем в найденном интервале добираем с шагом 1 вторым шаром
например 22 этаж => броски с 10, 23х, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22х = 14 бросков
                                                                              

Siny

Для этого нужно будет потратить довольно много времени. Давайте сбросим один шар, до момента пока он не разобьется. Начнем допустим с 14 этажа,если допустить в качестве примера что шар разбился на 65 этаже, то вторым проверим интервал с 60 по 65 этаж. Как бы мы не проверяли, то меньше чем за 14 шаров, нам с этой задачей никак не справится.

Taggeli

Метод последовательных интервалов:
1) 100 делим пополам по количеству шаров на 50. Варианты:
1_1) 1-й шар разбился. Для второго осталось 49 вариантов до 49-го этажа. Итог 50 вариантов. 1 + 49 = 50. Много.
1_2) 1-й шар не разбился. Для второго осталось 49 вариантов до 99-го этажа. Итог 50 вариантов. 1 + 49 = 50. Много. с 100-го этажа по логике не нужно сбрасывать. Шар должен разбиться гарантировано по условию.
2) 50 делим пополам по количеству шаров на 25. Варианты:
2_1) 1-й шар разбился. Для второго осталось 24 варианта до 24-го этажа.   
3) 25 делим пополам по количеству шаров на 13 (один не достаёт). 13*8 = 104. Нет поделю на 12. 12*8 = 96 (3 до 99 не хватает). Варианты:
3_1) 1-й шар разбился на 96-м этаже. Для второго осталось 9 + 99 - 96 = 11 вариантов.
3_2) 1-й шар разбился на 84 этаже. Для второго осталось 8 + 10 = 18 вариантов:
12, 24, 36, 48, 60, 72, 84, (2-й шар)73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83. разбился 2-й шар.
Я поняла! Здесь должна быть обратная арифметическая прогрессия. от 100 отнимаем 2, 3, 4, 5 и т.д. получится:
98, 95, 91, 86, 80, 73, 61, 52, 42, 31. Затем 23, 10. Всего 12 интервалов. Максимум 14 вариантов.
Но я начну сначала.

Udelar

Алгоритм:1)сбрасываем с 50 этажа-2 варианта-разбился или нет-разбился, идем на 25 этаж-не разбился ,на 75   2)бросаем с 25 или 75 этажа-разбился-идём на 12 или 62 этаж/-не разбился-на 37 или 87 этаж...И так далее.То есть мы каждый раз по результату располовиниваем участок.Пример-50,25,12,6,3,1.Всего чтоб гарантированно найти этот этаж нужно 6 попыток.