递归之汉诺塔(Hanoi)

1. 问题描述

   汉诺塔（Hanoi），又称河内塔问题，是印度的一个古老传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去。庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。

   后来，这个传说就演变为汉诺塔游戏：

   

   （1）有三根桩子A、B、C。A桩上有n个碟子，最大的一个在底下，其余一个比一个小，依次叠上去。

   （2）每次移动一块碟子，小的只能叠在大的上面。

   （3）把所有碟子从A桩全部移到C桩上，如图35-1所示。

   试求解n个圆盘A桩全部移到C桩上的移动次数，并求出n个圆盘的移动过程。

2. 算法分析

   (1)求移动次数

   递归关系

   当n=1时，只一个盘，移动一次即完成。

   当n=2时，由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，首先把小盘从A桩移到B桩；然后把大盘从A桩移到C桩；最后把小盘从B桩移到C桩，移动3次完成。

   设移动n个盘的汉诺塔需g(n)次完成。分以下三个步骤：

   (1) 首先将n个盘上面的n-1个盘子借助C桩从A桩移到B桩上，需g(n-1)次；

   (2) 然后将A桩上第n个盘子移到C桩上（1次）；

   (3) 最后，将B桩上的n-1个盘子借助A桩移到C桩上，需g(n-1)次。

   因而有递归关系：

   g(n)=2*g(n-1)+1

   初始条件(递归出口)：

   g(1)=1

#include <iostream>

using namespace std;

long long HanoiCount(int n)
{
    if (n == )
        return ;
    //汉诺塔求移动次数中的递推关系 
    return *HanoiCount(n-) + ; 
}

int main()
{
    int n;
    cin >> n;

    cout << HanoiCount(n) << endl; 

    return ;
}
           

(2)展示移动过程

求解思路

设递归函数hn(n,a,b,c)展示把n个盘从A桩借助B桩移到C桩的过程,函数mv(a,c)输出从a桩到c桩的过程。

完成hn(n,a,b,c)，当n=1时，即mv(a,c)。

当n>1时，分以下三步：

(1) 将A桩上面的n-1个盘子借助C桩移到B桩上，即hn(n-1,a,c,b)；

(2) 将A桩上第n个盘子移到C桩上，即mv(a,c)；

(3) 将B桩上的n-1个盘子借助A桩移到C桩上，即hn(n-1,b,a,c)。

在主程序中，用hn(m,1,2,3)带实参m,1,2,3调用hn(n,a,b,c)，这里m为具体移动盘子的个数.

#include <iostream>

using namespace std;

//a借助b移动到c 
void Hanoi(int n, char a, char b, char c)
{
    if (n == )
    {
        cout << a << "------>" << c << endl;
        return; 
    }
    //把n-1个盘子从a借助c移动到b 
    Hanoi(n-, a, c, b);
    //把a最下面的盘子移动到c
    cout << a << "------>" << c << endl;
    //把b上的n-1个盘子借助a移动到c
    Hanoi(n-, b, a, c); 
}

int main()
{
    //盘子数 
    int n;
    cin >> n;

    Hanoi(n, 'A', 'B', 'C'); 

    return ;
}