Re: Тут я открываю алгоритм - не читать! (но ставлю вопрос об оптимальности вари


Автор сообщения: gorm
Дата и время сообщения: 22 October 2004 at 18:05:39:

В ответ на сообщение: Тут я открываю алгоритм - не читать! (но ставлю вопрос об оптимальности варианто

Мне кажется, что стратегию слегка можно улучшить в любом случае достаточно просто.

a) Первый, как обычно, оставляет выключенную лампочку. Если он попадает в карцер и на второй день, то продолжает тянуть лямку водилы, оставляя лампочку выключенной. Если же на второй день попадает другой (а первый, соответственно, не попадает) то водилой становится второй, оставляя выключенной лампочку и отмечая, для себя, что двое уже побывали, а первый слагает с себя все права и обязанности.

б) Попробуем двигаться дальше в этом же направлении. Пусть теперь второй, опять-таки, взяв на себя лямку, не оставляет лампочку, а включает ее.
Возможны два варианта:
1. на третий день приходит он же, тогда продолжает быть водилой и выключает лампочку.
2. на третий день приходит другой, и, видя включенную лампочку, перехватывает функции водилы, отмечая для себя, что уже прошло трое. Второй, слагает с себя все функции (он ведь знает, что его на третий день не посадили в карцер) и ответственность. Третий может оказаться тем же, что и первый, это ничего не меняет, он только будет считать, что прошло не 3, а 2 и опять становится водилой.

Эта стратегия вроде бы является оптимальной для n=1, 2 и 3. Можно ли продвинуться дальше в передаче полномочий? Является ли стратегия оптимальной для n=4?


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