递归解决汉诺塔问题

题目：输出解N层汉诺塔时的移动过程。

代码：

#include<iostream>
#include<vector>
using namespace std;
vector<int> stick[3];	//动态数组，存储三根柱子上的圆环 
int n,ans;	//总层数，当前移动步数

//求出总步数（answer=2^n-1）
int answer() {	 
	int a=1;
	for(int i=0;i<n;i++) a=a*2;
	return a-1;
}

//输出当前三根棍子上圆环的分布情况 
void print() {	
	ans++;
	printf("%d次移动后：\n",ans);
	for(int i=0;i<3;i++) {
		printf("第%d根柱：",i+1);
		for(int j=0;j<stick[i].size();j++) printf("%d ",stick[i][j]);
		printf("\n");
	}
	printf("\n");
}

//求出除了from和to,另外那根棍子是哪个 
int num(int from,int to) {
	if(from!=1&&to!=1) return 1;
	else if(from!=2&&to!=2) return 2;
	return 3;
}

// 把第from根棍子顶端的数移到第to根上，并输出 
void move(int from,int to) {
	int num;
	from--;	//由于数组从零开始，故减一 
	to--;
	num=stick[from].size();
	stick[to].push_back(stick[from][num-1]);	//移过去 
	stick[from].pop_back();	//删掉原来的 
	
	print();
}

//核心的递归函数
void solve(int x,int from,int to) {
	if(x==1) move(from,to);
	else {
		int middle=num(from,to);
		solve(x-1,from,middle);
		move(from,to);
		solve(x-1,middle,to);
	}
}

int main() {
	printf("请输入汉诺塔层数："); scanf("%d",&n); printf("\n");	//输入
	
	printf("共需要移动%d次\n\n",answer());	//输出答案
	
	for(int i=n;i>0;i--) stick[2].push_back(i);	//初始化动态数组
	
	solve(n,3,1);	//把n个数从最3移到1，并输出过程 
	
	return 0; 
}

运行效果：