MAIL2FUTURE.NET - Free Mail Delivery Service
MAIL2FUTURE.NET - Служба Доставки Злектронной Почты
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

Так что мы сможем проверить первый этаж,
и даже крышу :)

Тема:
Текст:
Автор:
Пароль: ( только для авторизации )