STL學習筆記：用非遞歸的方法實現漢諾塔問題
shaohui_1983#163.com t,srctop,dsttop,britop,last = 0;
7 stack<int> ssrc,sdst,sbri;
8 for (cnt=1 ;cnt<=scale; cnt++)
9 ssrc.push(cnt);
10
11 while (sdst.size() != scale)
12 {
13 srctop = ssrc.empty() ? 0 : ssrc.top();
14 dsttop = sdst.empty() ? 0 : sdst.top();
15 britop = sbri.empty() ? 0 : sbri.top();
16
17 if (last != srctop && ((srctop%2 && srctop>dsttop) || ((srctop%2==0) && srctop>britop)))
18 {
19 ssrc.pop();
20 last = srctop;
21 srctop % 2 ? sdst.push(srctop) : sbri.push(srctop);
22 if (srctop % 2)
23 cout<<"move disk "<<scale-srctop+1<<" from \'a\' to \'c\'\n";
24 else
25 cout<<"move disk "<<scale-srctop+1<<" from \'a\' to \'b\'\n";
26 }
27
28 if (last != britop && ((britop%2 && britop>srctop) || ((britop%2==0) && britop>dsttop)))
29 {
30 sbri.pop();
31 last = britop;
32 britop % 2 ? ssrc.push(britop) : sdst.push(britop);
33
34 if (britop % 2)
35 cout<<"move disk "<<scale-britop+1<<" from \'b\' to \'a\'\n";
36 else
37 cout<<"move disk "<<scale-britop+1<<" from \'b\' to \'c\'\n";
38 }
39
40 if (last != dsttop && ((dsttop%2 && dsttop>britop) || ((dsttop%2==0) && dsttop>srctop)))
41 {
42 sdst.pop();
43 last = dsttop;
44 dsttop % 2 ? sbri.push(dsttop) : ssrc.push(dsttop);
45 if (dsttop % 2)
46 cout<<"move disk "<<scale-dsttop+1<<" from \'c\' to \'b\'\n";
47 else
48 cout<<"move disk "<<scale-dsttop+1<<" from \'c\' to \'a\'\n";
49 }
50 }
51 }
看上面的代碼好象復雜了點，不過主要還是因為判別的條件太復雜了，才會導致這段代碼這麽難懂。在這個while循環裏面有3個if語句都在判定當前的盤子是否可以被移動，如果可以移動就移動它並且打印出來。
對於壹個盤子要可以移動要滿足以下2個條件
1． 前壹次沒有被移動過也就是不能夠等於last
2． 盤子的編號必須要大於目標盤最上面的盤子的編號
這兩個條件都要滿足才能移動，可以證明在任何時候可以移動的盤子都是唯壹的。
為了便於和開始的方法比較，在輸出的時候對盤子的編號做了個轉換，還是把它還原成原來的編號的方法。也就是編號小的在上，編號大的在下。上面我這個寫法實在是太不簡潔了，希望有寫得更好的替換它。
3．遞歸的方法
盡管書上已經有遞歸的方法，不過我還是要給出我的遞歸的方法，作為參考。然後用於性能的比較。
3 #define move(disk,src,dst) cout<<"move disk "<<disk<<" from \'"<<src<<"\' to \'"<<dst<<"\'\n"
4 void hanoi_r(int size,char src,char dst,char bri)
5 {
6 if (size == 1)
7 move(size,src,dst);
8 else
9 {
10 hanoi_r(size-1,src,bri,dst);
11 move(size,src,dst);
12 hanoi_r(size-1,bri,dst,src);
13 }
14 }
4.各種方法的比較
有不同的實現方法，當然就有對比，我壹直以為非遞歸的方法要比遞歸的方法要快壹些，不過結果好象並不是這樣。
由於打印輸出需要消耗部少的時間，所以我就把它去掉了，只是改動我定義的宏就可以了。
堆棧
#define print_oprt(op)
遞歸
#define move(disk,src,dst)
表示這個打印操作什麽都不做。
下面是我在我的計算機上虛擬的Linux環境下用3種不同的方法解決規模為1-30的漢諾塔問題所花的時間的比較結果（單位是秒）,妳也可以把這個程序下載到妳的計算機上去測試壹下。
Scale Stack Recursion Other (1-30)
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
5 0 0 0
6 0 0 0
7 0 0 0
8 0 0 0
9 0 0 0
10 0 0 0
11 0 0 0
12 0 0 0
13 0 0 0
14 0 0 0.01
15 0 0 0.01
16 0.02 0 0.01
17 0.03 0 0.03
18 0.05 0 0.05
19 0.12 0 0.12
20 0.23 0.01 0.23
21 0.49 0.01 0.47
22 0.95 0.04 0.89
23 1.92 0.07 1.87
24 3.8 0.15 3.55
25 7.65 0.3 7.52
26 15.2 0.6 14.24
27 30.49 1.2 29.7
28 61.11 2.41 57.24
29 111.15 4.29 97.56
30 201.09 7.72 184.32
用堆棧和其它的方法所花的時間比較接近，而用遞歸的速度卻是最快的。相差非常的大。到底是什麽原因呢，按理說應該不會有這麽大的差別哦。
總結了壹下，大概有以下原因：
1． STL本身的效率不是太高
STL功能強大了，效率上必然要受到壹定的影響
2． 遞歸的方式函數調用比較少，就是調用它本身，而其它方式函數調用比較多
從代碼中我們就可以看出，非遞歸方式調用函數的次數遠遠比遞歸方式多，每次移動操作都要調用好幾次函數，pop,push等，而遞歸方式，每次移動操作只調用本身壹次，故系統堆棧的負擔要小的多。
3． 對堆棧實現，涉及到對象的多次構造和析構，並且還有就是堆棧的多次重新分配也需要消耗不少的時間(STL中stack是順序存儲結構，當空間不夠用時，再向系統申請雙倍的空間)
附錄
上面提到的所以代碼我都已經把它壓縮好了，並且提供下載，
/zhengsh/download/hanoi.tar.gz
在readme文件中有比較詳細的說明。除了hanoi_cmp.c其它的文件都可以在windows,linux下通過編譯，我使用的是Linux下實現的，所以最好在Linux下重新編譯它們。