汉诺塔非递归算法

最近的算法课,讲到了递归与分治策略,书上递归的例子是很经典的汉诺塔问题。问题大意是有三个塔座,分别为a,b,c,开始时塔座a上叠有n个圆盘,这些圆盘自上而下,由小到大地叠放在一起,各圆盘从小到大编号为1到n。要求将塔座a上的圆盘移动到塔座b上,并且在移动时每次只能移动一个圆盘,且每个塔座上的圆盘都必须保持自上而下、由小到大的排列顺序。

本文不涉及对非递归算法的数学性证明,若想理解非递归算法的道理,下面的就不用看啦。

递归的解法就不再说了,这里谈一下非递归的解法。教科书上对于非递归解法是这样描述的:

假设塔座a,b,c排成一个三角形,a->b->c->a构成一顺时针循环,在移动圆盘的过程中,若是奇数次移动,则将最小的圆盘移到顺时针方向的下一塔座;若是偶数次移动,则保持最小的圆盘不动,而在其他两个塔座之间,将较小的圆盘移到另一塔座上去。

在这里我们默认塔座a是初始圆盘放置的塔座,塔座b是圆盘需要移到的目标塔座,塔座c是目标塔座,n是初始的圆盘数量。经过个人编码验证,证实书上说的有一点不妥,正确的说法是:

当n是奇数时,塔座按a->b->c->a排列,而当n是偶数时,塔座应该按a->c->b->a排列。

自己编码之前,也上网看过别人写的代码,自己都不是很喜欢,定义了各种复杂的结构体还有函数等,于是自己写了一个c++版本的,只用到了vector这一种数据结构,不过由于都写在一个hanoi函数体内,关于打印信息方面可能处理的不是很好,显得程序有点冗长,但整体结构还是挺清晰的。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
void hanoi(int n) {
// the aim is to move plates from A to B
// when n is odd, the tower is placed in order A->B->C
// when n is even, the tower is placed in order A->C->B
vector<char> odd{'A', 'B', 'C'};
vector<char> even{'A', 'C', 'B'};
vector<vector<int>> tower(3, vector<int>());
// initialize
for(int i=n; i>=1; i--)
tower[0].push_back(i);
// loop begin
int iter = 0;
while(true) {
// different endings for n
if(n%2 && tower[0].empty() && tower[2].empty()) break;
if(n%2==0 && tower[0].empty() && tower[1].empty()) break;
iter++;
if(iter % 2) { // odd plate move
// just move plate1 to next tower
int min = MAX+1;
int index;
for(int i=0; i<3; i++) {
if(!tower[i].empty() && tower[i].back()<min) {
min = tower[i].back();
index = i;
}
}
tower[index].pop_back();
tower[(index+1)%3].push_back(min);
if(n%2) { // different n, different messages
cout << "Moving plate " << min << " from "
<< odd[index] << " to "
<< odd[(index+1)%3] << endl;
}
else {
cout << "Moving plate " << min << " from "
<< even[index] << " to "
<< even[(index+1)%3] << endl;
}
}
else { // even plate move
// move the smallest plate except plate1 to another
int min = MAX+1;
int index;
for(int i=0; i<3; i++) {
if(!tower[i].empty() && tower[i].back()<min) {
min = tower[i].back();
index = i;
}
}
// get the other two tower whose top is not plate1
int index1 = (index+1)%3;
int index2 = (index+2)%3;
if(tower[index1].empty()) {
min = tower[index2].back();
tower[index2].pop_back();
tower[index1].push_back(min);
if(n%2) { // different n, different messages
cout << "Moving plate " << min << " from "
<< odd[index2] << " to "
<< odd[index1] << endl;
}
else {
cout << "Moving plate " << min << " from "
<< even[index2] << " to "
<< even[index1] << endl;
}
}
else if(tower[index2].empty()) {
min = tower[index1].back();
tower[index1].pop_back();
tower[index2].push_back(min);
if(n%2) { // different n, different messages
cout << "Moving plate " << min << " from "
<< odd[index1] << " to "
<< odd[index2] << endl;
}
else {
cout << "Moving plate " << min << " from "
<< even[index1] << " to "
<< even[index2] << endl;
}
}
else {
int index3;
if(tower[index1].back() < tower[index2].back()) {
min = tower[index1].back(); index3 = index1;
}
else {
min = tower[index2].back(); index3 = index2;
}
tower[index3].pop_back();
tower[3-index-index3].push_back(min);
if(n%2) { // different n, different messages
cout << "Moving plate " << min << " from "
<< odd[index] << " to "
<< odd[(index+1)%3] << endl;
}
else {
cout << "Moving plate " << min << " from "
<< even[index] << " to "
<< even[(index+1)%3] << endl;
}
}
}
}
return;
}

上面代码的5,6两行定义的两个vector是用于打印信息的时候用的,当n是奇数时,就采用odd里面的顺序,n是偶数时,就采用even里面的顺序,所有打印处理信息的时候要考虑到n的奇偶性,显得打印信息那几块地方比较罗嗦。记录每个塔座上的圆盘信息只用了一个二维vector tower,初始化的时候tower[0],即塔座a上面自下而上从大到小放置了n个圆盘。

然后就进入循环了,由于n的奇偶问题,所以终结循环的判定条件也有两种,在第17、18行。进入循环分成两大块,即判定当前移动次数是奇数次还是偶数次,如果是奇数次,就执行22行开始的代码,将标号为1的圆盘顺时针移动到下一个塔座,要考虑n的奇偶性不同带来的顺时针顺序不同的问题;如果是偶数次,就执行46行开始的代码,保持最小的圆盘不动,移动另外两个塔座上较小的圆盘到另一个塔座,这里要判定一下这两个塔座其中是否不存在圆盘,同样的还是要考虑n的奇偶性带来的顺时针顺序不同的问题。

考虑到博客里代码显示宽度不够,给阅读带来一定的不便性,代码也放在了我的github上,点击这里
(完)

文章目录
|