汉诺塔问题（递归）（C++）

汉诺塔问题（递归）（C++）

Question:

先搬一个百度百科的图片过来，侵删~~~

 Solve:

1.总体三大步： 

 1    将A中的n-1个圆盘先放到中转的柱子上 2    将A中的第n个圆盘移动到目标柱子上 3    将C柱中的n-1个圆盘移动到目标柱子上

        至于第一步和第三步的实现，考虑递归，直到挪动的圆盘数n-1 = 1，问题也就解决了

2.还有一个点是这个问题的步骤数是多少：

        首先，我们设n个圆盘的移动次数为cnt[n]

        移动一个圆盘步骤数是一，也就是说cnt[1] = 1

        第二步 *** 作圆盘移动一次，步骤数为1

        第一步 *** 作和第三步 *** 作里，圆盘的移动次数都是cnt[n-1]次

        所以可以推出公式cnt[n]  = cnt[n-1]*2 + 1;

将公式用数学方法算出来，就可以得到结论：n个圆盘时的步骤数为2的n次方减一

Code:

void Hanoi(char start_post, char end_post, char temp_post, int n)
{
    if(!n) return;  //已经没有圆盘可以移动，返回
    //三个步骤三行代码，直接递归调用函数
    Hanoi(start_post, temp_post, end_post, n - 1);

    printf("take %d : from %c to %cn", n, start_post, end_post);

    Hanoi(temp_post, end_post, start_post, n - 1);
}

 eg：放一个三个圆盘的测试结果