汉诺塔问题（递归）

今天看了汉诺塔问题，在一本书上简单了看了个大概，没有深入的了解。先记上。

#include<stdio.h>
/*
	汉诺塔问题。
	有n个盘子，有三根石柱，n个盘子从上到下依次为从小到大的盘子，而且在第一个石柱上面，
	问题：把一个石柱上面的盘子移到第三个上面，而且一次只能移动一个，移动时小盘子必须
	放在大盘子上面。求最后移动的整个过程，和 
	  
	
	我们把n个盘子从A柱移动到C柱,问题可以变为: 
	Hanio(n,A,B,C)
	该问题可以分解为以下子问题:
	第一步：将n-1个盘子从A柱移动至B柱（借助C柱为过渡柱）
	第二步:将A柱底下最大的盘子一定至C柱
	第三步：将B柱的n-1个盘子移至C柱（借助A柱为过渡柱） 
	
	 
	 最后的步数为:(2^n)-1 
*/
int i;//记录步数 

//表示进行的步数,将编号为n的盘子由from柱移动到to柱（目标柱） 
void move(int n,char from,char to){
	printf("第%d步，将%d号盘子%c--->%c\n",i++,n,from,to); 
} 

//汉诺塔递归函数 
void Hanio(int n,char pos_start,char pos_trans,char pos_end){
	
	
	//当n=1时,表示就有一个盘子，直接从起始柱移动到目标柱上面 
	if(n == 1){
		move(n,pos_start,pos_end);
	}else{
		// 递归开始，我们要把最大的一个盘子移动到第三个柱子上面，n-1个盘子 在第二个盘子上面,所以此时第三个为过渡柱
		//所以把pos_trans放到第三个位置,pos_end放到第二个位置。 
		Hanio(n-1,pos_start,pos_end,pos_trans);
		move(n,pos_start,pos_end);
		//这是第一个柱子为空，变为过渡柱，最后一个柱子上面放着最大的盘子 
		Hanio(n-1,pos_trans,pos_end,pos_start);
	}
}

int main(){
	i = 1;
	Hanio(4,'1','2','3');
	printf("最后总共的步数是:%d\n",i-1);
}

执行结果如下：