数据结构--汉诺塔问题 清疚 2023-07-03 14:29 109阅读 0赞 # 数据结构–汉诺塔问题 # 我列举了两种解法—递归和非递归 1、这是递归解法 #include<iostream> using namespace std; int j = 1; void move(char a, char c) { cout << j++ << " " << a << "--->" << c << endl; } void Hanio(int n,char a,char b,char c) { if (n == 1) { move(a, c); return; } Hanio(n - 1, a, c,b); move(a, c); Hanio(n - 1, b, a,c); } int main() { int n; cin >> n; cin.get(); Hanio(n, 'a', 'b', 'c'); cin.get(); return 0; } ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70] 2、非递归解法,使用堆栈 #include<iostream> using namespace std; const int Maxsize = 100; typedef struct { //建立一个汉诺塔模型,n是盘个数,ABC是三个柱子 int N; char A; char B; char C; }Mode; typedef struct { //建立一个堆栈 Mode Data[Maxsize]; int Top; }Stack; Mode ERROR; void Push(Stack * Ptr, Mode item) //压进堆栈 { if (Ptr->Top == Maxsize - 1)return; else { Ptr->Data[++(Ptr->Top)] = item; return; } } Mode Pop(Stack * Ptr) //弹出堆栈 { if (Ptr->Top == -1)return ERROR; else { Ptr->Top--; return Ptr->Data[Ptr->Top + 1]; } } void Hanio(int n) //求汉诺塔解决子程序 { Mode P, toPush; Stack S; P.N = n; //建立一个汉诺塔型 的结构体,n是盘数 P.A = 'a'; P.B = 'b'; P.C = 'c'; S.Top = -1; Push(&S, P); //(n,a,b,c)可以分解为三个问题(n-1,a,b,c)(2,a,b,c)(n-1,b,a,c),然后反着压进堆栈 while (S.Top != -1) //看栈是不是空的 { P = Pop(&S); if (P.N == 1) cout << P.A << "--->" << P.C; else { toPush.N = P.N - 1; toPush.A = P.B; toPush.B = P.A; toPush.C = P.C; Push(&S, toPush); toPush.N = 1; toPush.A = P.A; toPush.B = P.B; toPush.C = P.C; Push(&S, toPush); toPush.N = P.N - 1; toPush.A = P.A; toPush.B = P.C; toPush.C = P.B; Push(&S, toPush); } } } int main() { /*int n; cin >> n;*/ Hanio(3); cin.get(); return 0; } 3、这是百度上的一个问题答案 #include <fstream> #include <iostream> using namespace std; ofstream fout("out.txt"); void Move(int n,char x,char y) { fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl; } 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() { fout<<"以下是7层汉诺塔的解法:"<<endl; Hannoi(7,'a','b','c'); //调用 fout.close(); cout<<"输出完毕!"<<endl; return 0; ## 【说明】 ## 汉诺塔使用递归的方法来实现的 可能你对递归还没理解透,反正记住,程序总是一步一步的按顺序执行,有调用函数就先在调用的地方设个断点,转入函数执行,执行完了又返回断点,万变不离其宗! 程序执行的顺序 Hannoi(7,‘a’,‘b’,‘c’);这里调用函数,转入函数执行并传入参数n=7 第一步,执行判断语句,根据n的值进入else执行 第二步,执行Hannoi(n-1,a,c,b);这时是调用函数本身,也就是所谓的递归了,你看传入的值n-1,相当于传入n=6,还有a,c,b,的值,这个要注意顺序,在调用的时候a,c,b的值是第一次传入的值 第三步,执行Hannoi(int n,char a,char b,char c)函数,这点能理解吧,这次传入的值n=6了,但是a,b,c,的值相对于第一次的值有改变了哦,可以理解成,a(2)=a(1),b(2)=c(1),c(2)=b(1),这里括号里代表函数调用的次数,其实这里最容易弄混的就是,a,b,c的值,自己用本子把每次传入的值的a,b,c按传入顺序列出来,会容易理解些 同样,执行判断,n>1进入else,按顺序执行,先执行Hannoi(n-1,a,c,b);然后又是调用本身,注意传入的值,是a(2),c(2),b(2),又转入去执行Hannoi(int n,char a,char b,char c)函数,这时接收的值a(3)=a(2),b(3)=c(2),c(3)=b(2),就像在兜圈子是吧,没错。后面你自己做张表来理一下。 这样兜圈子直到n=1。你看Hannoi(n-1,a,c,b);每次n都是减了1的,所以n-1次递归的时候,就直接执行if(n==1)里面的了,终于有所改变了是吧,他执行的是Move(1,a,c); 也就是输出函数,执行完Move(int n,char x,char y) 返回原来的调用的那个断点。继续向后。没有语句了,就返回上次调用的函数,上次调用Hannoi(int n,char a,char b,char c)是谁呢,就是n-2次的Hannoi(int n,char a,char b,char c)中的Hannoi(n-1,a,c,b);调用的他啊,返回到这里,继续向后又遇到Move(n,a,c); 这里不用讲解了吧,输出后返回来,继续向后执行Hannoi(n-1,b,a,c); 新的递归开始了,看你再列个新的表理一下呢,注意传入的值和他的顺序,还有n的值这时是多少。 其实我的讲解你可能看的也不是很清楚,关键是要理解到递归他无非就是调用自己,调用完返回就是返回上次调用的地方,也是他自己,只是俩次的函数使用中的值是不一样的,这个值呢,最好拿笔记下来,并写个次数才容易理解和分析。 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200207120135677.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk=,size_16,color_FFFFFF,t_70
相关 汉诺塔问题 import java.util.Scanner; / 汉诺塔问题 不考虑中转,只考虑起始柱子到目标柱子的移动 记住始终一点:中间一个不管是啥柱 素颜马尾好姑娘i/ 2022年09月30日 00:32/ 0 赞/ 149 阅读
相关 汉诺塔问题 1.汉诺塔问题:如果将n个盘子(由小到大)从a通过b,搬到c,搬运过程中不能出现小盘子在大盘子下面的情况。 分析:这个一个递归问题。只要将n-1个盘子从a通过c(没有中间点肯 刺骨的言语ヽ痛彻心扉/ 2022年08月20日 10:14/ 0 赞/ 213 阅读
相关 汉诺塔问题 “汉诺塔问题”的Java重写思路:典型的递归问题。 “汉诺塔问题”的Java重写代码: public class Hanoi { 不念不忘少年蓝@/ 2022年07月21日 05:42/ 0 赞/ 144 阅读
相关 汉诺塔问题 汉诺塔比较经典的实现是利用递归,但也可以利用堆栈。 题意理解:有A,B,C三个柱子,将A柱子上的N个盘子(从大到小排列)移到C柱子上,每次只允许移动一个盘子,并且保证每个柱子 た 入场券/ 2022年05月26日 12:14/ 0 赞/ 160 阅读
相关 汉诺塔问题 汉诺塔 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵 爱被打了一巴掌/ 2022年05月18日 00:40/ 0 赞/ 243 阅读
相关 数据结构之汉诺塔 汉诺塔栈 include <stdio.h> include <stack> //递归实现 void hanoi_W 落日映苍穹つ/ 2022年05月06日 16:28/ 0 赞/ 157 阅读
相关 汉诺塔问题 问题描述: 相传在[古印度][Link 1]圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺 向右看齐/ 2022年04月17日 05:12/ 0 赞/ 282 阅读
相关 汉诺塔问题 汉诺塔问题是经典的递归问题,它的递归类型是:求解问题的方法是递归的。 解题思路: 1. 首先将n-1个盘子从X借助Z移动到Y。 2. 将第n个盘子从X移动到Z。 3. ゝ一世哀愁。/ 2022年03月15日 15:48/ 0 赞/ 209 阅读
相关 汉诺塔问题 汉诺塔(Tower of Hanoi)源于印度传说中,大梵天创造世界时造了三根金钢石柱子,其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新 梦里梦外;/ 2021年09月28日 17:06/ 0 赞/ 452 阅读
相关 汉诺塔问题 汉诺塔问题 -------------------- 文章目录 汉诺塔问题 1. 问题描述 2. 问题分析 3. 代 刺骨的言语ヽ痛彻心扉/ 2021年09月23日 23:26/ 0 赞/ 332 阅读
还没有评论,来说两句吧...