Курсовая работа: Задача о Ханойских башнях

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

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

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

2.1 Пошаговый алгоритм (с рекурсией)

Входные данные: количество дисков, находящихся на колышке a;

Выходные данные: последовательность действий;

Шаг0:{определение типа переменных};

Шаг1:{описание процедуры Pernesti, которая выводит последовательность действий};

Шаг1.1:{переместить (n-1) дисков с колышка a на колышек b};

Шаг1.2:{переместить n-ый диск с a на c};

Шаг1.3:{переместить (n-1) диск с b на c};

(шаги 1.2-1.3 выполняются рекурсивно);

Шаг2:{основная программа};

Шаг2.1:{ввод количества дисков};

Шаг2.2:{вызов процедуры Perenesti}.

2.2 Структограмма

3. Проверка правильности алгоритма

Правильность алгоритма проверим при n=3 и n=4.

n=3

переместить диск со стержня a на стержень c

переместить диск со стержня a на стержень b

переместить диск со стержня c на стержень b

переместить диск со стержня a на стержень c

переместить диск со стержня b на стержень a

переместить диск со стержня b на стержень c

переместить диск со стержня a на стержень c

n=4

переместить диск со стержня a на стержень b