[C++知识库]汉诺塔递归&非递归（简码合辑）

“ Ctrl AC！一起 AC！”

递归法：

#include<iostream>
using namespace std;
//递归到第一个盘子进行操作
void hanoi(int n,char a,char b,char c){
	if(n==0) return;
	hanoi(n-1,a,c,b); //将n-1个盘子放到辅助柱上
	printf("%c -> %c\n",a,c); //上步空出空间，让第n个盘子移动到目的柱
	hanoi(n-1,b,a,c); //将n-1个盘子放到目的柱上
}
int main(){
	int n;cin>>n;
	hanoi(n,'a','b','c');
	return 0;
}

?非递归法：

#include<iostream>
#include<stack>
using namespace std;
struct done{
	int n;
	char a,b,c;
	done(int n,char a,char b,char c):n(n),a(a),b(b),c(c){}
};
int main(){
	int n;cin>>n;
	stack<done> s;
	s.push(done(n,'a','b','c')); //初始准备
	while(!s.empty()){
		done temp=s.top();s.pop(); //取出第一步操作
		if(temp.n==1) printf("%c -> %c\n",temp.a,temp.c); //n为1时才是目的碟
		else{
			//压操作：使得第一步先从栈出来
			s.push(done(temp.n-1,temp.b,temp.a,temp.c)); //第三步先压
			s.push(done(1,temp.a,temp.b,temp.c)); //第二步其次
			s.push(done(temp.n-1,temp.a,temp.c,temp.b)); //第一步最后压
		}
	}
	return 0;
}

感谢阅读！！！

“ Ctrl AC！一起 AC！”