汉诺塔问题——（经典递归问题）

经典题目

      有三根相邻的柱子，标号为A,B,C，

      A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，

      要把所有盘子一个一个移动到柱子C上，

      并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，

      请问至少需要多少次移动？

 

         

 

问题分析

      首先我们肯定是把上面n-1个盘子移动到柱子B上，

      然后把最大的一块放在C上，

      最后把B上的所有盘子移动到C上

 

C++实现

     

#include <iostream>

void hanoi(int n, char A, char B, char C)
{
	static int count=0;
	if (n < 1)
	{
		return;
	}
	else
	{
		hanoi(n - 1, A, C, B);
		std::cout << "第"<<++count <<"次移动：  "<<A << "->" << C << std::endl;
		hanoi(n - 1, B, A, C);
	}
}

void main()
{
	int n;
	std::cin >> n;
	hanoi(n,'A','B','C');

	std::cin.get();
	std::cin.get();

}