Математические задачи - Алгоритмы
- Задаю тебе последнюю задачу, - сказала принцесса Иванушке, - найди единственно верный путь из этой комнаты в наш зимний сад и сорви для меня самую красивую розу. Из этой комнаты ты пройдешь через левую, или правую, или среднюю дверь во вторую комнату; такие же три вида дверей будут перед тобой при переходе из второй комнаты в третью и из третей - в сад. Учти мои советы, - продолжала принцесса, - первый: из этого зала пройди через правую дверь; второй: из второй комнаты - не через правую дверь, и третий совет: из третей - не через левую дверь. Иванушка знал, что обычно из трех советов принцессы ровно в двух указывают ложное направление, кроме того, служанка принцессы успела шепнуть ему, что надо пройти через дверь каждого вида по одному разу. Как и полагается сказке, принес Иванушка розу и был вознагражден. Какой же маршрут оказался верным?
Ответ:
Рассмотрим все возможные маршруты. Т.к. на выбранном пути не должно встречаться одинаково расположенных дверей, то маршрутов всего шесть. Обозначим каждый из маршрутов записью вида Л П С, которая означает, что сначала идем в левую дверь, потом в правую, затем - в среднюю. И для каждой двери отметим, удовлетворяет ли она советам принцессы. Ставим плюс, если да, и минус, если выбранная дверь противоречит совету принцессы.
Л П С - - +
Л С П - + +
П Л С + + +
П С Л + + -
С П Л - - -
С Л П - + +
Т.к. нам известно, что два из трех советов были ложными, то правильным будет маршрут, имеющий два минуса и один плюс, т.е. Л П С