汉诺塔问题C语言程序设计

#ifndef HANIO_H_#define HANIO_Hclass Stack{private:enum{ MAX=50 };int m_node[MAX];int m_top;int m_size;int m_index;public:Stack();~Stack() { };bool Isfull() { return m_top==MAX-1 ;}; //堆栈满则返回TRUE bool Isempty() { return m_top==-1;}; //堆栈空则返回TRUE int Top() { return m_top; };int TopValue() { return m_node[m_top];};int GetDataFromIndex(int i) { return m_node[i]; };int GetIndex() { return m_index; } ;void SetIndex(int index) { m_index = index; };int Size() { return m_top+1; };bool Push(int data);bool Pop(int * pData);int MoveToNext();void OutPrint();};class Hanio{Stack m_stack[3];int m_num; //盘数int m_steps; //移动次数int m_times; //完成所用时间void print(char ch,int n);public:Hanio(int num=3);~Hanio() {};void GameStart();bool MoveFromTo(int x,int y); //从x号盘移动到y号盘void DrawPaletes(char ch='*'); //打印3个堆的盘子bool IsFinished() ; //结束返回TURE;int Solve(char from,char to,char auxiliary,int n); //求解其解法路径};#endif//hanio.cpp#include "hanio.h"#include <iostream>#include<cstdlib>#include<cstring>#include<cctype>#include<windows.h>Stack::Stack(){m_top=-1;m_index=m_top;for(int i=0;i<MAX;i++)m_node[i]=0;}bool Stack::Push(int data){if(Isfull())return false;m_top++;m_node[m_top]=data;m_index=m_top;return true;}bool Stack::Pop(int *pData){if(Isempty())return false;*pData=m_node[m_top];m_node[m_top]=0;m_top--;m_index=m_top;return true;}int Stack::MoveToNext(){int temp=m_index;m_index--;return m_node[temp];}void Stack::OutPrint(){if(m_top!=-1){for(int i=0;i<=m_top;i++)std::cout<<"["<<m_node[i]<<"]";}}///////////////////////////////////////Hanio::Hanio(int num){m_num=num;m_steps=0;m_times=0;for(int i=num;i>=1;i--)m_stack[0].Push(i);//m_stack[0].OutPrint();}void Hanio::print(char ch,int n){for(int i=1;i<=n;i++)std::cout<<ch;}void Hanio::DrawPaletes(char ch){int max;max=m_stack[0].Size()>m_stack[1].Size() ? m_stack[0].Size() : m_stack[1].Size();max=m_stack[2].Size()>max ? m_stack[2].Size() : max;//std::cout<<"Max:"<<max<<std::endl;m_stack[0].SetIndex(max-1);m_stack[1].SetIndex(max-1);m_stack[2].SetIndex(max-1);for(int i=1;i<=max;i++){int data1=m_stack[0].MoveToNext();int data2=m_stack[1].MoveToNext();int data3=m_stack[2].MoveToNext();if(data1==0)print(' ',20);else{print(' ',10-data1);print(ch,2*data1);print(' ',10-data1);}if(data2==0)print(' ',20);else{print(' ',10-data2);print(ch,2*data2);print(' ',10-data2);}if(data3==0)print(' ',20);else{print(' ',10-data3);print(ch,2*data3);print(' ',10-data1);}std::cout<<std::endl;}}bool Hanio::MoveFromTo(int x,int y){m_steps++; //计算所走的步数if(m_stack[x].Isempty()){std::cout<<x<<" pallete is empty ! continue !"<<std::endl; std::cin.get();return false;}if(m_stack[y].Isempty()){int data;m_stack[x].Pop(&data);m_stack[y].Push(data);return true;}else{if(m_stack[x].TopValue()>m_stack[y].TopValue()){std::cout<<"The board can't move from "<<x<<" plate to " <<y<<" plate!"<<std::endl;std::cin.get();return false;}else{int data;m_stack[x].Pop(&data);m_stack[y].Push(data);return true;}}}bool Hanio::IsFinished(){return m_stack[2].Top()==m_num-1;}void Hanio::GameStart(){using namespace std;UINT StartTime=::GetTickCount();UINT EndTime;while(1){system("cls");print('-',80);cout<<"steps: "<<m_steps; print(' ',20);cout<<"Used time: "<<m_times<<endl;print('-',80);cout<<endl; cout<<endl; print(' ',10); cout<<"A";print(' ',19); cout<<"B"; print(' ',19);cout<<"C"<<endl<<endl;Hanio::DrawPaletes();cout<<endl; cout<<endl;print('-',80);//测试游戏是否结束if(Hanio::IsFinished()){cout<<"你好强呀!从今天开始,维护世界和平的任务就交给你那!"<<endl;cin.get();break;}//输入命令并左相应的处理char szCommand[50];cout<<">>";cin.getline(szCommand,50);if(stricmp(szCommand,"QUIT")==0 || stricmp(szCommand,"Q")==0)break;if(stricmp(szCommand,"HELP")==0 || stricmp(szCommand,"H")==0){cout<<" 本游戏说明:"<<endl;cout<<" 该游戏由DAVID用C++编程,花费了一个多下午的时间呢!!!,由命令行来控制铁饼的移动:"<<endl;cout<<" QUIT / Q : 退出程序"<<endl;cout<<" HELP / H : 查看该说明"<<endl;cout<<" XY : X,Y的取值为A,B,C,意思时把X木桩最上面的铁饼移到Y 木桩"<<endl;cout<<" SOLVE / S : 显示求解该问题(移动铁饼)的最优路径..."<<endl; cin.get();}char ch1=toupper(szCommand[0]);char ch2=toupper(szCommand[1]);if( ch1=='A' && ch2=='B')Hanio::MoveFromTo(0,1);else if ( ch1=='A' && ch2=='C')MoveFromTo(0,2);else if ( ch1=='B' && ch2=='A')MoveFromTo(1,0);else if ( ch1=='B' && ch2=='C')MoveFromTo(1,2);else if ( ch1=='C' && ch2=='A')MoveFromTo(2,0);else if ( ch1=='C' && ch2=='B')MoveFromTo(2,1);else{cout<<"Bad command !"<<endl;cin.get();}//统计游戏所用时间EndTime=GetTickCount();m_times=(EndTime-StartTime)/1000;}}int Hanio::Solve(char from,char to,char auxiliary,int n) {if(n==1)return 0;}//main.cpp#include<iostream>#include"hanio.h"#include<cstdlib>using namespace std;int StartPicture();//返回选择的盘数int main(){int number;number=StartPicture();Hanio hanio(number);hanio.GameStart();return 0;}void print(char ch,int n){for(int i=1;i<=n;i++)std::cout<<ch;}int StartPicture(){using namespace std;int number;system("cls");system("color fc");print(' ',20);print('-',25);cout<<endl;print(' ',20);cout<<" Hanio(汉诺塔)"<<endl;print(' ',20);print('-',25);cout<<endl;print(' ',40);print('-',5);cout<<"By David"<<endl;print('=',80);cout<<" 相传在某一座古庙中有3根木桩,有24个铁盘由小到大放置在一根木柱上,庙中流传者一个传说:\"如果能把24个铁盘, 从一根木桩移动到另一个木桩,且必须遵守如下规则:"<<endl;cout<<endl;print(' ',5);cout<<"1. 每天只能动一个盘,而且只能从最上面的铁盘开始搬动."<<endl; print(' ',5);cout<<"2. 必须维持较小的铁盘在上方的原则"<<endl;cout<<endl;cout<<"这两个原则,则当24个铁盘完全般到另一个木桩时,世界就回永久和平!!"<<endl;cout<<"游戏的玩法可以在命令行中输入HELP查看"<<endl;cout<<endl;cout<<endl;cout<<endl;cout<<endl;cout<<endl;cout<<"再此输入你要搬的铁盘数(建议在1--10值间,太多回花费很长时间的)"<<endl;print('=',80);cout<<">>";cin>>number;cin.get();system("cls");return number;}。

汉诺塔问题是一个经典的递归问题。

在汉诺塔问题中，有三根柱子，第一根柱子上从下到上放着n 个盘子，目标是将这些盘子从第一根柱子移动到第三根柱子上，并且只能每次移动一个盘子，并且不能将一个较大的盘子放在较小的盘子上面。

以下是一个使用 C 语言实现的汉诺塔问题的示例代码：```c#include <stdio.h>void hanoi(int n, char A, char B, char C) {if (n == 1) {printf("Move disk 1 from %c to %c\n", A, C);return;}hanoi(n - 1, A, C, B);printf("Move disk %d from %c to %c\n", n, A, C);hanoi(n - 1, B, A, C);}int main() {int n = 3; // 盘子数量hanoi(n, 'A', 'B', 'C'); // 调用递归函数，将盘子从A 柱子移动到 C 柱子，B 柱子作为辅助柱子return 0;}```在这个代码中，我们定义了一个`hanoi` 函数来递归地解决汉诺塔问题。

在`hanoi` 函数中，我们首先检查盘子数量是否为1，如果是，则直接将盘子从起始柱子移动到目标柱子。

否则，我们使用两个辅助柱子来将n-1 个盘子从起始柱子移动到第二个辅助柱子上，然后将最后一个盘子从起始柱子移动到目标柱子上，最后再将n-1 个盘子从第二个辅助柱子移动到目标柱子上。

在`main` 函数中，我们定义了盘子数量n，并调用了`hanoi` 函数来解决问题。

【C语⾔程序设计】汉诺塔问题，⽤C语⾔实现汉诺塔！汉诺塔问题是指：⼀块板上有三根针 A、B、C。

A 针上套有 64 个⼤⼩不等的圆盘，按照⼤的在下、⼩的在上的顺序排列，要把这 64 个圆盘从 A 针移动到 C 针上，每次只能移动⼀个圆盘，移动过程可以借助 B 针。

但在任何时候，任何针上的圆盘都必须保持⼤盘在下，⼩盘在上。

从键盘输⼊需移动的圆盘个数，给出移动的过程。

算法思想对于汉诺塔问题，当只移动⼀个圆盘时，直接将圆盘从 A 针移动到 C 针。

若移动的圆盘为 n(n>1)，则分成⼏步⾛：把 (n-1) 个圆盘从 A 针移动到 B 针（借助 C 针）；A 针上的最后⼀个圆盘移动到 C 针；B 针上的 (n-1) 个圆盘移动到 C 针（借助 A 针）。

每做⼀遍，移动的圆盘少⼀个，逐次递减，最后当 n 为 1 时，完成整个移动过程。

因此，解决汉诺塔问题可设计⼀个递归函数，利⽤递归实现圆盘的整个移动过程，问题的解决过程是对实际操作的模拟。

程序代码#include <stdio.h>int main(){int hanoi(int,char,char,char);int n,counter;printf("Input the number of diskes：");scanf("%d",&n);printf("\n");counter=hanoi(n,'A','B','C');return0;}int hanoi(int n,char x,char y,char z){int move(char,int,char);if(n==1)move(x,1,z);else{hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);}return0;}int move(char getone,int n,char putone){static int k=1;printf("%2d:%3d # %c---%c\n",k,n,getone,putone);if(k++%3==0)printf("\n");return0;}调试运⾏结果：当移动圆盘个数为 3 时，具体移动步骤如下所⽰：Input the number of diskes：31: 1 # A---C2: 2 # A---B3: 1 # C---B4: 3 # A---C5: 1 # B---A6: 2 # B---C7: 1 # A---C总结：本实例中定义的 hanoi() 函数是⼀个递归函数，它有四个形参"n""x""y""z"。

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的关系图，并进行分析。

5.代码设计：Hanio.cpp#include"stdafx.h"#include<stdlib.h>#include<stdio.h>#include<iostream>void hanoi(int n,char x,char y,char z){if(n==1){printf("从%c->搬到%c\n",x,z);}else{hanoi(n-1,x,z,y);printf("从%c->%c搬到\n",x,z);hanoi(n-1,y,x,z);}}void main(){int m ;printf("input the number of diskes:");scanf("%d",&m);printf("The step to moving %3d diskes:",m);hanoi(m,'a','b','c');}自定义头文件：#pragma once#include"targetver.h"#include<stdio.h>#include<tchar.h>结果如下：6.递归应用中的Hanoi塔问题分析1）Hanoi塔问题中函数调用时系统所做工作一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事：①将所有的实参、返回地址等信息传递给被调用函数保存。

XXXX大学计算机科学与技术学院课程设计报告2012 — 2013学年第一学期课程名称C/C++高级语言程序设计课程设计设计题目小游戏和图形处理汉诺塔问题学生姓名XXX学号XXXXXXX专业班级XXXXXXXXXXX指导教师XX2012 年X 月XX 日目录一、课程设计问题描述 (1)1、课程设计题目 (1)2、设计任务要求 (1)二、总体设计 (1)1、设计思路 (1)2、汉诺塔求解流程图 (2)三、详细设计 (2)1、汉诺塔问题描述 (2)2、算法分析 (3)3、实现递归的条件 (4)4、用C语言实现 (4)四、程序运行结果测试与分析 (4)1、打开Microsoft Visual C++ 6.0操作平台输入以下的源代码 (4)2、编译源代码 (5)3、组建 (5)4、执行 (5)5、运行结果 (6)6、按任意键结束程序 (7)五、结论与心得 (7)六、参考文献 (8)七、附录：程序源代码 (8)一、课程设计问题描述1、课程设计题目汉诺塔问题2、设计任务要求输入盘子数（2个以上有效），移动速度，开始演示汉诺塔移动的步骤，要求：盘子A，B，C柱需要自己绘制，初始时盘子在A柱上通过B柱最终移动到C 柱上，显示出盘子在几个柱之间的移动过程。

二、总体设计1、设计思路对于一个类似的这样的问题，任何一个人都不可能直接写出移动盘子的每一个具体步骤。

可以利用这样的统筹管理的办法求解：我们假设把该任务交给一个僧人，为了方便叙述，将他编号为64。

僧人自然会这样想：假如有另外一个僧人能有办法将63个盘子从一个座移到另一个座，那么问题就解决了，此时僧人A B C64只需这样做：(1).命令僧人63将63个盘子从A座移到C座(2).自己将最底下的最大的一个盘子从A座移到C座(3).再命令僧人63将63个盘子从B座移到C座为了解决将63个盘子从A座移到B座的问题，僧人63又想：如果能再有一个僧人62能将62个盘子移动到另一座，我就能将63个盘子从A座移动到B座。

c语言课程设计汉诺塔一、教学目标本节课的教学目标是让学生掌握汉诺塔问题的解法，理解其背后的算法思想，培养逻辑思维能力和编程能力。

具体分为以下三个部分：1.知识目标：使学生了解汉诺塔问题的定义、解法和算法思想，理解递归算法的原理及其在解决汉诺塔问题中的应用。

2.技能目标：培养学生运用C语言实现汉诺塔问题的解决方案，提高编程实践能力。

3.情感态度价值观目标：培养学生独立思考、合作交流的学习习惯，增强对计算机科学的兴趣和热情。

二、教学内容本节课的教学内容主要包括以下几个部分：1.汉诺塔问题的定义和解法：介绍汉诺塔问题的背景，讲解其解法及步骤。

2.递归算法的原理：讲解递归算法的基本概念、特点及其在解决汉诺塔问题中的应用。

3.C语言实现汉诺塔问题：引导学生运用C语言编写汉诺塔问题的解决方案，并进行调试和优化。

4.算法分析和改进：分析汉诺塔问题的算法复杂度，探讨如何优化算法性能。

三、教学方法为了达到本节课的教学目标，采用以下几种教学方法：1.讲授法：讲解汉诺塔问题的定义、解法和递归算法的原理。

2.案例分析法：分析实际案例，让学生了解递归算法在解决汉诺塔问题中的应用。

3.实验法：引导学生动手实践，用C语言实现汉诺塔问题的解决方案。

4.讨论法：学生进行小组讨论，分享算法优化思路，培养合作交流能力。

四、教学资源本节课的教学资源包括以下几个方面：1.教材：选用《C程序设计》等相关教材，为学生提供理论知识的学习参考。

2.参考书：推荐《算法导论》等参考书籍，帮助学生深入了解算法原理。

3.多媒体资料：制作PPT、教学视频等多媒体资料，辅助学生理解和记忆知识点。

4.实验设备：为学生提供计算机、编程环境等实验设备，方便学生动手实践。

五、教学评估本节课的教学评估主要包括以下几个方面：1.平时表现：评估学生在课堂上的参与度、提问回答等情况，占比20%。

2.作业：评估学生完成的汉诺塔问题相关练习，包括C语言代码编写和调试，占比30%。

简单的汉诺塔问题解法代码以前学东西不扎实，现在捡捡也好，汉诺塔本是C语⾔开门就学的东西，不过上课那会⼉真⼼听不懂，直到⼤⼆了，才明⽩那是咋回事，我感觉的编程，真的是⼀张窗户纸，不过捅破要花时间理解吸收。

题⽬描述：有⼀个塔，塔内有A,B,C三个柱⼦。

起初，A柱上有n个盘⼦，依次由⼤到⼩、从下往上堆放，要求将它们全部移到C柱上；在移动过程中可以利⽤B柱，但每次只能移到⼀个盘⼦，且必须使三个柱⼦上始终保持⼤盘在下，⼩盘在上的状态。

要求编程输出移动的步骤。

代码如下：复制代码代码如下:#include<stdio.h>int move(char one,char two)//这个函数就是为了输出的结果直观显⽰出来，⽐如只有⼀个盘⼦时，输出a-->c. 就这样，把移动n个盘⼦每个步骤显⽰出来{printf("%c --> %c\n",one,two);}int hanoi(int n,char one,char two,char three)//是核⼼函数了{int move(char one,char two);if(n==1)//当只有⼀个盘⼦时，直接从a柱移到c柱就好，也是递归程序的⼀个出⼝move(one,three);else{ //盘⼦⼤于⼀时hanoi(n-1,one,three,two);//先借助c柱把上⾯的n-1个盘⼦从a柱全部移动到b柱move(one,three); //这时a柱只剩下⼀个盘⼦了，移动到c柱即可hanoi(n-1,two,one,three);//将b柱剩下的n-1个盘⼦借助a柱移动到c柱，任务也就完成了}}int main(){int n;char a,b,c;while(scanf("%d",&n)!=EOF)//可以输⼊多组数据检验结果hanoi(n,'a','b','c');}。

汉诺塔问题的程序实现汉诺塔问题的程序实现实验⽬的：运⽤程序解决汉诺塔（hanoi）问题。

汉诺塔问题：假设有3个分别命名为A，B，C的塔座，在塔座A上插有n个直径⼤⼩各不相同，依⼩到⼤编号为1,2....,n的圆盘。

现要求将A轴上的n个圆盘移到C并仍按同样顺序叠排，圆盘按以下规则（1）每次只能⼀动⼀个盘⼦（2）圆盘可以插在A，B，C中任⼀个塔座上（3）任何时刻都不能将⼀个较⼤的圆盘压在较⼩的圆盘之上。

A B C实验分析：汉诺塔问题可以规划为⼀个递归的问题予以分析，将n个盘⼦从A针移动到C 针可进⾏3个步骤:(1)将A上n-1的个盘⼦移到B针上；(2)把A针最后1个盘⼦移到C针上；(3)再把B盘⼦上的n-1个移到C针上。

实验过程：#includeusing namespace std;void main(){void hanoi(int m,char A,char B,char C); //A代表初始柱⼦，B代表辅助柱⼦，C代表⽬标柱⼦int m;printf("请输⼊盘⼦的个数:");scanf("%d", &m);printf("当盘⼦的个数为%d时移动的步骤是:\n",m);hanoi(m,'A','B','C');}void hanoi(int n,char X,char Y,char Z){void move(char X,char Z );if(n==1)move(X,Z);else{hanoi(n-1,X,Z,Y);move(X,Z);hanoi(n-1,Y,X,Z);}}void move(char x,char y){printf("%c-->%c\n",x,y);}过程：A代表初始柱⼦，B代表辅助柱⼦，C代表⽬标柱⼦。

⽽a代表第⼀根柱⼦,b代表第⼆根柱⼦,c代表第三根柱⼦。

一、实验目的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. 非递归解法除了递归解法，我们还可以使用栈来实现汉诺塔问题的非递归解法。

c语言程序汉诺塔优秀教学设计C语言程序汉诺塔优秀教学设计引言：汉诺塔是一个经典的数学谜题，也是计算机科学中的经典算法之一。

通过教学学生编写C语言程序实现汉诺塔问题，可以锻炼学生的逻辑思维能力、编程能力和解决问题的能力。

本文将提供一套优秀的教学设计，一步一步引导学生完成汉诺塔程序的编写。

一、理解汉诺塔问题首先，我们需要向学生介绍汉诺塔问题的背景和规则。

给定三个柱子A、B和C，其中柱子A上有多个大小不等的圆盘，我们的目标是将所有的圆盘从A柱子上移动到C柱子上，并且保证移动过程中大圆盘不会放在小圆盘上。

二、解答汉诺塔问题的思路1. 观察问题首先，我们可以让学生观察当圆盘数量为1、2、3的时候，问题的解决方法，以帮助他们理解问题规律。

2. 分解问题然后，我们引导学生发现，并分解出一个子问题：如何将n-1个圆盘从A柱子通过B柱子移动到C柱子。

这一步是解决该问题的关键，也是递归思想的应用。

3. 递归思想我们通过递归思想解决子问题：将n-1个圆盘从A柱子通过B柱子移动到C柱子。

递归的停止条件是当圆盘数量为1时，直接将其从A柱子移动到C柱子。

4. 移动圆盘接下来是具体的移动圆盘的操作。

我们可以定义一个函数move()，通过将圆盘从一个柱子移动到另一个柱子来实现。

该函数应该接受三个参数：源柱子、目标柱子和经由的柱子。

我们通过调用该函数来实现圆盘的移动。

三、实现C语言汉诺塔程序在介绍完解题思路后，我们引导学生一步一步实现C语言的汉诺塔程序。

1. 定义函数move()首先，我们可以引导学生定义一个函数move()，该函数接受三个参数：源柱子、目标柱子和经由的柱子。

例如，函数定义可以如下所示：void move(char from, char to, char via);2. 实现递归停止条件然后，我们引导学生实现递归停止条件。

当圆盘数量为1时，我们将其从源柱子移动到目标柱子。

例如，可以使用如下语句实现：if(n == 1){printf("Move disk from c to c\n", from, to);return;}3. 递归调用move()函数接下来，我们需要在递归的情况下调用move()函数。

汉诺塔问题非递归算法
汉诺塔问题是一个经典的递归算法问题，但也可以使用非递归的方式解决。

下面是一种非递归算法的实现思路：
1. 创建三个栈，分别命名为A、B、C，表示三个柱子。

2. 对于n个盘子的汉诺塔问题，首先将所有盘子按从大到小的顺序依次压入栈A中。

3. 定义一个变量count，用来记录移动步数，初始值为0。

4. 如果n为奇数，则执行步骤5；如果n为偶数，则执行步骤6。

5. 循环执行以下操作：
5.1 将栈A的栈顶元素弹出，放入栈B中；
5.2 将栈A中剩余的n-1个盘子移到栈C中；
5.3 将栈B中的盘子移到栈C中；
5.4 将栈A作为辅助栈，栈B作为目标栈，栈C作为源栈，重复步骤5.1~5.3，直到栈A为空。

6. 循环执行以下操作：
6.1 将栈A的栈顶元素弹出，放入栈C中；
6.2 将栈A中剩余的n-1个盘子移到栈B中；
6.3 将栈C中的盘子移到栈B中；
6.4 将栈A作为辅助栈，栈C作为目标栈，栈B作为源栈，重复步骤6.1~6.3，直到栈A为空。

通过上述非递归算法，可以按照汉诺塔问题的规则将所有的盘子从栈A移动到栈B，并记录移动的步骤数。

07141326汉诺塔-课程设计汉诺塔课程设计报告⽬录⼀、需求分析 (3)⼆、概要设计 (4)三、详细设计 (6)四、测试与分析 (7)五、总结 (7)六、附录：源程序清单 (8)⼀、需求分析1．1问题描述汉诺塔（⼜称河内塔）问题是印度的⼀个古⽼的传说。

开天辟地的神勃拉玛在⼀个庙⾥留下了三根⾦刚⽯的棒，第⼀根上⾯套着64个圆的⾦⽚，最⼤的⼀个在底下，其余⼀个⽐⼀个⼩，依次叠上去，庙⾥的众僧不倦地把它们⼀个个地从这根棒搬到另⼀根棒上，规定可利⽤中间的⼀根棒作为帮助，但每次只能搬⼀个，⽽且⼤的不能放在⼩的上⾯。

这是⼀个著名的问题，⼏乎所有的教材上都有这个问题。

由于条件是⼀次只能移动⼀个盘，且不允许⼤盘放在⼩盘上⾯，所以64个盘的移动次数是：18，446，744，073，709，551，615这是⼀个天⽂数字，若每⼀微秒可能计算(并不输出)⼀次移动，那么也需要⼏乎⼀百万年。

我们仅能找出问题的解决⽅法并解决较⼩N值时的汉诺塔，但很难⽤计算机解决64层的汉诺塔。

后来，这个传说就演变为汉诺塔游戏: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座上。

1．2基本要求（1）输⼊的形式和输⼊值的范围：输⼊圆盘的数量，类型为整型，⼤于零。

（2）输出的形式：运⾏结果为⽤字母表⽰移动盘⼦的⽅案，⽽并⾮是真正移动盘⼦。

(3) 程序所能达到的功能；输⼊圆盘数量为定值时的移盘⽅案。

帮助我们更清晰的理解汉诺塔问题，及递归调⽤的应⽤。

汉诺塔问题的程序实现（hanoi塔）问题重述：有三根柱A、B、C，在柱A上有N块盘⽚，所有盘⽚都是⼤的在下⾯，⼩⽚能放在⼤⽚上⾯。

现要将A上的N块盘⽚移到C柱上，每次只能移动⼀⽚，⽽且在同⼀根柱⼦上必须保持上⾯的盘⽚⽐下⾯的盘⽚⼩，输⼊任意的N，输出移动⽅法。

(注意：这是⼀个古⽼的传说，传说是如果把64个盘⼦由A柱移到了C柱的话，那么世界末⽇就到了，事实上如果要把64个盘⼦从A柱移到C柱的话，即使⽤计算机运算，也要计算数亿年，所以这个预⾔未必不是真实。

)【分析】我们可以这样考虑，当n=1时，我们只要直接将A柱的盘⼦移到C柱，当n>1时，我们可以先把n-1个盘⼦由A柱通过C柱移到B 柱，此时就可以把A柱剩下的最后⼀个盘⼦直接移到C柱，这样接下来只要把n-1个盘⼦通过A柱移到C 柱即可，如果就构成了递归的思路，我们可以定义个移动过程mov(n,a,b,c)表⽰将n个盘⼦从a通过b移到c1.只要求输出搬运的次数#includeusing namespace std;int m=0;void move(){m++;}void I(int n){if(n==1)move();else{I(n-1);move();I(n-1);}}int main(){I(3);cout<cout<<"输出完毕！"<return 0;}更加简单的⽅法！#includeusing namespace std;int fact(int n){if(n==1)return(1);elsereturn((2*fact(n-1)+1));}int main(){cout<}2.不仅要求输出搬运的次数，⽽且要输出每个步骤的详细搬运#includeusing namespace std;int m=0;void Move(int n,char x,char y){cout<<"把"<m++;}void Hannoi(int n,char a,char b,char c){if(n==1)Move(1,a,c);else{Hannoi(n-1,a,c,b);Move(n,a,c);Hannoi(n-1,b,a,c);}}int main(){int i;cout<<"请输⼊圆盘数"<cin>>i;Hannoi(3,'a','b','c');cout<<"总的搬运次数"<cout<<"输出完毕！"<return 0;}}另外⼀种不利⽤递归的解法（很抱歉，我⾃⼰也没调出来，实在太复杂了）#includeusing namespace std;//圆盘的个数最多为64const int MAX = 1;//⽤来表⽰每根柱⼦的信息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^yvoid 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; ita[0].s[i] = n - i;//柱⼦B，C 上开始没有没有圆盘ta[1].top = ta[2].top = 0;for (int j=0; jta[1].s[j] = ta[2].s[j] = 0;//若n 为偶数，按顺时针⽅向依次摆放A B Cif (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; isum *= 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; }}}}补充知识：【典型例题1】求阶乘n!#includeusing namespace std;int fact(int n){if(n==0)return(1);elsereturn(n*fact(n-1)); }int main(){cout<。

本微课适用范围如下所示：课程所属学科：计算机适用专业：计算机应用技术、计算机软件工程、电子信息适用课程：C语言程序设计、C++程序设计、JAVA程序设计、数据结构适用对象：有一定编程基础的同学《汉诺塔问题》微课教案学院(部)：软件学院系（教研室）：网络教研授课教师：杨珺职称：副教授时间复杂度为：O(2n)程序实现部分汉诺塔问题的递归实现：#include<stdio.h>void hanoi(int n,char A,char B,char C){if(n==1){printf("Move disk %d from %c to %c\n",n,A,C);}else{hanoi(n-1,A,C,B);printf("Move disk %d from %c to %c\n",n,A,C);hanoi(n-1,B,A,C);}}main(){int n;printf("请输入数字n以解决n阶汉诺塔问题：\n");scanf("%d",&n);hanoi(n,'A','B','C');}●汉诺塔算法的非递归实现C++源代码#include <iostream>using namespace std;//圆盘的个数最多为64const 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^yvoid 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 (int i=0; i<n; i++)ta[1].s[i] = ta[2].s[i] = 0;//若n为偶数，按顺时针方向依次摆放 A B Cif (n%2 == 0){ta[1].name = 'B';ta[2].name = 'C';}else //若n为奇数，按顺时针方向依次摆放 A C Bta[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;}}}}汉诺塔问题的非递归实现#include <stdio.h>#include <math.h>#include <stdlib.h>//第0位置是柱子上的塔盘数目int zhua[100]={0},zhub[100]={0},zhuc[100]={0};char charis(char x,int n)//左右字符出现顺序固定,且根据n值奇偶而不同{switch(x){case 'A':return (n%2==0)?'C':'B';case 'B':return (n%2==0)?'A':'C';case 'C':return (n%2==0)?'B':'A';default:return '0';}}void print(char lch,char rch)//打印字符{if(lch=='A'){switch(rch){case 'B':zhub[0]++;zhub[zhub[0]]=zhua[zhua[0]]; zhua[zhua[0]]=0;zhua[0]--;break;case 'C':zhuc[0]++;zhuc[zhuc[0]]=zhua[zhua[0]]; zhua[zhua[0]]=0;zhua[0]--;break;default:break;}}if(lch=='B'){switch(rch){case 'A':zhua[0]++;zhua[zhua[0]]=zhub[zhub[0]]; zhub[zhub[0]]=0;zhub[0]--;break;case 'C':zhuc[0]++;zhuc[zhuc[0]]=zhub[zhub[0]]; zhub[zhub[0]]=0;zhub[0]--;break;default:break;}}if(lch=='C'){switch(rch){case 'A':zhua[0]++;zhua[zhua[0]]=zhuc[zhuc[0]];zhuc[zhuc[0]]=0;zhuc[0]--;break;case 'B':zhub[0]++;zhub[zhub[0]]=zhuc[zhuc[0]];zhuc[zhuc[0]]=0;zhuc[0]--;break;default:break;}}printf("\t");int i;printf("(");for(i=1;i<=zhua[0];i++)printf(" %d ",zhua[i]);printf(")");printf("(");for(i=1;i<=zhub[0];i++)printf(" %d ",zhub[i]);printf(")");printf("(");for(i=1;i<=zhuc[0];i++)printf(" %d ",zhuc[i]);printf(")");printf("\n");}void Hannuo(int n){//分配2^n个空间bool *isrev;isrev=(bool *)malloc(sizeof(bool)*(int)pow(2,n)); for(int i=1;i<pow(2,n);i++)//循环计算是否逆序for(int ci=2;ci<=n;ci++){for(int zixh=(int)pow(2,ci-1);zixh<pow(2,ci);zixh+=4) //初始值重复一次，自增值可加4，减少循环次数。