遞歸之漢諾塔(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 ;
}