Re: продвинуться до K+1


Автор сообщения: Michael
Дата и время сообщения: 24 October 2004 at 13:03:39:

В ответ на сообщение: Re: продвинуться до K+1

> Надеюсь, я нигде не ошибся (немного смущает, что новый алгоритм работает хуже при N=4,5)

Этого не может быть. Для N=4 алгоритм идентичен.

По-моему, есть один момент, который не был учтён. Но это моя вина - я плохо подчеркнул, что в худшем случае водилой будет тот, кто сидит в третий день. То есть, от первого до третьего дня у нас идёт старый алгоритм, от 4 до k идёт передача полнолочий водилы (до первого сбоя), и с k+1 идёт подсчёт оставшихся. К сожалению, мой первый мэйл сбился и потерял часть текста.

Но в главном Вы правы - этот алгоритм очевидно будет давать улучшение именно для больших N. Ведь чем N больше, тем больше вероятность, что k первых будут разными людьми, и тем больше выигрыш на каждого подсчитанного экспресс-методом разбойника.


1811. Mihael'ю еще одна задачка! - Заметил-Просто 11:14 21.10.04 (61)
К списку тем на странице