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


Автор сообщения: Заметил-Просто
Дата и время сообщения: 22 October 2004 at 16:57:57:

В ответ на сообщение: Re: N бандитов

Я думаю, что времени было достаточно, а хочется обсудить оптимальность.

Алгоритм, который я прислал Горму следующий

Тот кто садится в карцер в первый день объявляется водилой, он и будет сообщать ответ, все остальные - неводилами. Водила в первый день после себя оставляет лампочку выключенной. Начинается игра.

Игра такова. Каждый неводила попадая в карцер смотрит на лампочку. Если лампочка включена, то ничего не делает. Если выключена, то включает лампочку и становится выбывшим из игры.

Выбывшие из игры попадая в карцер ничего не делают вне зависимости от состояния лампочки.

Водила попадая в карцер смотрит на лампочку. Если выключена, то ничего не делает, если включена - выключает. После того как он выключит лампочку n-1 раз требует всех освободить!


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

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

Остальных бандитов делим на "четных" и "третьего" :)) !!

"Четными" будем называть бандитов, которые в первый свой приход в карцер найдут лампочку погашенной. Их задачей будет в первый приход включить лампочку, а в следующие приходы, если таковые будут, ничего не делать.

"Третьим" будем называть бандита, который в первый свой приход в карцер увидит лампочку включенной. Его задачей будет выключить лампочку в свой первый приход, а в следующие приходы ничего не делать.

Игра заканчивается когда:

Первый, после первого дня, который он в карцере не проведет, он увидит лампочку сначала включенной, а потом выключенной.

либо

Второй, когда увидит лампочку сначала выключенной, а потом включенной (естественно первое его попадание не в счет)

Либо

Третий, когда после того как выключит лампочку в свои следующие приходы увидит лампочку снова включенной.

Четвертый после того как вернется из карцера в свою камеру снова в карцер попасть не успеет :).

Вроде как такая стратегия для четырех оптимальнее первой, но вот как считать оптимальность и как все это распространить на N > 4 я пока ответить не готов :)



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