漢諾塔問題的遞歸實現（擴展）

Title：漢諾塔問題的遞歸實現

漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

一、漢諾塔（基本）

漢諾塔問題是典型的分治算法問題，首先我們來討論最基本的漢諾塔問題。假設有n個圓盤，三根柱子，a，b，c，需要把n個盤子（從下往上按照大小順序摞著）從a柱移動到c柱，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

1.1 打印路徑

采用分治法，分而治之，把大問題化解成小問題。故可以把n個盤子看成n-1個盤子，和第n個盤子，首先我們需要把n-1個盤子移動到b柱子上，然后把第n個盤子移動到c柱子上，最后把n-1個盤子移動到c柱子上，這樣就用最少的移動次數完成了任務。

c++實現：

#include <iostream>
using namespace std;
void move(int n, char a, char b){
    cout<<a<<"->"<<b<<endl;
}
void hanoi(int n, char a, char b, char c){//把n個盤子從a柱子移動到b柱子
    if(n > 0) {
        hanoi(n - 1, a, c, b);// 把n-1個盤子移動到c柱子上
        move(n, a, b);  // 把a移動到b
        hanoi(n - 1, c, b, a);  // 把第n-1個盤子從c柱子移動到b柱子上
    }
}
int main()
{
    int n;
    while(cin>>n){
        char a='a',b='b',c='c';
        hanoi(n,a,c,b);   //把n個盤子從a柱子移動到c柱子
    }
    return 0;
}

以上程序顯示全部步驟的移動方法。

1.2 計算移動次數

如果要計算一共移動了多少次，找出規律即可。

假設移動n個盤子需要移動f(n)次，所以把n-1個盤子移動到b柱子上，需要移動f(n-1)次，然后把第n個盤子移動到c柱子上，需要移動1次，最后把n-1個盤子移動到c柱子上，需要移動f(n-1)次，綜上所述，一共移動了

f(n) = 2 f(n-1) + 1

而：

 f(1) = 1;

 f(2) = 2*1+ 1;

 f(3) = 2(2*1+ 1)+ 1;

 .......

 f(n) = 2^n -1

C++實現：

//基本漢諾塔移動次數，可以算小于64的所有盤子數
#include <iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n){
        if(n>63||n<1) {
            cout<<"ERROR"<<endl;
            continue;
        }
        __int64 sum = 1;
        for(int i=1;i<=n;i++)
            sum*=2;
        cout<<sum-1<<endl;
    }
    return 0;
}

二、漢諾塔（必須通過中間的柱子）

假設有n個圓盤，三根柱子，a，b，c，需要把n個盤子（上從下往上按照大小順序摞著）從a柱移動到c柱，不允許直接從最左(右)邊移到最右(左)邊(每次移動一定是移到中間桿或從中間移出)，也不允許大盤放到下盤的上面。

2.1 打印路徑

參考acm題目：http://acm.hdu.edu.cn/showproblem.php?pid=2064

這道題和之前不同，約束了必須通過中間的柱子才可以，這也難不倒我們，我們只需要在遞歸的時候改變一下策略就可以完成任務。

解決方法：

依然采用分治法，分而治之，把大問題化解成小問題。最開始在a柱子上有n個盤子，我們可以把n個盤子看成n-1個盤子，和第n個盤子。首先我們需要把n-1個盤子移動到c柱子上（n-1個盤子只能由a移動到c或者由c移動到a，否則就不是最少次數了），然后把第n個盤子移動到b柱子上（不能直接由a移動到c），最后把n-1個盤子移動到c柱子上，這樣就用最少的移動次數完成了任務。

c++實現：

#include <iostream>
using namespace std;
void move(int n, char a, char b){
    cout<<a<<"->"<<b<<endl;
}
void hanoi(int n, char a, char c, char b){
    if(n > 0) {
        hanoi(n - 1, a, c, b);
        move(n, a, b);
        hanoi(n - 1, c, a, b);
        move(n, b, c);
        hanoi(n - 1, a, c, b);
    }
}
int main()
{
    char a='a',b='b',c='c';
    hanoi(3,a,c,b);
    return 0;
}

2.2 計算移動次數

如果要計算一共移動了多少次，找出規律即可。

假設移動n個盤子需要移動f(n)次，所以把n-1個盤子移動到c柱子上，需要移動f(n-1)次，然后把第n個盤子移動到b柱子上，需要移動1次，然后把n-1個盤子移動到a柱子上，需要移動f(n-1)次，第n個盤子移動到c柱子上，需要移動1次，最后把n-1個盤子移動到c柱子上，需要移動f(n-1)次，綜上所述，一共移動了

f(n) = 3 f(n-1) + 2

而：

 f(1) = 2;

 f(2) = 3*2+ 2;

 f(3) = 3(3*2+ 2)+ 2;

 .......

 f(n) = 3^n -1

C++實現：

#include <iostream>
using namespace std;
int main()
{
    int n;
    __int64 f[36];
    f[1]=2;
    for(int i=2;i<=35;i++) f[i]=3*f[i-1]+2;
    while(cin>>n){
        if(n>56||n<1){
            cout<<"ERROR!"<<endl;
            continue;
        }
        cout<<f[n]<<endl;
    }
    return 0;
}

三、漢諾塔（必須通過中間的柱子，允許最大的放在最上面）

假設有n個圓盤，三根柱子，a，b，c，需要把n個盤子（上從下往上按照大小順序摞著）從a柱移動到c柱，不允許直接從最左(右)邊移到最右(左)邊(每次移動一定是移到中間桿或從中間移出)，也不允許大盤放到小盤的上面。如果我們允許最大的盤子放到最上面會怎么樣呢？（只允許最大的放在最上面）當然最后需要的結果是盤子從小到大排在最右邊。

3.1 打印路徑

參考acm題目：http://acm.hdu.edu.cn/showproblem.php?pid=2077

這道題和之前不同，約束了必須通過中間的柱子才可以，也放寬了對最大盤子的限制，所以肯定比第二種漢諾塔移動次數少，我們也是只需要在遞歸的時候改變一下策略就可以完成任務。

解決方法：

依然采用分治法，分而治之，把大問題化解成小問題。最開始在a柱子上有n個盤子，我們可以把n個盤子看成n-2個盤子，和第n-1，以及第n個盤子。首先我們需要把n-2個盤子移動到c柱子上（利用第二種類型的算法），然后把第n-1和n個盤子依次移動到b柱子上，再把n-2個盤子移動到a柱子上，再把第n和第n-1個盤子移動到柱子c上，這樣就用最少的移動次數完成了任務。

C++實現：

#include <iostream>
using namespace std;
void move(int n, char a, char b){
    cout<<a<<"->"<<b<<endl;
}
void hanoi(int n, char a, char c, char b){
    if(n > 0) {
        hanoi(n - 1, a, c, b);
        move(n, a, b);
        hanoi(n - 1, c, a, b);
        move(n, b, c);
        hanoi(n - 1, a, c, b);
    }
}
void Hanoi_(int n, char a, char c, char b){
    if(n > 0) {
        hanoi(n - 2, a, c, b);
        if(n > 1)
        move(n - 1, a, b);
        move(n, a, b);
        hanoi(n - 2, c, a, b);
        move(n, b, c);
        if(n > 1)
        move(n - 1, b, c);
        hanoi(n - 2, a, c, b);
    }
}
int main()
{
    int n;
    while(cin>>n) {
        char a='a',b='b',c='c';
        Hanoi_(n,a,c,b);
    }
    return 0;
}

3.2 計算移動次數

如果要計算一共移動了多少次，找出規律即可。

假設移動n個盤子需要移動F(n)次，用第二種算法把n-2個盤子移動到c柱子上（利用第二種類型的算法），需要f(n-2)次，然后把第n-1和n個盤子依次移動到b柱子上，需要2次，再把n-2個盤子移動到c柱子上，再把第n和第n-1個盤子移動到柱子c上，需要2次，綜上所述，一共移動了

f(n) = 3 f(n-2) + 4

而：

 f(n-2) = 3^(n-2)-1

故，f(n)=3^(n-1)+1

C++實現;

#include <iostream>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        if(n>51||n<1) {
            cout<<"ERROR"<<endl;
            continue;
        }
        __int64 sum = 1;
        for(int i=1;i<=n-1;i++)
            sum*=3;
        cout<<1+sum<<endl;
    }
    return 0;
}

四、漢諾塔（加一根柱子）

假設有n個圓盤，三根柱子，a，b，c，需要把n個盤子（上從下往上按照大小順序摞著）從a柱移動到c柱，再找來了一根一模一樣的柱子d，通過這個柱子來更快的把所有的盤子移到第三個柱子上。

4.1 計算移動次數

參考acm題目：http://acm.hdu.edu.cn/showproblem.php?pid=1207

這道題和之前都有很大的不同，加了一根柱子，意味著有的時候可用3根柱子，有的時候可用4根柱子，當把j個小盤子移動到d盤上時，有四根柱子可用，而當把n-j個盤子從a移動到c時，僅有三根柱子可用。這里我們就要找到j的值，使所有移動的次數和最小。

解決方法：

依然采用分治法。首先把j個盤子移動到d柱子上（通過四個柱子可用的算法），需要B[j]次移動，然后把n-j個盤子移動到c柱子上（通過三個柱子可用的算法），需要A[n-j]次移動，，然后把d中的j個盤子移動到c柱子上，需要B[j]次移動。我們可以用j的大小循環，找到移動次數最小的j。

首先我們先計算移動的次數，核心公式為下面代碼中的：flag = 2*B[ j ] + A[ i - j];   //j個盤子移動到第四個柱子，然后把剩下的i-j個在第四個不能用的情況下移到第三個

計算次數的c++實現：

#include <iostream>
using namespace std;
int main()
{
    int n;
    double a[65],b[65];  //數組a代表沒加第四個柱子的結果，數組b代表加了第四個柱子的結果
    a[1]=1;
    for(int i=2;i<=64;i++) a[i]=2*a[i-1]+1;
    b[1]=1;
    b[2]=3;
    for(int i=3;i<=64;i++){
        double min=a[i],flag;
        for(int j=1;j<i;j++){
            flag=2*b[j]+a[i-j]; //j個移動到第四個柱子，然后把剩下的i-j個在第四個不能用的情況下移到第三個柱子上
            if(min>flag) min=flag;
        }
        b[i]=min;
    }
    while(cin>>n){
        if(n>64||n<1){
            cout<<"ERROR!"<<endl;
            continue;
        }
        cout<<b[n]<<endl;
    }
    return 0;
}

4.2 打印路徑

利用上面的算法，我們可以很容易得出路徑

模擬移動步驟的C++實現：

#include <iostream>
using namespace std;
void move(int n, char a, char b){
    cout<<a<<"->"<<b<<endl;
}
void hanoi_basic_3(int n, char a, char b, char c){//把n個盤子從a柱子移動到b柱子
    if(n > 0) {
        hanoi_basic_3(n - 1, a, c, b);// 把n-1個盤子移動到b柱子上
        move(n, a, b);  // 把a移動到b
        hanoi_basic_3(n - 1, c, b, a);  // 把第n個盤子移動到b柱子上
    }
}
void hanoi(int n, char a, char c, char b, char d, int C[]){
    int j=C[n]; //j個盤子使用四個柱子的移動方式
    if(n > 0) {
        hanoi(j, a, d, b, c, C);// 把j個盤子移動到d柱子上
        hanoi_basic_3(n - j, a, c, b);// 把n-j個盤子移動到c柱子上（使用三個柱子的移動方式）
        hanoi(j, d, c, a, b, C);    // 把j個盤子移動到c柱子上
    }
}
int main()
{
    int n,flag_j;
    double A[65];  //未加第四個柱子時候的移動次數情況
    A[1]=1;
    for(int i=2;i<65;i++) A[i]=2*A[i-1]+1;
    double B[65],flag,min;
    int C[65]; //把前 c[j]個元素用四個柱子的方法，后i-j 個元素用三個柱子的方法
    C[1]=0;
    C[2]=0;
    for(int i=3;i<=64;i++){
        min=A[i];  //數組A代表沒加第四個柱子的結果次數，數組b代表加了第四個柱子的結果次數
        B[1]=1;
        B[2]=3;
        flag_j=0;
        for(int j=1;j<i;j++){
            flag=2*B[j]+A[i-j]; //j個移動到第四個柱子，然后把剩下的i-j個在第四個不能用的情況下移到第三個
            if(min>flag) {
                min=flag;
                flag_j=j;
            }
        B[i]=min;
        C[i]=flag_j;
        }
    }
    while(cin>>n){
        char a='a',b='b',c='c',d='d';
        hanoi(n,a,c,b,d,C);   //把n個盤子從a柱子移動到c柱子
    }
    return 0;
}

@碼農同學，版權所有。