Для любителей нестандартных задачек. Есть здание в сто этажей и два стеклянных шара. Эти шары абсолютно одинаковые и могут разбиться, если их бросить с определенной высоты. Экспериментатор может бросать шары с любого из этажей вниз. Вопрос: за какое минимальное число бросаний экспериментатор определит, при бросании с какого этажа шары разбиваются? Разумеется, что осколки разбитого шара бросать не имеет смысла. Например, с одним шаром он может бросить его с первого этажа, потом со второго, и т.д., т.е. надо 100 бросаний.
вроде (n+2)/2 т.е. сначала бросаем со 2-го этажа, Возможно 2 варианта: 1) разбился -> тогда бросаем с первого 2) не разбился. -> тогда бросаем с 4-го. Если с 4-го разбился, то бросаем с 3-го (для контроля) Если не разбился - идем на 6-ой и т.д. итого получаем что если шар разобется на n ом этаже, то надо сделать (n+2)/2 попытку. Оговорюсь: надо рассмотреть верхний предел, но сейчас мозги туго будут сображать
Teacher, а можно и так: шаг избрать не 2 а Х, тогда получается: бросаем с этажа Х*K, где 1 <= K <= (100/X), K - целое. если разбился, то второй шар бросаем поочередно с этажей X*(K-1) + I, 1 <= I < X? пока не разобьется. в самом худшем случае надо сделать (X+100/X) бросков. теперь берем производную, находим минимум. ответ готов. ПС. мог напутать с +-1.
Бросить шар с середины здания, допустим, с 50 этажа. Если разбился, то тогда начинать с первого этажа, и бросать до тех пор, пока не разобъется. Если не разбился, то подняться на 75-ый, и бросить оттуда. Если не разбился, то оставшееся расстояние опять поделить на 2, и вычислить сегмент. Если разбился, то пройти снизу оставшийся сегмент.
Ivan, в твоем случае понадобится 50 попытка (если шарик разбивается при броске с 49 этажа). в моем решении Х=10, следовательно количество попыток равно 20.
Ivan, а если кинешь с 50 разобьется и кинешь с 25 тоже разобьется... что дальше делать шаров то 2 всего... В случае с двумя шарами 100-этажное здание можно гарантированно промерить за 14 бросков. Делается это так: первый шар сбрасывается с 14-ого этажа, далее, если не разбивается, с этажа номер 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100. Определенный таким образом промежуток, в котором разбивается шар, последовательно промеряется вторым шаром. Иначе говоря, вначале мы зондируем здание первым шаром с шагом, уменьшающимся на единицу, начиная с 14. То есть номер этажа для сбрасывания определяется последовательным суммированием 14 + 13 + 12 + 11 + ... Каждый бросок первым шаром отнимает у нас один ход, потому следует уменьшать на один и количество этажей для промера вторым шаром. В итоге сумма бросков первым и вторым шаром не превысит 14 и мы точно определим искомый этаж. За N бросков таким способом можно гарантированно промерить N + (N-1) + ... + 3 + 2 + 1 = N*(N+1)/2 этажей. При N=13 это 91 этаж, а при N=14 уже 105
Arturvn, хитро "... потому следует уменьшать на один и количество этажей для промера вторым шаром ..." об этом я не подумал.