Теперь, когда мы знаем, что всех перестановок 24, можно начинать перечислять их. Систематический способ получения всего перечня таков: оставляя одну из букв на неизменном месте, систематически перемещаем оставшиеся три буквы, после чего повторяем процедуру для каждой из них. В нашем примере в результате такой стратегии получаем:
Обратите внимание, что первая буква (А) находится на постоянном месте во всех шести перечисленных перестановках, и изменение в порядке происходит в направлении <п правого конца перестановок к левому. Другими словами, < начала последние две буквы (В и Г) меняются местами, II лишь после этого мы позволяем себе изменить третью с конца букву. В результате имеем шесть перестановок с буквой А на первой позиции и по две перестановки с буквами Б, В и Г на второй позиции. Поскольку всего перестановок 24, то мы знаем, что в решении задачи прошли ровно четверть пути к окончательному ответу. Так как во всех перечисленных до сих пор перестановках буква А находилась на первом месте, можно предположить, что мы на верном пути, и теперь осталось лишь перечислить еще по шесть перестановок, где на первом месте поочередно будут стоять Б, В и Г.
Продолжение перечня перестановок будет выглядеть так:
А вот еще два упражнения на перестановки, которые вы можете попробовать решить самостоятельно: 1) LU, Н, К, Т и 2) 3, 5, 6, 9. Задание такое же: выписать все возможные перестановки, образуемые указанными наборами букв и чисел.
Одной из самых известных задач, решение которой требует строгого упорядочения шагов, является так называемая задача о миссионерах и людоедах, многие годы используемая и изучаемая психологами. Попробуйте решить ее. Формулируется она так:
На берегу реки находятся три миссионера и три людоеда. И миссионерам, и людоедам надо переправиться на другой берег. Для этой цели в их распоряжении маленькая лодка с веслами, вмещающая только двух человек. Однако существует одна проблема. Если число людоедов на любом из берегов превысит число миссионеров, находящихся на том же берегу, людоеды съедят миссионеров. Каким образом им всем перебраться на другой берег, но с тем непременным условием, что все останутся целы и невредимы?
Решение задачи о миссионерах и людоедах вы найдете в конце этой главы (рис. 3.9). В решении можно увидеть ряд моментов, заслуживающих внимания. Во-первых, задача может быть решена как минимум за одиннадцать шагов, включая первый и последний. Во-вторых, решение, по сути, является линейным. На всех, кроме двух, этапах всего пути решения единственная ошибка, которую может совершить решающий, заключается в том, что движение выполняется не в ту сторону. Иными словами, у вас есть только два варианта: вернуться на шаг назад, отменив предыдущий ход, или выполнить следующий шаг вперед. Из всех шагов ііишь два отличаются от остальных тем, что предполагают два варианта движения вперед, однако оба варианта ведут к правильному решению. Таким образом, и здесь единственной ошибкой будет возвращение на шаг назад. Отме-1им еще один момент — возможность выполнения недопустимого хода, т. е. такого, который противоречит условиям іадачи. Пример незаконного хода — когда в лодку садятся больше двух человек. Может показаться странным, каким образом у людей вообще могут возникать трудности с задачей такого рода при практически линейной структуре ее решения. Самые распространенные ошибки и трудности в решении этой и похожих задач, как показывают исследования, заключаются: а) в неумышленном совершении обратных ходов, б) в совершении недопустимых шагов, в) в непонимании, каким может быть следующий законный ход.
Если вы чувствуете себя готовыми к решению более серьезной разновидности задачи с миссионерами и людоедами, то попытайтесь решить ее снова, но на этот раз с пятью миссионерами и пятью людоедами. Как и прежде, задание состоит в том, чтобы переправить их всех через реку, причем в лодке на сей раз может поместиться не более трех человек. Прежним требованием остается не допускать ни на берегу, ни в лодке численного перевеса людоедов над миссионерами, так как миссионеры, оказавшиеся в меньшинстве, будут незамедлительно съедены.
Данная версия задачи значительно труднее предыдущей, поскольку решение более не является линейным. Попробуйте решить ее, прежде чем заглядывать в ответ (рис. 3.10), приведенный в конце главы. Как вы сами увидите, здесь гораздо больше допустимых шагов, но некоторые из них ведут в тупик.