汉诺塔

好好学习，天天向上。

汉诺塔问题

古代有一座汉诺塔， 塔内有 3 个座 A、B、C,A 座上有 几 个盘子， 盘子大小不等， 大的在下，小的 在上， 如图 4−1 所示。有一个和尚想把这n个盘子从A座移到 C座， 但每次只能移动一个盘子， 并且在移动过程中， 3 个座上的盘子始终保持大盘在下，小 盘在上。在移动过程中可以利用 B座来放盘子。要求输出移动的步骤。

思路

只有一个盘子那就直接 a->c.

两个盘子需要先将上面的盘子移动到b盘

先a->b 再a->c 再b->c

三个盘子需要先将前两个盘子移动到b盘，再把第三个盘子移动到c盘，最后把上面两个盘子移动c盘上去

前两个盘子移动到b盘，就是问题转化成a到b 借助c盘 上面两个盘子从b到c转化成b到c借助a

总的思路就是 先把前n-1个盘子移动到b盘，

再把最后第n个盘子移动到c盘，

最后把前n-1个盘子移动到C盘上。

递归代码

#include<bits/stdc++.h>
using namespace std;

void pf(char a,char b)
{
	printf("%c->%c\n",a,b);
}

void f(char a,char b, char c,int n)
{
	if(n==0)return ;
	
	f(a,c,b,n-1);  
	
	pf(a,c);
	
	f(b,a,c,n-1); 
}

int main()
{
	int n;
	cin>>n;
	
	char a = 'A',b = 'B',c = 'C';
	
	f(a,b,c,n);
	
	return 0;
}