数据结构实验报告汉诺塔

一、实验背景汉诺塔问题（Hanoi Tower Problem）是一个经典的递归问题，最早由法国数学家亨利·埃德蒙·卢卡斯（Edouard Lucas）在1883年提出。

该问题涉及三个柱子和一系列大小不同的盘子，初始时所有盘子按照从小到大的顺序叠放在一个柱子上。

问题的目标是按照以下规则将所有盘子移动到另一个柱子上：每次只能移动一个盘子，且在移动过程中，大盘子不能放在小盘子上面。

汉诺塔问题不仅是一个数学问题，也是一个计算机科学问题。

它在算法设计、递归算法分析等领域有着重要的应用价值。

通过解决汉诺塔问题，可以加深对递归算法的理解，同时也能够锻炼逻辑思维和问题解决能力。

二、实验目的1. 理解汉诺塔问题的基本原理和解决方法。

2. 掌握递归算法的设计和应用。

3. 分析汉诺塔问题的复杂度，为实际应用提供参考。

三、实验内容1. 实验环境：Windows操作系统，Python编程语言。

2. 实验步骤：（1）设计一个汉诺塔问题的递归算法。

（2）编写程序实现该算法。

（3）测试算法在不同盘子数量下的运行情况。

（4）分析算法的复杂度。

3. 实验程序：```pythondef hanoi(n, source, target, auxiliary):if n == 1:print(f"Move disk 1 from {source} to {target}")returnhanoi(n-1, source, auxiliary, target)print(f"Move disk {n} from {source} to {target}") hanoi(n-1, auxiliary, target, source)# 测试程序hanoi(3, 'A', 'C', 'B')```4. 实验结果：（1）当盘子数量为3时，程序输出以下移动序列：```Move disk 1 from A to CMove disk 2 from A to BMove disk 1 from C to BMove disk 3 from A to CMove disk 1 from B to AMove disk 2 from B to CMove disk 1 from A to C```（2）当盘子数量为4时，程序输出以下移动序列：```Move disk 1 from A to CMove disk 2 from A to BMove disk 1 from C to BMove disk 3 from A to CMove disk 1 from B to AMove disk 2 from B to CMove disk 1 from A to CMove disk 4 from A to BMove disk 1 from C to BMove disk 2 from C to AMove disk 1 from B to AMove disk 3 from C to BMove disk 1 from A to CMove disk 2 from A to BMove disk 1 from C to BMove disk 4 from B to CMove disk 1 from B to AMove disk 2 from A to CMove disk 1 from A to C```四、实验分析1. 算法复杂度：汉诺塔问题的递归算法具有指数级的复杂度，其时间复杂度为O(2^n)，其中n为盘子的数量。

汉诺塔实验报告汉诺塔实验报告引言：汉诺塔是一种经典的数学谜题，它激发了人们对逻辑思维和解决问题的热情。

本次实验旨在通过模拟汉诺塔游戏，探究其背后的数学原理和解决方法，并分析实验结果。

实验目的：1. 理解汉诺塔问题的规则和目标。

2. 掌握汉诺塔问题的解决方法。

3. 分析实验结果，总结汉诺塔问题的数学特性。

实验过程：首先，我们需要了解汉诺塔的规则。

汉诺塔由三个柱子组成，分别命名为A、B 和C。

开始时，所有的盘子都放在柱子A上，且按照从小到大的顺序叠放。

目标是将所有的盘子从柱子A移动到柱子C上，期间可以利用柱子B作为辅助。

接下来，我们使用计算机程序模拟汉诺塔游戏。

通过编写算法，我们可以实现自动化的盘子移动过程。

我们设定盘子的数量为n，初始时所有盘子都在柱子A上。

通过递归算法，我们可以将柱子A上的n个盘子移动到柱子C上。

实验结果：我们进行了多次实验，分别模拟了不同数量的盘子移动过程。

通过观察实验结果，我们可以得出以下结论：1. 移动次数：根据经验公式2^n-1，我们可以计算出移动n个盘子所需的最小步数。

实验结果验证了这一公式的正确性，进一步证明了汉诺塔问题的数学特性。

2. 时间复杂度：随着盘子数量的增加，移动所需的时间也呈指数级增长。

这是因为递归算法的时间复杂度为O(2^n)，需要大量的运算时间。

3. 解决方法：我们发现，无论盘子数量多少，解决汉诺塔问题的方法都是相同的。

通过将问题分解为更小规模的子问题，我们可以逐步移动盘子，最终达到目标。

4. 空间复杂度：在我们的模拟实验中，我们使用了计算机程序来模拟汉诺塔游戏。

这意味着我们不需要实际的物理空间来放置盘子，大大降低了实验的难度和成本。

结论：通过本次实验，我们深入了解了汉诺塔问题的规则和解决方法。

我们通过模拟实验验证了数学公式，并观察到了汉诺塔问题的特殊性质。

此外，我们还了解到递归算法的时间复杂度和空间复杂度，这对于进一步研究和解决类似问题具有重要意义。

目录1 课题需求......................................... 错误！未定义书签。

2 概要设计 (2)2.1 递归 (2)2.2 非递归 (4)3 详细设计和实现 (2)4 调试与测试 (11)4.1 启动窗口 (11)4.2 递归实现 (11)4.3 非递归实现 (13)4.4 退出 (14)5 致谢 (15)6 参考文献 (15)2 概要设计汉诺塔是一个经典的问题，曾被称为“世界末日问题”。

此次程序设计全面讨论了解决此问题的方案，详细研究，了解，解决问题的算法设计，给出了具体算法，最后由手工输入测试数，运用递归与非递归算法得出结果。

2.1 递归若只有一个圆盘的话直接将圆盘移至C杆；若为N个圆盘的话将N-1个圆盘当作整体借助C杆移至B杆，将N号盘移至C杆，再借助A杆重复上面的操作即可将圆盘移至C杆。

2.2 非递归看出二叉树实现，假设‘A’一开始有n个圆盘，前n-1个‘A’通过‘C’移到‘B’上看出左孩子，第n个移到‘C’看出根，将‘B’中n-1通过‘A’移到‘C’看成右孩子，建立完全二叉树。

主要借助二叉树的非递归中序遍历方法实现，利用栈堆来实现。

3 详细设计和实现DiGui.cpp文件：#include<iostream.h>//递归法解决汉诺塔问题void HanNuoTaDiGui(int n,char a,char b,char c){if(n<2){cout<<" 圆盘"<<n<<" : 从"<<a<<"移到"<<c<<endl;return;}HanNuoTaDiGui(n-1,a,c,b);//n-1个圆盘移到bcout<<" 圆盘"<<n<<" : 从"<<a<<"移到"<<c<<endl;HanNuoTaDiGui(n-1,b,a,c);}munu.cpp文件：//目录菜单#include<iostream.h>void munu(){cout<<"**************************************************"<<endl;cout<<"********************************************"<<endl<<endl;cout<<" 汉诺塔 "<<endl<<endl;cout<<"**************************************************"<<endl;cout<<"**************************************************"<<endl;cout<<"请选择实现的方法："<<endl;cout<<" 1 代表递归方法。

汉诺塔实验报告2012 年 12 月 21 日目录1、概述 ................................................................ 错误～未定义书签。

42、实验目的 ........................................................ 错误～未定义书签。

43、问题分析 ..................................................................... ...................... 2 4、实验步骤 ........................................................ 错误～未定义书签。

55、流程图 ..................................................................... .......................... 3 6、程序代码: .................................................................... ................... 4 7、程序调试与测试 ..................................................................... .......... 8 8、结论 .............................................................. 错误～未定义书签。

129、总结 .............................................................. 错误～未定义书签。

15一、概述数据结构是计算机学科非常重要的一门专业基础理论课程，要想编写针对非数值计算问题的高质量程序，就必须要熟练的掌握这门课程设计的知识。

数据结构求解汉诺塔问题的递归算法汉诺塔问题是一个经典的数学问题，它可以通过递归算法来求解。

在这个问题中，我们需要将一堆盘子从一个柱子移动到另一个柱子，同时遵守以下规则：一次只能移动一个盘子，大盘子不能放在小盘子上面。

为了解决这个问题，我们可以使用数据结构中的栈来模拟柱子的堆叠。

我们可以将每个柱子表示为一个栈，每个盘子表示为一个元素。

初始时，所有的盘子都在第一个柱子上，我们需要将它们移动到第三个柱子上。

下面是求解汉诺塔问题的递归算法的伪代码：```1. 定义一个函数hanoi，接受参数n、起始柱子A、辅助柱子B、目标柱子C2. 如果n等于1，则直接将盘子从A移动到C3. 否则，将n-1个盘子从A移动到B，借助C作为辅助柱子4. 将第n个盘子从A移动到C5. 将n-1个盘子从B移动到C，借助A作为辅助柱子```接下来，我们来详细解释一下这个算法。

首先，我们定义了一个函数hanoi，它接受四个参数：n表示盘子的数量，起始柱子A、辅助柱子B和目标柱子C。

在函数内部，我们首先判断如果n等于1，那么我们直接将盘子从A移动到C即可。

这是递归算法的终止条件。

如果n大于1，我们需要将n-1个盘子从A移动到B，借助C作为辅助柱子。

这一步是通过递归调用hanoi函数来实现的。

在递归调用中，我们将n-1作为新的盘子数量，A作为起始柱子，B作为目标柱子，C作为辅助柱子。

接下来，我们将第n个盘子从A移动到C。

这一步是直接操作的，不需要递归调用。

最后，我们需要将n-1个盘子从B移动到C，借助A作为辅助柱子。

同样地，我们通过递归调用hanoi函数来实现这一步。

在递归调用中，我们将n-1作为新的盘子数量，B作为起始柱子，C作为目标柱子，A作为辅助柱子。

通过这样的递归调用，我们可以将所有的盘子从起始柱子A移动到目标柱子C，同时遵守汉诺塔问题的规则。

总结起来，数据结构中的栈可以很好地模拟汉诺塔问题中的柱子堆叠，而递归算法则可以很好地解决这个问题。

汉诺塔实验报告实验报告课程名称数据结构实验名称汉诺塔实验类型验证性实验实验地点计304机房实验日期指导教师魏海平专业计算机科学与技术班级计算机1002学号20姓名张森辽宁石油化工大学计算机与通信工程学院数据结构实验报告评分表项目要求分数有无项目（√）得分预习报告（30分）实验目的明确 5 实验内容理解透彻 5 实验方案设计完整合理程序总体框架设计完整10完成相关辅助代码 5测试方案合理 5实验过程（30分）发现问题 5 问题的分析15 问题的解决方法10 实验报告（20分）内容翔实无缺漏5 如实记录实验过程10 撰写规整 5实验总结（10分）实验结果的分析 5 按照结果对原实验方案的改进意见 5实验体会（10分）实验的收获 5 实验内容的发散考虑 5总分1.实验目的：通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。

2.问题描述：汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A),其上有64个金碟。

所有碟子按从大到小的次序从塔底堆放至塔顶。

紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。

从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。

每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。

当牧师们完成任务时，世界末日也就到了。

3.算法设计思想：对于汉诺塔问题的求解，可以通过以下三个步骤实现：(1)将塔A上的n-1个碟子借助塔C先移到塔B上。

(2)把塔A上剩下的一个碟子移到塔C上。

(3)将n-1个碟子从塔B借助于塔A移到塔C上。

4.实验步骤：1.用c++ 或c语言设计实现汉诺塔游戏；2.让盘子数从2 开始到7进行实验，记录程序运行时间和递归调用次数；3.画出盘子数n和运行时间t 、递归调用次数m的关系图，并进行分析。

实验内容及实验结果请写出具体的实验步骤，并给出相应的实验结果，附上编写的程序及其运行结果截图!!#includevoid hanio(int n,char A,char B,char C){if (n==1) printf("Move disk from %c to %c\n",A,B);else{hanio(n-1,A,C,B);printf("Move disk from %c to %c\n",A,B);hanio(n-1,C,B,A);}}void main(){int n;printf("input the number of disk:");scanf("%d",&n);printf("the steps for %d disk are:\n",n);hanio(n,'A','B','C');}运行结果：7、结论通过对上述递归在Hanoi塔问题上的应用分析，我们可以得出如下结论：1、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模取决于递归调用的次序。

实验一（3）一、实验题目：顺序表的应用二、实验内容：Hanoi塔问题。

（要求4个盘子移动，输出中间结果）三、设计分析：首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，按顺时针方向依次摆放 A C B。

（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。

（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。

即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。

这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。

（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。

所以结果非常简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C四、程序代码：#include<iostream>using namespace std;int m=0;void move(char A,int n,char C){cout<<n<<"从"<<A<<"到"<<C<<endl;}void hanoi(int n,char A,char B,char C){if(n==1){move(A,1,C);m=m+1;}else{hanoi(n-1,A,C,B);move(A,n,C);hanoi(n-1,B,A,C);m=m+1;}}void main(){int n;cout<<"请输入圆盘的个数N=";cin>>n;cout<<"移动的方法如下:"<<endl;hanoi(n, 'A','B','C');cout<<"移动总次数:"<<m<<endl;}五、测试用例：六、实验总结通过这次实验，对于顺序表的相关知识有了更加深刻的认识，虽然中间出了很多问题，但是经过查阅资料，请教同学，对程序进行调试以后都得以解决。

计算机学院实验报告课程名称：数据结构实验名称：汉诺塔学生姓名：朱孝彬学生学号：20110511001实验日期：2012一、实验目的1．理解数据结构中汉诺塔2．掌握汉诺塔的C++描述。

二、实验内容1．编制汉诺塔的程序。

三、实验步骤1．需求分析本演示程序用C++6.0编写，完成汉诺塔的生成，2．概要设计1）为了实现上述程序功能，需要定义单链表的抽象数据类型：（1）insert3. 源代码#include<stdio.h>#include<stdlib.h>#define MaxSize 30typedef struct{int data[MaxSize];char name;int top;}SqStack;void Move(SqStack * &a,SqStack * &b);int Hanoi(int n,SqStack * &a,SqStack * &b,SqStack * &c); void InitStack(SqStack * &s);int Push(SqStack * &s,int e); /*进栈*/int Pop(SqStack * &s,int &e); /*出栈*/void main(){int n,i;SqStack *a,*b,*c;InitStack(a);InitStack(b);InitStack(c);a->name='A';b->name='B';c->name='C';printf("请输入汉诺塔中圆环的个数n: ");scanf("%d",&n);for(int t=n;t>0;t--)Push(a,t);printf("\n\t假设有三根柱子A、B、C，开始时A柱子上有1~%d环，并且它们是按照从小到大的顺序放在A柱子上的，按照汉诺塔规则，将A柱子上所有环通过B柱子，移动到C柱子的则移动方法为：\n\n",n);i=Hanoi(n,a,b,c);free(a);free(b);free(c);printf("总共需要移动的次数为：%d次\n",i);}void InitStack(SqStack * &s) /*初始化栈*/{s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;}int Push(SqStack * &s,int e) /*进栈*/{if(s->top==MaxSize-1)return 0;s->top++;s->data[s->top]=e;return 1;}int Pop(SqStack * &s,int &e) /*出栈*/{if(s->top==-1)return 0;e=s->data[s->top];s->top--;return 1;}int Hanoi(int n,SqStack * &a,SqStack * &b,SqStack * &c){static int i=0;if(n==1){Move(a,c);i++;}else{Hanoi(n-1,a,c,b);Move(a,c);i++;Hanoi(n-1,b,a,c);}return i;}void Move(SqStack * &a,SqStack * &b){int i;Pop(a,i);printf("\t\t\t%d环-->%c柱子\n",i,b->name); Push(b,i);}实验结果：1.当输入2时，运行结果如下：2. 当输入3时，运行结果如下：3. 当输入4时，运行结果如下：4. 当输入5时，运行结果如下：四、实验总结（结果分析和体会）本次试验中，在解决汉诺塔问题中，结合了最近刚学的栈的知识，并且运用到之前学到的函数的递归的运用，很好的解决了这一类问题。

汉诺塔目录一.小组成员介绍二.问题背景描述三..汉诺塔的递归算法1、汉诺塔移动示意图2、源程序代码3、流程图4、运行结果四．汉诺塔的非递归算法1、源程序代码2、流程图3、运行结果五.课程设计的心得成员介绍组员姓名学号任务杨乐41012054 组长，设计非递归算法和程序，并报告非递归汉诺塔算法梁义莲41012075 负责递归算法程序设计、调试、运行和PPT制作，修改word，制作递归算法的流程图蔡婷婷41012072 负责非递归算法程序设计、调试、运行和PPT制作，修改word，制作非递归算法的流程图杜得文41012061 整理word，把课程设计整个流程用文字形式展示岳跃鹏41012057 查阅资料，参与递归程序的设计和调试，帮助制作word 郝雯41012086 整理word，把课程设计整个流程用文字形式展示王新颖41012082 整理word，把课程设计整个流程用文字形式展示江小英41012097 报告递归算法，查阅资料，参与递归程序的设计指导老师雷秀娟.问题背景描述Hanoi（汉诺）塔问题是一个古典的数学问题，是一个用递归方法解题的典型例子。

汉诺塔游戏是这样的：有三个塔（塔1，塔2和塔3）和N个半径不同的盘子。

初始所有的盘子按半径从小到大堆叠在塔1上，半径最小的盘子在最上面。

规则：每次只可以移动一个塔上最顶端的盘子到另一个塔上，而且不可以把大盘子堆在小盘子上。

问题是要把所有盘子移动到塔3上。

例如：有三个盘子分别命名为X，Y，Z的塔座，在塔座X上插有n个直径大小各不相同，以小到大编号为1，2，……n的圆盘，现要求将X轴上的n 个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则：（1）每次只能移动一个圆盘;（2）圆盘可以插在X，Y和Z中的的任一塔座上；（3）任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。

解题思路；当n=3时，第一步，现将3号圆盘移至Z塔座上；第二步，将2号圆盘移至Y塔座上；第三步，将3号圆盘从Z塔座移至Y塔座上；第四步，将1号圆盘移至Z塔座上；第五步，将3号圆盘移至X塔座上；第六步，将2号圆盘移至Z塔座；第七步，将3号圆盘移至Z塔座上，计算完毕。

1.实验目的： 通过本实验，掌握复杂性问题的分析方法，了解汉诺塔
游戏的时间复杂性和空间复杂性。 2.问题描述：
汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有 一座钻石宝塔（塔 A),其上有 64 个金碟。所有碟子按从大到小的次 序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔 B 和 塔 C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔 A 上的碟子移动到塔 C 上去，其间借助于塔 B 的帮助。每次只能移 动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。 当牧师们完成任务时，世界末日也就到了。 3.算法设计思想：
8、总结
5
缓存大小
通过对汉诺塔算法的分析让我更清楚的认识到了不同的算法对 程序性能的影响，也让我明白掌握了算法将会有助于提高软件的开 发。
6
2）Hanoi 塔问题递归程序的复杂度分析
① 运行 hanoi 程序的时间
程序 hanoi.c 在硬件环境为赛扬 400MHz、内存 128M 的计算平台 （不同机器运行时间有一定差别）运行，可得出如下时间结果：
盘子数
时间结果
<=12 个
<=1 秒
14 个
2秒
16 个
13 秒
20 个
204 秒
② 时间复杂度
自定义头文件 ：#pragma once
#include "targetver.h" #include <stdio.h> #include <tchar.h>
结果如下：
2
6.递归应用中的 Hanoi 塔问题分析 1）Hanoi 塔问题中函数调用时系统所做工作
一个函数在运行期调用另一个函数时，在运行被调用函数之前，系 统先完成 3 件事：

一、引言汉诺塔问题是一种经典的递归问题，起源于印度的一个古老传说。

该问题涉及三个柱子和若干个大小不一的盘子，要求按照一定的规则将盘子从第一个柱子移动到第三个柱子。

在解决汉诺塔问题的过程中，我们可以锻炼逻辑思维、递归算法设计以及编程能力。

本报告将详细介绍汉诺塔问题的背景、解决方法、实践过程及心得体会。

二、汉诺塔问题背景汉诺塔问题最早由法国数学家卢卡斯在1883年提出。

传说在古印度有一个名为汉诺塔的庙宇，庙里有一个汉诺塔塔，塔上有64个盘子，每个盘子大小不同，且按照从小到大的顺序叠放。

为了拯救世界，僧侣们需要将所有盘子从第一个柱子移动到第三个柱子，同时每次只能移动一个盘子，且在移动过程中，大盘子不能放在小盘子上面。

三、汉诺塔问题解决方法1. 递归算法汉诺塔问题可以通过递归算法来解决。

递归算法的基本思想是将大问题分解为若干个小问题，然后逐一解决小问题，最终解决大问题。

对于汉诺塔问题，我们可以将其分解为以下三个步骤：（1）将n-1个盘子从第一个柱子移动到第二个柱子；（2）将第n个盘子从第一个柱子移动到第三个柱子；（3）将n-1个盘子从第二个柱子移动到第三个柱子。

递归算法如下：```function hanoi(n, start, end, auxiliary) {if (n == 1) {console.log(`移动盘子1从${start}到${end}`);return;}hanoi(n - 1, start, auxiliary, end);console.log(`移动盘子${n}从${start}到${end}`);hanoi(n - 1, auxiliary, end, start);}```2. 动态规划除了递归算法，我们还可以使用动态规划的方法来解决汉诺塔问题。

动态规划的思想是将问题分解为若干个子问题，然后求解子问题，最后将子问题的解合并成原问题的解。

对于汉诺塔问题，我们可以定义一个二维数组dp[i][j]，表示将i个盘子从第一个柱子移动到第j个柱子的最小移动次数。

一，算法程序#include <iostream>using namespace std; /*圆盘的个数最多为64*/const int MAX = 64; /*用来表示每根柱子的信息*/struct st{int s[MAX]; /*柱子上的圆盘存储情况*/int top; /*栈顶，用来最上面的圆盘*/char name; /*柱子的名字，可以是A，B，C中的一个*/int Top() /*取栈顶元素*/{return s[top];}int Pop(){return s[top--];}void Push(int x){s[++top] = x;}} ;long Pow(int x, int y); /*计算x^y */void Creat(st ta[], int n); /*给结构数组设置初值*/void Hannuota(st ta[], long max); /*移动汉诺塔的主要函数*/int main(void){int n;cin >> n; /*输入圆盘的个数*/st ta[3]; /*三根柱子的信息用结构数组存储*/Creat(ta, n); /*给结构数组设置初值*/long max = Pow(2, n) - 1; /*动的次数应等于2^n – 1*/Hannuota(ta, max); /*移动汉诺塔的主要函数*/system("pause");return 0;}void Creat(st ta[], int n){ta[0].name = 'A';ta[0].top = n-1; /*把所有的圆盘按从大到小的顺序放在柱子A上*/ for (int i=0; i<n; i++)ta[0].s[i] = n - i; /*柱子B，C上开始没有没有圆盘*/ ta[1].top = ta[2].top = 0;for ( i=0; i<n; i++)ta[1].s[i] = ta[2].s[i] = 0; /*若n为偶数，按顺时针方向依次摆放A B C*/if (n%2 == 0){ta[1].name = 'B';ta[2].name = 'C';}else /*若n为奇数，按顺时针方向依次摆放A C B*/{ta[1].name = 'C';ta[2].name = 'B';}}long Pow(int x, int y){long sum = 1;for (int i=0; i<y; i++)sum *= x;return sum;}void Hannuota(st ta[], long max){int k = 0;int i = 0;int ch;while (k < max){/*按顺时针方向把圆盘1从现在的柱子移动到下一根柱子*/ch = ta[i%3].Pop();ta[(i+1)%3].Push(ch);cout << ++k << ": " <<"Move disk " << ch << " from " << ta[i%3].name <<" to " << ta[(i+1)%3].name << endl;i++;/*把另外两根柱子上可以移动的圆盘移动到新的柱子上*/if (k < max){ /*把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆盘*/if (ta[(i+1)%3].Top()==0 || ta[(i-1)%3].Top()>0 && ta[(i+1)%3].Top() >ta[(i-1)%3].Top()){ch = ta[(i-1)%3].Pop();ta[(i+1)%3].Push(ch);cout << ++k << ": " << "Move disk " << ch << " from " <<ta[(i-1)%3].name << " to " << ta[(i+1)%3].name << endl;}else{ch = ta[(i+1)%3].Pop();ta[(i-1)%3].Push(ch);cout << ++k << ": " << "Move disk "<< ch << " from " << ta[(i+1)%3].name<< " to " << ta[(i-1)%3].name << endl;}}}}二,实验感想在实际操作过程中犯的一些错误还会有意外的收获，感觉很有意思。

河内塔实验报告河内塔，又称汉诺塔，是一个经典的数学谜题，它由法国数学家爱德华·卢卡斯在1883年发现并首次提出。

这个谜题由三根柱子和若干个不同大小的圆盘组成，开始时所有圆盘都按照大小顺序叠在柱子A上。

游戏的目标是将所有圆盘从柱子A移动到柱子C上，并且在移动过程中始终保持较小的圆盘在较大的圆盘上面。

在移动的过程中可以借助柱子B作为中转站，但是每次只能移动一个圆盘，并且大圆盘不能放在小圆盘上面。

在这次实验中，我们尝试使用计算机程序来模拟解决河内塔问题的过程。

我们编写了一个递归算法，通过不断地将问题分解成更小的子问题来模拟人类解决这个谜题的过程。

我们将在实验中展示这个算法的运行情况，并对其进行分析和总结。

首先，我们设计了一个简单的图形界面来展示河内塔的三根柱子和圆盘，以及移动的过程。

通过点击按钮，我们可以观察到圆盘在柱子之间的移动情况，以及递归算法的运行过程。

实验结果显示，递归算法能够准确地模拟人类解决河内塔问题的过程，而且在圆盘数量较少的情况下，运行速度较快。

接下来，我们对递归算法的运行时间进行了分析。

我们发现随着圆盘数量的增加，递归算法的运行时间呈指数级增长。

这是因为递归算法在每一步都需要进行多次递归调用，导致运行时间呈指数级增长。

因此，在处理大规模的河内塔问题时，递归算法的效率较低，需要考虑其他更加高效的算法。

总结而言，通过这次实验，我们深入了解了河内塔问题以及递归算法的运行原理。

我们展示了递归算法在模拟解决河内塔问题时的运行情况，并对其进行了分析和总结。

同时，我们也意识到了递归算法在处理大规模问题时的效率问题，需要进一步研究和探讨更加高效的算法。

这次实验为我们提供了宝贵的经验，也为我们今后的研究工作提供了参考和借鉴。

一、实验目的1. 理解汉诺塔问题的基本原理。

2. 掌握分治算法在解决汉诺塔问题中的应用。

3. 通过编程实现汉诺塔问题的递归与非递归解法。

4. 分析汉诺塔问题的移动次数，并探讨优化方案。

二、实验原理汉诺塔问题是一个经典的递归问题，描述为：有n个大小不同的圆盘，它们分别放在三根柱子上，初始状态为第1根柱子从上到下依次排列。

要求按照以下规则将所有圆盘移动到第3根柱子上：1. 一次只能移动一个圆盘。

2. 任何时候，在某一根柱子上的圆盘都必须是按照从上到下依次递减的顺序排列。

3. 不能将一个较大的圆盘放在一个较小的圆盘上面。

汉诺塔问题可以通过分治法来解决。

分治法的基本思想是将大问题分解成小问题，分别解决小问题，最后将小问题的解合并成大问题的解。

对于汉诺塔问题，我们可以将其分解为以下三个子问题：1. 将n-1个圆盘从第1根柱子移动到第2根柱子。

2. 将第n个圆盘从第1根柱子移动到第3根柱子。

3. 将n-1个圆盘从第2根柱子移动到第3根柱子。

通过递归地解决这三个子问题，我们可以得到汉诺塔问题的解。

三、实验内容1. 递归解法我们可以使用递归函数来实现汉诺塔问题的递归解法。

以下是C语言实现的示例代码：```c#include <stdio.h>void hanoi(int n, char from, char to, char aux) {if (n == 1) {printf("Move disk 1 from %c to %c\n", from, to);return;}hanoi(n - 1, from, aux, to);printf("Move disk %d from %c to %c\n", n, from, to);hanoi(n - 1, aux, to, from);}int main() {int n;printf("Enter the number of disks: ");scanf("%d", &n);hanoi(n, 'A', 'C', 'B');return 0;}```2. 非递归解法除了递归解法，我们还可以使用栈来实现汉诺塔问题的非递归解法。

汉诺塔实验报告一：最终的效果图（1）没使用single step（2）添加了single step的效果图二：汉诺塔的树形结构图三：创建workspace 和application （1）创建workspace（2）创建application四：创建用户对象（1）整体图效果（2）主要控件插入的方法（3）属性的设置以Tower为例同样设置disk的属性，此处不再赘述。

（4）实例变量的声明（5）三个函数（1）Adddisk函数编写（2）Remove 函数编写（3）Resetpeg函数编写五：主窗口（1）窗口主体图窗口属性（2）start等button按钮的script（4）实例变量和外部变量（5）movedisk的函数六：增加单独移动的控制窗口（1）效果图（2）single step代码七：实验中遇到的问题（1）在一个控件中有的script有变量没有定义就忽视了警告直接保存，在进行第二个控件script的时候依然会出现错误。

如果一开始就不更改错误会出现所有的控件的script的都是一样的，如果在大型的项目中的话显然这种错误是毁灭性的。

（2）U_tower编辑了之后需要在w_tower中调用，但是u_tower在打开的状态下没有办法直接拖入到w_tower中。

同样的如果在w_tower中打开，那么U_tower是没有办法对它进行直接编辑的。

简单的说，就是u_tower和w_tower只能有一个在正在工作的工作台当中。

（3）经常会出现一些经过某些不当的操作正在工作的工作台的一般视图发生了变化，比如说出现不了layout需要在view中进行设置，system tree等的一些东西消失了要在window中重新设置出现。

（4）在这次实验中经常会出现一些变量的没有定义，比如说局部变量，实例变量，外部变量等等。

八：主要实验的思考通过本次实验主要学习了（1）w orkspace application structure 等创建和属性里面的注意点（2）怎样定义变量（3）对于function 和event怎么操作和修改（4）P B中的语法规范和C C++s的异同，处理这个问题的算法大致是相同的（5）对上面问题进行一些处理。

汉诺塔问题一、实验目的假设有三个分别命名为X，Y和Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1，2，…，n的圆盘，现要求将塔座X上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵守下列规则：(1)每次只能移动一个圆盘，(2)圆盘可以插在X，Y和Z中任一塔座上，(3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。

请写一算法，打印出正确的操作步骤。

二、实验内容利用顺序栈来实现：（1）程序要求用户输入初始圆盘数（2）输出所有移动过程三、实验平台Microsoft Visual C++四、设计流程用结构体数组来模拟栈的结构，其中no为一种标记，当no值为0时表示可以直接移动一个圆盘，当no值为1时表示需进一步分解；ns表示当前圆盘数X Y Z表示三个塔座。

由此得到hanoi函数，此函数将X塔座上的n个盘子借助于Y塔座按自下向上从大到小的顺序转移到Z塔座上。

五、源代码清单//#include "consts.h"#include <stdio.h>#define MAXNUM 50typedef struct{int no;int ns;char x,y,z;}Stack;void Hanoi(Stack st[], int n, char a, char b, char c){int top = 1;int n1;char a1, b1, c1;st[top].no = 1;st[top].ns = n;st[top].x = a;st[top].y = b;st[top].z = c;while (top > 0){if (st[top].no == 1){n1 = st[top].ns;a1 = st[top].x;b1 = st[top].y;c1 = st[top].z;top--;top++;st[top].no = 1;st[top].ns = n1-1;st[top].x = b1;st[top].y = a1;st[top].z = c1;top++;st[top].no = 0;st[top].ns = n1;st[top].x = a1;st[top].y = c1;top++;st[top].no = 1;st[top].ns = n1-1;st[top].x = a1;st[top].y = c1;st[top].z = b1;}while (top > 0 && (st[top].no == 0 || st[top].ns == 1)){if (top > 0 && st[top].no == 0){printf("\t将第%d个盘片从%c移动到%c\n",st[top].ns,st[top].x,st[top].y);top--;}if (top > 0 && st[top].ns == 1){printf("\t将第%d个盘片从%c移动到%c\n",st[top].ns,st[top].x,st[top].z);top--;}}}}int main (int argc,char* argv[]){int n = -1;Stack st[MAXNUM];printf("请输入汉诺塔中盘子个数：");scanf("%d",&n);printf("\nhanoi(%d)的移动过程为：\n",n);Hanoi(st,n,'x','y','z');return 0;}六、调试与测试结果。

汉诺塔实验报告汉诺塔实验报告引言：汉诺塔是一种经典的数学游戏，它可以帮助我们理解递归算法的原理和应用。

在这个实验报告中，我们将介绍汉诺塔的规则和解法，并通过实际操作来验证递归算法的正确性和效率。

一、汉诺塔的规则汉诺塔由三个柱子和一些盘子组成，盘子从小到大依次放置在柱子上。

游戏的目标是将所有盘子从起始柱子移动到目标柱子，期间可以借助一个辅助柱子。

然而，有一个重要的规则：在移动过程中，大盘子不能放在小盘子上面。

二、汉诺塔的解法汉诺塔问题的解法可以通过递归算法来实现。

我们可以将问题分解为三个子问题：1. 将n-1个盘子从起始柱子移动到辅助柱子；2. 将最大的盘子从起始柱子移动到目标柱子；3. 将n-1个盘子从辅助柱子移动到目标柱子。

通过递归调用上述三个步骤，我们可以解决汉诺塔问题。

下面是一个示例：```pythondef hanoi(n, start, target, auxiliary):if n > 0:# 将n-1个盘子从起始柱子移动到辅助柱子hanoi(n-1, start, auxiliary, target)# 将最大的盘子从起始柱子移动到目标柱子print("Move disk", n, "from", start, "to", target)# 将n-1个盘子从辅助柱子移动到目标柱子hanoi(n-1, auxiliary, target, start)# 测试hanoi(3, 'A', 'C', 'B')```三、实验结果与分析我们使用上述代码进行了一次实验，将3个盘子从A柱子移动到C柱子。

实验结果如下：Move disk 1 from A to CMove disk 2 from A to BMove disk 1 from C to BMove disk 3 from A to CMove disk 1 from B to AMove disk 2 from B to CMove disk 1 from A to C从实验结果可以看出，我们按照汉诺塔的规则成功地将3个盘子从起始柱子A 移动到目标柱子C。