7-8 汉诺塔的非递归实现

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

                 本文链接：[https://blog.csdn.net/shiliang97/article/details/96485180](https://blog.csdn.net/shiliang97/article/details/96485180)

?点这里

7-8 汉诺塔的非递归实现

借助堆栈以非递归（循环）方式求解汉诺塔的问题（n, a, b, c），即将N个盘子从起始柱（标记为“a”）通过借助柱（标记为“b”）移动到目标柱（标记为“c”），并保证每个移动符合汉诺塔问题的要求。

输入格式:

输入为一个正整数N，即起始柱上的盘数。

输出格式:

每个操作（移动）占一行，按柱1 -> 柱2的格式输出。

输入样例:

3

输出样例:

a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

没有错，我用递归写✍的而且过了。。。。（虽然这道题说了非递归实现）

​

​

​

​

汉诺塔，咱还真不会（C语言?老师讲过?，咱都还回去了）

感觉从B站学了一下?才懂了点：汉诺塔算法粗劣讲解以及编程实现

就是每一?‍步都可以分解为

1.前n-1个移到辅助杆子上。

2.把最后一个移到目标杆子上。

3.把辅助杆子上的移到目标杆子上。

hanno（n,yuanshi,fuzhu,mubiao）{ hanno(n-1,yuanshi,mubiao,fuzhu); hanno(1,yuanshi,fuzhu,mubiao); hanno(n-1,fuzhu,yuanshi,mubiao); } //大概思路就是这么个思路

#include<iostream>
using namespace std;
int hanno(int n,char yuanshi,char fuzhu,char mubiao){
	if(n==1){
		printf("%c -> %c\n",yuanshi,mubiao);
	}else{
		hanno(n-1,yuanshi,mubiao,fuzhu);
		hanno(1,yuanshi,fuzhu,mubiao);
		hanno(n-1,fuzhu,yuanshi,mubiao);
	}
	return 0;
}
int main(){
	int n;
	cin>>n;
	hanno(n,'a','b','c');
	return 0;
} 

ps：我后来又遇到了这个题，总算是研究了一下非递归实现

1-2 汉诺塔的非递归实现 (25 分)点击传送~~~

至于非递归?嘛，咱现在还不会。咱也不敢写。给个链接⑧；

非递归的思想来实现汉诺塔问题的求解

​