递归求解汉诺塔问题

• 数据结构习题解析・邓俊峰 课后习题

问题
有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

1. 每次只能移动一个圆盘
2. 大盘不能叠在小盘上面
   提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。

问：如何移？最少要移动多少次？

汉诺塔
问题分析

• 具体分析网上有个博客解释的十分详尽，我自认不能比他解释的更清楚，所以在此贴一下他的地址: 汉诺塔的理解

要把圆盘移至C杆，我们可以分为以下步骤:

1. 先把堆在A杆上的前n-1根借助C杆移到B杆上
2. 再把A杆上剩余的最后一个移到C杆上
3. 最后再把B杆上的n-1个盘借助A杆移到C上

• 当碟子为0时递归结束

代码:

#include <iostream>
using namespace std;

/* diskNums 盘子数量，init 初始杆名称，temp 临时杆名称，dest 目标杆名称 */
void hanoi(int diskNums, string init, string temp, string dest);
void move(int diskNums, string init, string dest);

int main(int argc, const char * argv[]) {
    hanoi(3, "A", "B", "C");
    return 0;
}
void hanoi(int diskNums,string init,string temp,string dest){
    if (diskNums>0) {
        hanoi(diskNums-1, init, dest, temp);
        move(diskNums, init, dest);
        hanoi(diskNums-1, temp, init, dest);
    }
}
void move(int diskNums, string init, string dest){
    cout<<"No."<<diskNums<<" disks from "<<init<<" to "<<dest<<endl;
}

运行结果

No.1 disks from A to C
No.2 disks from A to B
No.1 disks from C to B
No.3 disks from A to C
No.1 disks from B to A
No.2 disks from B to C
No.1 disks from A to C
Program ended with exit code: 0

复杂度分析
由递归的基本条件推出递推式:

T(1) = O(1)    对应 if(n>0),递归基

T(n) = 2*T(n-1) + O(1)    
对应下面这三个函数
hanoi(diskNums-1, init, dest, temp);
move(diskNums, init, dest);
hanoi(diskNums-1, temp, init, dest);

S(n) = T(n) + O(1) = 2*T(n-1) + 2*O(1)
S(n-1) = T(n-1) + O(1)
S(n) = 2*S(n-1)
     = 2^2*S(n-2)
     ......
     = 2^n-1*S(1)
     = 2^n

故有 T(n) = O(2^n)