Ханойская башня алгоритм паскаль

Ханойская башня алгоритм паскаль

Задача

Написать программу решения задачи о ханойской башне.

Решение

В одной из древних легенд говорится следующее. «В храме Бенареса находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разного диаметра из чистого золота так, что наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это – башня Брамы. Работая день и ночь, жрецы переносят диски с одного стержня на другой, следуя законам Брамы:
1. диски можно перемещать с одного стержня на другой только по одному;
2. нельзя класть больший диск на меньший.
Когда все 64 диска будут перенесены с одного стержня на другой, и башня, и храмы, и жрецы-брамины превратятся в прах, и наступит конец света».

Эта древняя легенда породила задачу о Ханойской башне: переместить m дисков с одного из трех стержней на другой, соблюдая «законы Брамы».

Назовем стержни левым (left), средним (middle) и правым (right). Задача состоит в переносеm дисков с левого стержня на правый.

Задача может быть решена одним перемещением только для одного (m = 1) диска. В общем случае потребуется 2m-1 перемещений.

Построим рекурсивное решение задачи, состоящее из трех этапов:

a) перенести башню, состоящую из m – 1 диска, с левого стержня на средний;
b) перенести один оставшийся диск с левого стержня на правый;
c) перенести башню, состоящую из m – 1 диска, со среднего стержня на правый.

Таким образом, задача о перемещении m дисков сводится к задаче о перемещении m – 1диска. Обращаясь опять к этому же алгоритму, сведем задачу к перемещению m – 2 дисков. Продолжая этот процесс, получим, в конце концов, задачу о перемещении одного диска. Эта задача решается за один ход. Таким образом, в процессе решения возникают промежуточные задачи: переместить башню из нескольких n дисков с одного стержня на другой.

Обозначим тот стержень, с которого следует снять диски, через s1, на который надеть – через sk, а вспомогательный стержень через sw.

Оформим алгоритм решения задачи о переносе башни из n дисков с s1 на sk в виде процедуры move с 4-мя параметрами: n, s1, sw, sk; алгоритм для n = 1 выделим в отдельную процедуру step, которая перемещает один диск со стержня s1 на sk.

Есть три стержня A, B, и C. На стержень A надето N дисков, наверху самый маленький, каждый следующий диск больше предыдущего, а внизу самый большой. На другие стержни дисков не надето.

Hеобходимо перенести диски со стержня A на стержень C, пользуясь стержнем B, как вспомогательным, так, чтобы диски на стержне C располагались в том же порядке, в каком они располагаются на диске A перед перемещением.

При перемещении никогда нельзя класть больший диск на меньший.


Решение

Рекурсивный метод

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

Всего получается 2 N-1 перекладываний.

Нерекурсивный метод

Стержню, на котором диски находятся в начале, дадим номер 0; стержню, на который их надо перенести — номер 2; и, соответственно, оставшемуся стержню — номер 1.

Читайте также:  Программа искать музыку по звуку

Пусть всего дисков N. Занумеруем диски в порядке увеличения радиуса числами 0,1,2. N-1.

Как известно, задача решается за 2 N-1 ходов. Занумеруем ходы числами 1,2. 2 N-1 .

Любое натуральное число i единственным образом представимо в виде i=(2t+1)*2 k , где t и k — целые (т.е. как произведение нечетного числа на некоторую степень двойки). Так вот, на i-ом ходе переносится диск номер k со стержня номер ((-1) N-k *t mod 3) на стержень номер ((-1) N-k *(t+1) mod 3).

если пpедставить что стержни, на котоpые одеваются диски, pасположены в yглах pавностоpоннего тpеyгольника, то самый маленький диск каждым нечетным ходом движется по (или пpотив, это от пеpвоначального кол-ва дисков зависит) часовой стpелки.

Все четные ходы опpеделяются однозначно. Какой диск меньше — тот и перекладывать (иначе противоречит условию). Т.к. тpогать диск 0 нельзя и класть больший на меньший тоже нельзя.

Отметим две закономерности:

  1. Hа каждом нечетном ходy происходит перенос наименьшего диска.
  2. Hаименьший диск всегда переносится циклически: либо A-B-C-A-B-C-. (в слyчае четного количества дисков), либо A-C-B-A-C-B-. (в слyчае нечетного).

А посемy полyчаем алгоритм:

1. Определяем число дисков, откyда находим как бyдет перемещаться наименьший диск (данный шаг делается в начале, притом один раз).

2. Смотрим номер хода: если нечетный — переносим наименьший диск в направлении, определенном в п.1. если четный — то возможный ход один единственный — берем наименьший из двyх верхних дисков и переносим его.

Можно написать немного по другому:

Для N от 1 до 2 k-1 выполнять
1. В двоичном представлении N найти самый правый ненулевой разряд. Обозначим номер этого разряда t.

2. Обозначим номер стержня, на котором находится диск t через i. Переместить диск t со стержня i на стержень (i+(-1) t ) mod 3.

Задача 3. Несколько дисков различных размеров нанизаны на один из нескольких стержней, образуя пирамидку (башню), чем выше находится диск, тем меньше его диаметр. Требуется переместить эту пирамидку на другой стержень, соблюдая следующие правила: за один раз можно перекладывать только один диск; нельзя класть диск на меньший по диаметру диск; можно пользоваться только одним резервным стержнем[15].

Начальное и конечное положения четырех дисков (пирамидки)
при перекладывании с первого стержня на третий

Напишите алгоритм перемещения башни из n дисков со стержня 1 на стержень 3 при любом значении n:

а) Найдите метод решения задачи с применением рекурсии и метод, в котором рекурсия не используется.

б) Напишите алгоритм решения задачи в виде блок-схемы.

в) Напишите программу на языках QBasic, Ершол, Turbo Pascal.

Решение. Эта задача очень легко решается с использованием рекурсии, но достаточно сложно, когда рекурсия не допускается.

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

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

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

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

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

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

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

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

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

Читайте также:  Нетбук msi u100 характеристики

В. Рассмотрим алгоритм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 имеет вид:

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

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

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

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

Число дисков Число ходов

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

Первое решение Второе решение
1=0*2+1 1=2 1 -1
3=1*2+1 3=2 2 -1
7=3*2+1 7=2 3 -1
15=7*2+1 15=2 4 -1
31=15*2+1 31=2 5 -1
kn=kn-1*2+1 kn=2 n -1

kn и knn-ые члены соответственно первой и второй последовательностей.

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

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

Позиция Шаги алгоритма Постепенная детализация шагов алгоритма
1, A→C
2, A→B 1, A→B
1, C→B
2 n -2 3, A→C 1, A→C 1, A→C
1, B→A
2, B→C 1, B→C
1, A→C
2 n -1 4, A→B 1, A→B 1, A→B 1, A→B
1, C→B
2, C→A 1, C→A
1, B→A
2 n -1 +2 n -2 3, C→B 1, C→B 1, C→B
1, A→C
2, A→B 1, A→B
2 n -1 1, C→B

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

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

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

Позиция T(i) D(i) A(i) T(i) D(i) A(i)
2 n -2 n-1 A 6-A-B
2 n -1 n A B A B
2 n -1 +2 n -2 n-1 6-A-B B
2 n -1

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

алгоритма игры «Ханойская башня» алгоритма 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

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

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

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

ELSEIF t(i) > 1 THEN

LOOP UNTIL fl = 1

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

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

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

If t[i]>1 then Decompose

If n 3, если да, то убери · или * из клетки (сделай ее пустой для следующего поколения). Перейди на шаг 2.5.

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

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

Алгоритм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).

F.Эволюция некоторых простых конфигура­ций колоний организмов.Рассмотрим как изменяются некоторые простые конфигурации колоний организмов при игре.

1. Один организм, а также любая пара организмов, где бы они не стояли, очевидно, погибают после первого же хода.

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

Ссылка на основную публикацию
Форге оф импаерс великие строения
Другое название: Кузница Империй Ниже мы приводим подробный гайд по игре Forge of Empires с советами как вам быстрее отстроить...
Троттлинг процессора что это
Простой компьютерный блог для души) Всем привет. Сегодня мы затронем тему процессоров, а если быть точнее, то такое явление как...
Троянские программы и хакерские утилиты
В данную категорию входят программы, осуществляющие различные несанкционированные пользователем действия: сбор информации и ее передачу злоумышленнику, ее разрушение или злонамеренную...
Форза хорайзен 3 список машин
Серия игр Forza всегда поражала количеством доступных автомобилей. На момент выхода игры доступно уже более 150 автомобилей, а разработчики обещают...
Adblock detector