版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://cloud.tencent.com/developer/article/1535016
借助堆栈以非递归(循环)方式求解汉诺塔的问题(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
#include<iostream>
using namespace std;
int hannuo(int n,char a,char c,char b){//n个从a到c借助b
if(n==1){
cout<<a<<" -> "<<c<<endl;
}else{
hannuo(n-1,a,b,c);
hannuo(1,a,c,b);
hannuo(n-1,b,c,a);
}
}
int main(){
int n;
cin>>n;
hannuo(n,'a','c','b');
return 0;
}
汉诺塔的非递归算法描述如下: 首先容易证明,当盘子的个数为n时,移动的次数应等于2^n - 1。 一位美国学者发现一种出人意料的方法,只要轮流进行两步操作就可以了。 首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子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)操作,最后就能按规定完成汉诺塔的移动。
博主的感悟感觉很有意思 感想: 1.能用人脑能完成的部分尽量不要让计算机去完成,这样可以节省不少时间 2.printf快于cout 3.做题不要死磕,有些题是有毒的 4.不要尝试去自己写stack或者queue,deque来代替STL里的容器,这并不能节省多少时间 5.让人看得懂 > 代码简短
#include<iostream>
#include <stack>
char s[4] = { 'q','a','b','c' };
std::stack<int> a[4];
bool move(int before, int after) {
if (a[before].empty())
return false;
if (!a[after].empty())
if ((a[after].top() - a[before].top()) < 0)
return false;
a[after].push(a[before].top());
a[before].pop();
printf("%c -> %c\n", s[before], s[after]);//faster than cout
return true;
}
int main() {
int N, count = 0;
std::cin >> N;
for (int i = 0; i < N; i++)
a[1].push(N - i);
if (N % 2 == 1) {
s[2] = 'c'; s[3] = 'b';
}
while (++count) {
move((count - 1) % 3 + 1, (count) % 3 + 1);
if (!move((count - 1) % 3 + 1, (count + 1) % 3 + 1)&&!move((count + 1) % 3 + 1, (count - 1) % 3 + 1))
break;
}
}