Переправы.
Как и задачи на поиск фальшивой монеты с помощью взвешиваний, задачи на переправы являются алгоритмическими задачами. То есть в качестве решения нужно предоставить алгоритм или порядок действий, необходимый для достижения цели.
В этих задачах обычно требуется придумать алгоритм переправки людей, животных, грузов через реку или тоннель с соблюдением некоторых условий. Проблема заключается в том, что средство передвижения не вмещает всех пассажиров или все грузы одновременно, а оставлять некоторых пассажиров или некоторые грузы одних без присмотра нельзя по каким-либо причинам.
Самой известной задачей на переправы является задача про волка, козу и капусту. На её примере мы разберем решение и запись подобных задач.
Задача.
Мужику нужно перевезти через реку волка, козу и капусту. Лодка двухместная, в ней может поместиться только мужик и еще что-то одно: волк, коза или капуста. Грести может только мужик. Если оставить волка с козой без присмотра, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как мужику перевезти свой груз?
Решение.
Решение этой задачи может быть записано разными способами. Рассмотрим некоторые из них.
Текстовая запись решения.
Если первым переправлять через реку волка, то оставленная без присмотра коза съест капусту. Если первую переправлять капусту, то оставленный без присмотра волк съест козу.
Значит, сначала мужик должен переправить на другой берег козу, высадить ее там и вернуться обратно.
Затем взять, например, капусту и отвезти её на другой берег. На другом берегу выложить капусту, посадить в лодку козу и вернуться обратно.
Затем на этом берегу высадить козу, взять волка и отвезти его на другой берег. Высадить там волка и вернуться обратно.
Затем на этом берегу забрать козу и отвезти её на другой берег.
Таким образом, мужик переправит весь свой груз.
Решение в виде рисунка.
Чтобы не писать длинные тексты, в которых можно запутаться, можно нарисовать рисунок:
Решение в виде таблицы.
На рисунок, возможно, времени уйдет больше, чем на написание текстового решения.
Поэтому лучше придумать какую-нибудь понятную и простую схему записи решения.
Для более краткой записи введём обозначения. Обозначим мужика, волка, козу и капусту буквами М, В, К и к соответственно. Лодку обозначим чертой.
Наиболее наглядным и в то же время простым способом записи решения задачи является таблица:
Здесь на каждом шаге (ходу) видно, где находятся персонажи задачи и куда плывёт лодка.
Кроме того, при такой записи решения легко отследить зацикливание, то есть повторение ситуации, которая уже была. Поскольку при зацикливании мы возвращаемся к ситуации, которая уже была, это означает, что мы сделали несколько бесполезных ходов. Зацикливаний при решении задач следует избегать и делать только те ходы, которые действительно приведут к решению.
Очень краткая запись решения.
Обозначим мужика, волка, козу и капусту буквами М, В, К и к соответственно.
Знаком > обозначим переправу с исходного берега на другой, знаком < обозначим переправу в обратном направлении.
Решение задачи можно записать так (записываем только тех, кто переправляется через реку):
МК>, М<, Мк>, МК<, МВ>, М<, МК>.
Или, чтобы не путаться со знаками <>, можно писать так:
МК туда, М обратно, Мк туда, МК обратно, МВ туда, М обратно, МК туда.
Недостаток этого способа записи заключается в том, что нет наглядного представления, кто на каком берегу находится на данном шаге, поэтому сложнее отследить зацикливание.
Тем не менее, эта запись — тоже решение задачи.
Ответ: смотрите любое из решений выше.
Рекомендация по записи решений к задачам.
Формат наших занятий предполагает прием ответов только в виде чисел или в виде текста. К сожалению, рисунки и таблицы принять в качестве решения мы не можем.
Поэтому мы рекомендуем сначала решить каждую задачу на черновике наиболее наглядным способом (рисунок или таблица). Затем, на основе этого решения, аккуратно составить очень краткое решение (как в рассмотренной задаче) и ввести его в поле ответа. Либо указать полное текстовое решение.