Закрыть

Ханойские башни.

Автор: Васин Алексей
Опубликовано 08.02.2008 в 15:56
Раздел: Дискретная математика
Даны три стержня, нумерованны 1, 2 и 3 и набор из N дисков (N≥1) уменьшающегося диаметра с дыркой в центре. Сначала все N дисков насажены на стержень C1 в порядке уменьшения диаметра, т.е., самый большой диск внизу, самый маленький наверху первого стержня. Задача состоит в том, чтобы переместить эту башню с первого стержня на третий за некоторое число "ходов", где "ходом" является перемещение верхнего диска со стержня на верх другого стержня, с таким ограничением, что больший диск никогда не может быть помещен над меньшим. Второй стержень может использоваться как вспомогательное "хранилище" для дисков, которые находятся "в пути".

 

Итак, если мы можем решить эту игру для любых двух стержней при N = N0, мы можем также решить ее для N = N0 + 1. Назовем

movetower(m, A, B, C)

набор ходов, который перемещает башню из дисков со стержня A (если необходимо, через стержень B) на стержень C Отдельные ходы имеют форму

movedisk (P, Q)

Набор ходов

movetower(N0 + 1, A, B, C)

это то же самое, что и последовательные ходы

movetower(N0, A, B, C) movedisk (A, C) movetower(N0, B, A, C)

Словами: первая башня из N0 дисков перемещается с A в B, используя C как вспомогательный стержень, затем N0 + 1-ый диск перемещается непосредственно с A на C и наконец башня из N0 дисков, которая временно была помещена на стержень B, перемещается на свою конечную цель C, используя A как вспомогательный стержень. Поскольку башня состоит из N0 меньших дисков, присутствие больших дисков не приведет к нарушению условия уменьшения диаметра дисков. Перемещение башни из одного диска (N0 = 1) не составляет трудности, как результат, головоломка может быть решена. Поставленный перед нами вопрос, однако, состоит в составлении программы, генерирующей перемещения дисков, в том порядке, в каком они должны происходить.

 

Примечание. Нереалистично требовать выполнения этой программы для больших значений , поскольку общее число требуемых ходов = 2N - 1. Докажите это и докажите также, что головоломка не может быть решена меньшим числом ходов.

 

Тот факт, что ход с N > 1 разлагается на три "меньших" хода, предполагает, сто мы храним список ходов, которые должны быть сделаны. Если первый ход простой, мы делаем его, иначе мы заменяем его на его декомпозицию и пересматриваем заново. В обоих случаях, если мы имеем список из k ходов, только первый из тех, что должны быть сделаны, подлежит рассмотрению, и, пока мы обрабатываем его, остальные k - 1 ходов остаются неизменными нашими обязательствами. Это предполагает, что мы вводим

movek, movek-1, ... , move2, move1

которые должны быть сделаны в порядке уменьшения индекса, в порядке слева направо. Если movek простой, он делается, оставляя

movek'=k-1, ... , move2, move1

(показанное как , новое значение , длина списка оставшихся обязательств), иначе шаг movek заменяется тремя другими, что ведет к

movek'=k+2, movek'-1=k+1, movek'-2=k, movek'-3=k-1, ... , move2, move1

В обоих перемещениях нижний (т.е. последний) -й ход должен быть простым.

 

Ход задается четырьмя параметрами, скажем

n - число дисков в перемещаемой башне

from - номер исходного стержня

via - номер вспомогательного стержня

to - номер целевого стержня

 

Мы можем хранить эти ходы в четырех массивах "". (Проверьте, что список обязательств никогда не длиннее ходов.) Не простой ход (с ) задаваемый в табличной форме, как

$\begin{array}{rrrrr} & n= & from= & via= & to= \\ k & N & A & B & C \end{array}$

 

должен быть заменен тройкой

$\begin{array}{rr} & n'= & from'= & via'= & to'= \\ k'-2=k & N-1 & B & A & C \\ k'-1=k+1 & 1 & A & (B) & C \\ k'=k-2 & N-1 & A & C & B \\ \end{array}$

 

в которой верхняя строка заменяет исходную строку, я две другие строки - новые. (В средней строке элемент "via" взят в скобки, так как он несущественный; программа, приведенная ниже, оставляет это значение неизмененным.)

begin integer k; integer array n, from, to [1:2*N-1]; n[1]:= N; from[1]:= 1; via[1]:= 2; to[1]:= 3; k:=1; repeat if n[k] = 1 then begin movedisk(from[k], to[k]); k:= k + 1 end else begin n[k+2]:= n[k] - 1; from[k+2]:= from[k]; via[k+2]:= to[k]; to[k+2]:= via[k]; n[k+1]:= 1; from[k+1]:= from[k]; to[k+2]:= to[k]; n[k]:= n[k+2]; from[k]:= to[k+2]; via[k]:= from[k+2]; to[k]:= via[k+2]; k:= k + 2 end until k = 0 end

Замечание. В программе мы не описали подробно операцию "movedisk(A, B)". Если она печатает номера пары A, B, то будет отпечатано решение; если машина связана с механической рукой, которая на самом деле перемещает диски, то машина будет играть в игру!

 

Мы настоятельно рекомендуем читателю выполнить вышеприведенную программу самому с небольшим значением N (скажем, 4), чтобы увидеть, как значение k возрастает и убывает. Приглашаем также читателя внимательно проверить "шунтирование" значение N(-1), A, B и C, когда не простой ход разлагается на три более простых. Эта проверка является мучительным процессом, настолько мучительным, что всякий, кто ее проделал, будет только рад согласиться, что вышеприведенная программа до некоторой степени неприятная. Вышеприведенная программа включена сюда с целью сделать его более восприимчивым к элегантности, так называемого "рекурсивного решения", которое теперь последует.

begin procedure movetower (integer value m, A, B, C); begin if m = 1 then movedisk(A, C) else begin movetower(m-1, A, C, B); movedisk(A, C) movetower(m-1, B, A, C); end end movetower(N, 1, 2, 3); end

Здесь вводится оператор, названный "movetower" с четырьмя (целочисленными) параметрами, перемещающий башню длиной m с A через B на C. В терминах этого оператора конечная программа сворачивается в единственный оператор, который приведен в последней строке, а именно, "movetower(N, 1, 2, 3)". Все, что приведено перед ним, (строки со 2 по 8) описывает этот оператор в маленькой программе, маленькой потому, что оператору разрешено вызывать самому себя. Определение оператора (так называемое, "тело процедуры") в точности следует нашему исходному анализу игры. Рекурсивные процедуры - т.е., процедуры, которым разрешено вызывать самим себя - являются настолько мощным инструментом программирования, что дадим еще примеры их.

 

Замечание. Некоторые более старомодные языки программирования не обеспечивают рекурсию. Курсы программирования, базирующиеся на таких языках, часто содержат много примеров, которые трудны только потому, что студентам отказано в рекурсивном решении.

Комментарии (0)

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
Aрхив статей