Охранник находится в одноэтажном круглом здании, которое состоит из одинаковых комнат. Из каждой комнаты можно попасть в две соседние. Количество комнат неизвестно. В них охранник может только включать или выключать свет. Изначально свет горит произвольным образом. Как охраннику определить общее количество комнат в здании?
update
Ответ
Охранник включает свет в комнате, которую назовём начальной. Далее идёт в заранее выбранном направлении, например по часовой стрелке, и считает количество пройденных комнат. Как только ему встречается комната с включённым светом, он выключает в ней свет и возвращается к начальной комнате. Горящий в ней свет будет означать, что здание ещё не пройдено по кругу. Охранник повторяет действия - идёт по часовой стрелке до первой комнаты с включённым светом. Если после возвращения в начальной комнате свет выключен, то охранник обошёл здание по кругу и искомое количество комнат в здании будет равно подсчитанному количеству комнат на последнем шаге.
И ещё - головоломка про лабиринт.
Ну если речь об оптимальности не идет....:)
ОтветитьУдалитьДелаем в исходном месте комбинацию - например 6 подря выключенных комнаты. Бежим направо. Если встречаем комбинацию шесть подряд выключенных комнаты, меняем комбинацию и возвращаемся к исходным комнатам, если комбинация поменялась, как мы ее меняли - задача выполнена, охранник пробежал полный круг. Если нет - бежим снова в том же направлении что и первый раз. И так дальше пока вернувшись назад не обнаружим изменившуюся комбинацию.
дополнение - пока бежит ему еще нужно во всех комнатах свет включать, по пути, чтобы по пути назад не наткнуться на комбинацию, которую он изменил для опознания старта.
ОтветитьУдалитьВ общем-то комбинацию из шести комнат можно сократить до одной. И также к ней возвращаться и проверять изменилось ли положение.
Удалитьв принципе да - но комбинацию из одной он будет встречать очень часто... тут конечно от количества комнат зависит, хотя бы приблизительной оценки.
ОтветитьУдалитьС одной комнатой алгоритм становится универсальным, ведь общее количество комнат может быть и меньше 6.
УдалитьОхранник включает свет в комнате, в которой находится. Далее действует по алгоритму:
ОтветитьУдалить1. Идет по часовой стрелке до первой комнаты с включенным светом, считая комнаты.
2. При обнаружении комнаты с включенным светом, выключает его и возвращается к исходной.
3. Если свет в исходной еще горит, то он не обошел здание, продолжаем с п.1
4. Если свет выключен, все здание обойдено, и он подсчитал все комнаты.
Если подытожить, то схема действий должна быть именно такой.
УдалитьМне кажется, что самым простым способом будет снять с себя один ботинок или рубашку, оставить в первой комнате и, проходя по часовой стрелке, влючать свет в каждой из комнат (чтобы находить дверь :)). Там, где обнаружится ботинок, и будет конец отсчета. Про то, что нельзя ничего с себя снимать, ничего не сказанно в условиях.
ОтветитьУдалить