Re: Задача про тарелки. - Plus , 30.11.2004 22:21 MSK | ||
: : Есть здание высотой 90 этажей. И есть две одинаковые тарелки. При сбрасывании с определенного этажа тарелка бьется или не бьется. Нужно определить с какого этажа тарелки начинают биться. Самый простой способ сделать это - это начать с первого этажа и идти вверх бросая тарелку пока она не разобьется. Но таким методом в худшем случае мы будем вынуждены сделать 90 бросков (если тарелка очень прочная). Нужно придумать алгоритм бросания, чтобы гарантированно минимизировать число бросков за которые мы определим этаж с которого тарелки начинают биться. : Я попробую в общем виде. Две попытки - значит, разбив первую тарелку, нам придётся идти со второй по одному этажу. Пусть X - максимальное число попыток. Тогда первую тарелку мы кинем с этажа X, чтобы осталось как раз (X-1) попыток. Второй раз мы её кинем с этажа X+(X-1), так как одна попытка истрачена. Всего можно покрыть X*(X+1)/2 этажей. Решив это уравнение, мы получим число попыток. Для N=90: X=13. А именно: 13,25,36,46,55,63,70,76,81,85,88,90,91 Так что мы сможем проверить первый этаж, и даже крышу :) | ||
|