понедельник, 14 апреля 2014 г.

Круглое здание

Круглое здание
Охранник находится в одноэтажном круглом здании, которое состоит из одинаковых комнат. Из каждой комнаты можно попасть в две соседние. Количество комнат неизвестно. В них охранник может только включать или выключать свет. Изначально свет горит произвольным образом. Как охраннику определить общее количество комнат в здании?

update
Ответ
Охранник включает свет в комнате, которую назовём начальной. Далее идёт в заранее выбранном направлении, например по часовой стрелке, и считает количество пройденных комнат. Как только ему встречается комната с включённым светом, он выключает в ней свет и возвращается к начальной комнате. Горящий в ней свет будет означать, что здание ещё не пройдено по кругу. Охранник повторяет действия - идёт по часовой стрелке до первой комнаты с включённым светом. Если после возвращения в начальной комнате свет выключен, то охранник обошёл здание по кругу и искомое количество комнат в здании будет равно подсчитанному количеству комнат на последнем шаге.

И ещё - головоломка про лабиринт.

7 комментариев:

  1. Ну если речь об оптимальности не идет....:)
    Делаем в исходном месте комбинацию - например 6 подря выключенных комнаты. Бежим направо. Если встречаем комбинацию шесть подряд выключенных комнаты, меняем комбинацию и возвращаемся к исходным комнатам, если комбинация поменялась, как мы ее меняли - задача выполнена, охранник пробежал полный круг. Если нет - бежим снова в том же направлении что и первый раз. И так дальше пока вернувшись назад не обнаружим изменившуюся комбинацию.

    ОтветитьУдалить
  2. дополнение - пока бежит ему еще нужно во всех комнатах свет включать, по пути, чтобы по пути назад не наткнуться на комбинацию, которую он изменил для опознания старта.

    ОтветитьУдалить
    Ответы
    1. В общем-то комбинацию из шести комнат можно сократить до одной. И также к ней возвращаться и проверять изменилось ли положение.

      Удалить
  3. в принципе да - но комбинацию из одной он будет встречать очень часто... тут конечно от количества комнат зависит, хотя бы приблизительной оценки.

    ОтветитьУдалить
    Ответы
    1. С одной комнатой алгоритм становится универсальным, ведь общее количество комнат может быть и меньше 6.

      Удалить
  4. Охранник включает свет в комнате, в которой находится. Далее действует по алгоритму:
    1. Идет по часовой стрелке до первой комнаты с включенным светом, считая комнаты.
    2. При обнаружении комнаты с включенным светом, выключает его и возвращается к исходной.
    3. Если свет в исходной еще горит, то он не обошел здание, продолжаем с п.1
    4. Если свет выключен, все здание обойдено, и он подсчитал все комнаты.

    ОтветитьУдалить
    Ответы
    1. Если подытожить, то схема действий должна быть именно такой.

      Удалить