Ханойская башня

Исходное положение пирамидки:

1. Перенеси малый диск с исходного стержня на промежуточный.

2. Перенеси большой диск с исходного стержня на конечный.

3. Перенеси малый диск с промежуточного стержня на конечный. Конечное положение пирамидки.

Чтобы запись алгоритма сделать короче, обозначим ходы тремя числами: первое число означает количество перекладываемых дисков, второе – номер стержня, с которого диск снимается, третье – номер стержня, на который диск надевается.

Короткая формализованная запись алгоритма1 перекладывания двух дисков с первого стержня на третий: 1, 1 – 2; 1, 1 – 3; 1, 2 – 3.

В. Рассмотрим алгоритм2перекладывания трех дисков со стержня 1 на стержень 2.

Словесное описание алгоритма2 с графической иллюстрацией ходов

Исходное положение пирамидки:

1. Перенеси два верхних диска с исходного стержня на промежуточный.

2. Перенеси нижний диск с исходного стержня на конечный.

3. Перенеси два диска с промежуточного стержня на конечный. Конечное положение пирамидки.

Короткая формализованная запись алгоритма2 перекладывания трех дисков с первого стержня на второй: 2, 1 – 3; 1, 1 – 2; 2, 3 – 2.

Алгоритм1 перекладывания двух дисков с одного стержня на другой известен, детализируем алгоритм2 перекладывания трех дисков с первого стержня на второй: 1, 1 – 2; 1, 1 – 3; 1, 2 – 3; 1, 1 – 2; 1, 3 – 1; 1, 3 – 2; 1, 1 – 2.

Зная алгоритм переноса трех дисков, легко написать алгоритм переноса четырех дисков и т.д.

С. Алгоритм перекладывания дисков с одного стержня на другой можно обобщить для произвольного n.

Назовем Hanoi(n,A,B) процедуру переноса пирамидки из n дисков со стержня A на стержень B.

Алгоритм3переноса n дисков со стержня A на стержень B имеет вид:

1. Hanoi (n-1,A,C).

2. Перенеси 1 диск со стержня A на стержень B.

3. Hanoi (n-1,C,B).

Этот способ описания алгоритма3 позволяет получить изящную рекурсивную программу (смотрите программу на стр. 127).

D. Определим количество перекладываний при перемещении пирамидки из n дисков со стержня A на стержень B

Таблица количества ходов при игре в Ханойскую башню

Подсчитать количество перекладываний дисков можно двумя способами.

k_n и k'_n – n-ые члены соответственно первой и второй последовательностей.

E. Распишем перекладывание четырех дисков со стержня A на B, используя в качестве вспомогательного диск C, используем алгоритм3.

Таблица шагов алгоритма3 перенесения n дисков(n=4)
со стержня A на стержень B, используя промежуточный стержень C

F. Построим блок-схему и напишем программуперекладывания n дисков со стержня A на стержень B, не используя рекурсию.

Необходимо совершить 2ⁿ-1 шагов и на каждом шаге расписать, с какого стержня, на какой стержень нужно переложить верхний диск. Будем расписывать перекладывания в таблице по столбцам.

Таблица разложения на шаги перекладывания n дисков
со стержня A на стержень B

Блок-схема основного Блок-схема вспомогательного

алгоритма игры «Ханойская башня» алгоритма Decompose

Для решения задачи возьмем 3 массива. Массив T, где T(i) – количество перекладываемых дисков в позиции i; i – номер строки таблицы; D(i) – указывают исходный стержень для перекладывания T(i) дисков в i строке; A(i) – конечный (целевой) стержень для строки i. Если T(i) = 0, то строка i еще не расписана. Если T(i)=1, то задан перенос диска со стержня, указанного D(i), на стержень, указанный A(i). Если T(i)>1, то задана операция Hanoi(T(i),D(i),A(i)), которая должна быть разложена на элементарные операции. Первоначально массив T(i) заполняется нулями. Разложение осуществляется то тех пор, пока все T(i) не получат значение 1.

Программа на языке QBasic игры Ханойская башня
(без использования рекурсии)[16]

DECLARE SUB Decompose ()

DIM SHARED r AS INTEGER, s AS INTEGER, n AS INTEGER, k AS INTEGER

DIM SHARED i AS INTEGER, h AS INTEGER, fl AS INTEGER

INPUT "Введите количество перекладываемых дисков"; n

k = 2 ^ n - 1

DIM SHARED t(1 TO k) AS INTEGER, d(1 TO k) AS INTEGER

DIM SHARED a(1 TO k) AS INTEGER

INPUT "С какого стержня переложить (1, 2, 3)"; r

INPUT "На какой стержень переложить (1, 2, 3)"; s

FOR i = 1 TO k

t(i) = 0

NEXT i

h = 2 ^ (n - 1) 'Начальная установка: n дисков перенести со стержня r (d(h))

t(h) = n : d(h) = r : a(h) = s 'на стержень s (a(h))

DO

fl = 1

FOR i = 1 TO k

IF t(i) = 0 THEN

fl = 0

ELSEIF t(i) > 1 THEN

Decompose

END IF

NEXT i

LOOP UNTIL fl = 1

FOR i = 1 TO k 'Распечатка результата исполнения программы

IF n <= 4 THEN

PRINT USING "#####"; t(i); d(i); a(i)

ELSE

PRINT USING "#####"; t(i); d(i); a(i);

PRINT " ***";

END IF

NEXT i

END

SUB Decompose 'Разложение переноса t(i) дисков со стержня d(i) на a(i)

DIM q AS INTEGER, j AS INTEGER

'Разложение переноса m дисков со стержня r на стержень s на три переноса

'1) m-1 диск со стержня r на стержень 6-r-s

'2) 1 диск со стержня r на s

'3) m-1 диск со стерня 6-r-s на стержень s

r = d(i): s = a(i)

IF t(i) = 2 THEN

t(i - 1) = 1 : d(i - 1) = d(i) : a(i - 1) = 6 - r - s : t(i) = 1

t(i + 1) = 1 : d(i + 1) = a(i - 1) : a(i + 1) = a(i)

ELSE

q = t(i) : j = i - 2 ^ (q - 2) : t(j) = q - 1 : d(j) = r : a(j) = 6 - r - s

j = i + 2 ^ (q - 2) : t(j) = q - 1 : d(j) = 6 - r - s : a(j) = s : t(i) = 1

END IF

END SUB

Программа на языке Turbo Pascal игры Ханойская башня
(без использования рекурсии)

Program Hanoi; {Ханойская башня, программа без использования рекурсии}

Const n1=10; k1=1023;

Var

r, s: 1..3; n: 0..n1;

k, i, h: 1..k1;

fl: boolean;

t: array[1..k1] of 0..n1;

d,a: array[1..k1] of 1..3;

Function Step(x,y:integer):integer;

Var o,v:integer;

Begin

v:=1;

for o:=1 to y do

v:=v*x;

Step:=v

end;

Procedure Decompose; {Разложение переноса t[i] дисков со стержня d[i] на a[i]}

Var

q:0..n1;

j:1..k1;

Begin

{Разложение переноса m дисков со стержня r на стержень s на три переноса

1) m-1 диск со стержня r на стержень 6-r-s

2) 1 диск со стержня r на s

3) m-1 диск со стерня 6-r-s на стержень s}

r:=d[i]; s:=a[i];

If t[i]=2 then

begin

t[i-1]:=1; d[i-1]:=d[i]; a[i-1]:=6-r-s; t[i]:=1; t[i+1]:=1; d[i+1]:=a[i-1]; a[i+1]:=a[i]

end

else

begin

q:=t[i]; j:=i-Step(2,q-2); t[j]:=q-1; d[j]:=r; a[j]:=6-r-s; j:=i+Step(2,q-2);

t[j]:=q-1; d[j]:=6-r-s; a[j]:=s; t[i]:=1;

end

end;

BEGIN

Write('Введите количество перекладываемых дисков');

Readln(n);

k:=Step(2,n)-1;

Write('С какого стержня переложить (1, 2, 3)');

Readln(r);

Write('На какой стержень переложить (1, 2, 3)');

Readln(s);

For i:=1 to k do

t[i]:=0;

h:=Step(2,n-1); {Начальная установка: n дисков перенести со стержня r (d[h])}

t[h]:=n; d[h]:=r; a[h]:=s; {на стержень s (a[h])}

Repeat

fl:=true;

For i:=1 to k do

If t[i]=0 then

fl:=false

else

If t[i]>1 then Decompose

Until fl;

For i:=1 to k do {Распечатка результата исполнения программы}

If n<=4 then

Writeln(t[i]:4, d[i]:4, a[i]:4)

else

Write(t[i]:4, d[i]:4, a[i]:4, ' ***')

END.

Программа на языке Turbo Pascal игры Ханойская башня
(с использованием рекурсии)

Program B_Hanoi; {Ханойская башня, программа с использованием рекурсии}

Uses crt;

Var a,b,c,n:integer;

Procedure Hanoi(i:integer;s,d,e:integer);

Begin

If i=1 then

Writeln(' ',s,'-',d)

else

begin

Hanoi(i-1,s,e,d); Hanoi(1,s,d,e); Hanoi(i-1,e,d,s);

end;

End;

Begin

Write ('введите кол-во дисков n='); Readln(n);

Writeln ('укажите начальный, конечный и промежуточный стержни:');

Readln(a); Readln(b); Readln(c); Hanoi(n,a,b,c);

End.

3.3 Игра «Жизнь»

Игра «Жизнь», придумана американским математиком Джоном Хортоном Конуэя (Конвея), сотрудником Кембриджского университета [6]. Описание игры появилось в октябрьском номере журнала «Scientific American» в 1970 году[17]. Возникающие в процессе игры ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели колонии живых организмов. По этой причине «Жизнь» можно отнести к быстро развивающейся в наши дни категории игр, имитирующих процессы, происходящие в живой природе. Эта игра необычна и красива.

Пусть «Жизнь» – многоклеточное сообщество, населяющее пустыни Флатландии. Для определенности предположим, что пустыня – прямоугольное поле, разделенное на квадратные клетки, каждая из которых может содержать организм – один элемент «жизни». Организмы умирают, рождаются, меняются поколения. Основная идея игры состоит в том, чтобы, начав с какого-нибудь простого расположения «организмов», находящихся по одному в клетке, проследить за эволюцией исходной конфигурации под действием «генетических законов» Конуэя, которые управляют рождением, гибелью, выживанием организмов.

A. Условия, которым должны удовлетворять правила игры «Жизнь». Конуэй тщательно подбирал свои правила и долго проверял их «на практике» добиваясь, чтобы они, по возможности, удовлетворяли трем условиям:

1. Не должно быть ни одной исходной конфигурации, для которой существовало бы простое доказательство возможности неограниченного роста популяции.

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

3. Должны существовать простые начальные конфигурации, которые в течении значительного промежутка времени растут, претерпевают разнообразные изменения и заканчивают свою эволюцию одним из следующих трех способов:

а) полностью исчезают (либо из-за перенаселенности, то есть от слишком большой плотности организмов, либо из-за разреженности, то есть от одиночества организмов, образующих конфигурацию);

б) переходят в устойчивую конфигурацию и перестают изменяться вообще;

в) выходят на колебательный режим, то есть – бесконечный цикл превращений с определенным периодом.

Короче, правила должны быть такими, чтобы поведение популяции было непредсказуемым.

B. Правила игры «Жизнь». Каждую клетку окружают 8 соседних клеток (клетка имеет 8 соседей), 4 соседние клетки имеют с ней общие стороны и 4 общие вершины (клетки, расположенные рядом с ней по горизонтали, вертикали и диагоналям).

Новое поколение организмов получается из предыдущего по простым правилам:

1. Выживание.Каждый организм, имеющий 2 или 3 соседних организма выживает и переходит в следующее поколение.

2. Гибель. Каждый организм, у которого больше 3 соседей, погибает из-за перенаселения. Каждый организм, вокруг которого свободны все соседние клетки или же занята одна клетка, погибает от одиночества.

3. Рождение. Если рядом с пустой клеткой оказывается ровно 3 клетки, в которых есть жизнь (организмы), то в ней рождается новый организм.

Важно понять, что гибель и рождение всех «организмов» происходит одновременно. Вместе взятые, они образуют одно поколение или, как мы будем говорить, один «ход» в эволюции начальной конфигурации.

Поскольку рождение и гибель «организмов» происходит одновременно, новорожденные «организмы» никак не влияют на гибель и рождение остальных организмов и поэтому, проверяя новую конфигурацию, необходимо уметь отличать их от организмов, перешедших из предыдущего поколения.

C.Некоторые варианты моделирования игры. Можно изображать ходы фишками двух цветов, можно рисовать ходы на бумаге либо переставлять фишки или шашки на доске. Начав игру, Вы сразу заметите, что популяция непрерывно претерпевает необычные, нередко очень красивые и всегда неожиданные изменения.

D.Возможные эволюции исходной конфигурации колонии организмов. В большинстве случаев исходные конфигурации либо переходят в устойчивые (их Конуэй назвал «любителями спокойной жизни») и перестают изменяться, либо навсегда переходят в колебательный режим, либо исчезают. Конфигурации, не обладавшие в начале игры симметрией, обнаруживают тенденцию к переходу в симметричные формы. Обретенные свойства симметрии в процессе дальнейшей эволюции не утрачиваются, симметрия конфигурации может лишь обогащаться.

E.Алгоритм получения конфигураций колонии организмов в игре «Жизнь».

Алгоритм одного хода игры. Попробуем составить алгоритм одного «хода» игры, т.е. получения новой конфигурации из старой. Первоначально алгоритм можно записать в таком виде:

1. Занеси в клетки пустыни исходную конфигурацию жизни, т.е. в некоторые клетки помести символ, которым ты будешь изображать жизнь организма, например · или *.

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

3. Построй новую конфигурацию.

Рассмотрим эти три шага подробнее.

1 шаг. Занеси в клетки пустыни исходную конфигурацию жизни.

Алгоритм1 определения «есть ли жизнь в данной клетке»

по исходной конфигурации

Чтобы определить есть ли жизнь в каждой конкретной (фиксированной) клетке поля данной конфигурации нужно выполнить следующий алгоритм1:

2.1Подсчитай число живых соседей данной клетки, присвой это число переменной k, т.е. подсчитай, в каких соседних клетках есть · или *. Перейди на шаг 2.2.

Алгоритм2 – заполнения каждой клетки новой «жизнью»

3.1 Если в клетке народившийся организм, зафиксируй в ней жизнь (занеси в клетку · или *) и перейди на 3.3, иначе – на 3.2.

3.2 Если в клетке погибший организм, то сделай клетку пустой и перейди на шаг 3.3, иначе оставь состояние клетки без изменения и перейди на шаг 3.3.

3.3 Закончи алгоритм заполнения каждой клетки новым состоянием, новой «жизнью».

Очевидно, что Алгоритм1 и Алгоритм2 выполняются столько раз, сколько клеток в пустыне, т.е. они идентичны (одинаковы) для всех клеток.

Реализация одного хода игры на языке QBasic

Для проведения одного хода игрыследует выделить два поля. На одно наносится исходная конфигурация жизни и определяется для каждой клетки, есть ли в ней «жизнь», на другом поле строится новая конфигурация – следующее поколение. Можно проследить за эволюцией начальной конфигурации, повторяя ходы игры. Для реализации игры на компьютере в системе QBasic (Turbo Pascal) смоделируем каждое поле в структуру языка – массив A(1:n) и B(1:n) соответственно, значение элемента массива «*» означает жизнь, а значение элемента «-» означает, что в клетке пустыни жизни нет (блок-схема стр. 137-138, программа стр. 139-140).