汉诺塔问题递归求解

问题描述：给定三根柱子，记为 ‘A’,’B’,’C’ ，其中 A柱子上有 B个盘子，从上到下编号为 0 到 N−1 ，且上面的盘子一定比下面的盘子小。问：将 A 柱上的盘子经由B柱移动到C柱最少需要多少次？

移动时应注意：

① 一次只能移动一个盘子

②大的盘子不能压在小盘子上

递归算法求解：

#include<iostream>
using namespace std;
void Honoi(int n, char first, char second, char third, int &num){
	if (n == 1 ) {
		cout << first << " -> " << third << endl ;//只有一个盘子 
		num++;
		return ;
	}
		Honoi(n-1 , first , third , second, num);//将n-1个盘子先移到second 
		cout << first << " -> " << third << endl;//再将一个盘子移到third 
		num++;
		Honoi(n-1 , second , first , third, num);//再将剩下的n-1个盘子从second移到third 
}
int main()
{
	int n;
	cin >> n;//盘子数目
	int num=0;//用来计算移动次数 
	Honoi(n , 'A' , 'B' , 'C', num);
	cout << "一共用了" << num << "次"; 
	return 0; 
}