- 数据结构习题解析・邓俊峰 课后习题
问题
有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
- 每次只能移动一个圆盘
- 大盘不能叠在小盘上面
提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
问：如何移？最少要移动多少次？
汉诺塔
问题分析
- 具体分析网上有个博客解释的十分详尽，我自认不能比他解释的更清楚，所以在此贴一下他的地址: 汉诺塔的理解
要把圆盘移至C杆，我们可以分为以下步骤:
- 先把堆在A杆上的前n-1根借助C杆移到B杆上
- 再把A杆上剩余的最后一个移到C杆上
- 最后再把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)
