汉诺塔问题(递归求解)

汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

现在我们来给出算法的详细实现
准确来讲核心代码只有三行（3步）
1.把除了最大盘子之外的所有盘子从A借助C移动到B(把n-1看成一个整体)
2.把最大盘子从A移到C
3. 把最大盘子之外的所有盘子再从B移到C

int dfsmove(int n,char A,char B,char C) //递归函数 ABC表示三根柱子
{	if(n==1)
	{   printf("把%c上的圆环移动到%c\n",A,C);
		step++; 
		return 0;
	}
	else     //把它简化为2层汉诺塔  然后三步移动 
	{ dfsmove(n-1,A,C,B);//把除了最大盘子之外的所有盘子从A借助C移动到B(把n-1看成一个整体)
	  printf("把%c上的圆环移动到%c\n",A,C); //把最大盘子从A移到C 
	  	step++;
      dfsmove(n-1,B,A,C); //把最大盘子之外的所有盘子再从B移到C 
	}
	return 1; 
}

下面给出完整的代码实现

#include <stdio.h>
int step=0; //统计执行步数 
int dfsmove(int n,char A,char B,char C) //递归函数 
{	if(n==1)
	{   printf("把%c上的圆环移动到%c\n",A,C);
		step++; 
		return 0;
	}
	else     //把它简化为2层汉诺塔  然后三步移动 
	{ dfsmove(n-1,A,C,B);//把除了最大盘子之外的所有盘子从A借助C移动到B(把n-1看成一个整体)
	  printf("把%c上的圆环移动到%c\n",A,C); //把最大盘子从A移到C 
	  	step++;
      dfsmove(n-1,B,A,C); //把最大盘子之外的所有盘子再从B移到C 
	}
	return 1; 
}
int main() 
{   int n;
    printf("输入汉诺塔的层数:");
	scanf("%d",&n); 
	dfsmove(n,'A','B','C');
	printf("执行次数为:%d",step);
	return 0; 
 } 

运行结果如下：