汉诺塔算法的非递归演示

1 课题描述

汉诺塔问题介绍：在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片，一次只移动一片，不管在哪根针上，小片必在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一概针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。 本次程序用C++语言编写了一个程序，建立一个汉诺塔模型，利用函数的非递归调用算法，实现汉诺塔算法的非递归的演示的功能。说明了测试方法,写出了完整的运行结果,具有较好的界面设计。本次课题阐述了设计思想，画出了流程图达到操作简单，易于为用户所接受的目标。

- 1 -

2 问题分析和任务定义

本课题要求完成汉诺塔算法的非递归的演示，而不是递归。汉诺塔问题包括两个非递归算法，解集递推法和解集树法。

汉诺塔游戏的问题是:

（1）有三根杆子A，B，C。A杆上有若干圆盘 （2）每次移动一块圆盘，小的只能叠在大的上面

（3）.把所有圆盘从A杆全部移到C杆上

经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动圆盘： 如3阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C 此外，汉诺塔问题也是程序设计中的经典非递归问题。

将n个盘子从a座移动到c座可以分解为以下3个步骤：(1)将a上n-1个盘借助c座先移到b座上。(2)把a座剩下的一个盘移到c座。(3)将n-1个盘从c座借助于a座移到c座上。 其基本要求是：

输入的形式和输入值的范围：输入圆盘的数量，类型为整型，大于零。输出的形式：运行结果为用字母表示移动盘子的方案，而并非是真正移动盘子。 程序所能达到的功能：输入圆盘数量为定值时的移盘方案。帮助我们更清晰的理解汉诺塔问题，及非递归调用的应用。

- 2 -

3 逻辑设计

本设计的程序流程图如下：

开始Int(0Return()Ta[0].name=’A’Int i=0Ni

图3.1 main函数和creat函数模块图（1）

- 3 -

1NNj

图3.2 main函数和creat函数模块图（2）

- 4 -