C++數據結構學習:遞歸(2.2)

2019-11-17 05:04:09

字體：大中小

來源：轉載

供稿：網友

　　3號盤子的目標柱是C，但是已經有了1號盤子，我們最直覺的反映就是——將礙事的盤子搬到另一根柱子上面去。于是，我們要做的是（規律2）：保存當前柱的信息（柱子號、應該搬動的最下面一塊盤子的號，和它的目標柱），以備當障礙清除后回到現在的柱子繼續搬，將當前柱轉換為礙事的盤子所在的柱子。假設這樣若干步后，我們將7號盤子從A搬到了C，此時，保存當前柱號的棧一定是空了，我們該怎么辦呢？ C++數據結構學習:遞歸(2.2)

　　顯而易見的，轉換當前柱為B，把6號盤子搬到C。由此可得出（規律3）：假設當前的問題規模為n，搬動第n個盤子到C后，問題規模減1，當前柱轉換到另一個柱子，最下面的盤子的目標柱為C。

更多內容請看C/C++技術專題數據結構數據結構教程專題，或　　綜上，我們已經把這個問題解決了，可以看出，要害是如何確定當前柱需要移動多少盤子，這個問題請大家自己考慮，給出如下例程，因為沒有經過任何優化，本人的編碼水平又比較低，所以這個函數很慢——比遞歸的還慢10倍。

　　#include

　　#include

　　using namespace std;

　　class Needle

　　{
　　
　　public:
　　
　　Needle() { a.push_back(100); }//每一個柱子都有一個底座
　　
　　void push(int n) { a.push_back(n); }
　　
　　int top() { return a.back(); }

　　int pop() { int n = a.back(); a.pop_back(); return n; }

　　int movenum(int n) { int i = 1;while (a[i] > n) i++; return a.size() - i; }

　　int size() { return a.size(); }

　　int Operator [] (int n) { return a[n]; }

　　PRivate:

　　vector a;

　　};

　　void Hanoi(int n)

　　{

　　Needle needle[3], ns;//3個柱子，ns是轉換柱子時的保存棧，借用了Needle的棧結構

　　int source = 0, target, target_m = 2, disk, m = n;

　　for (int i = n; i > 0; i--) needle[0].push(i);//在A柱上放n個盤子

　　while (n)//問題規模為n，開始搬動

　　{

更多內容請看C/C++技術專題數據結構數據結構教程專題，或　　if (!m) { source = ns.pop(); target_m = ns.pop();

　　m = needle[source].movenum(ns.pop()); }//障礙盤子搬走后，回到原來的當前柱

　　if (m % 2) target = target_m; else target = 3 - source - target_m;//規律1的實現

　　if (needle[source].top() < needle[target].top())//當前柱頂端盤子可以搬動時，移動盤子

　　{

　　disk = needle[source].top();m--;

　　cout << disk << " move " << (char)(source + 0x41) << " to "<< (char)(target + 0x41) << endl;//顯示搬動過程

　　needle[target].push(needle[source].pop());//在目標柱上面放盤子

　　if (disk == n) { source = 1 - source; target_m = 2; m = --n; }規律3的實現

　　}

　　else//規律2的實現

　　{

　　ns.push(needle[source][needle[source].size() - m]);

　　ns.push(target_m); ns.push(source);

　　m = needle[target].movenum(needle[source].top());

　　target_m = 3 - source - target; source = target;

　　}

　　}
　　　　}

更多內容請看C/C++技術專題數據結構數據結構教程專題，或　　這個算法實現比遞歸算法復雜了很多（遞歸算法在網上、書上隨便都可以找到），而且還慢很多，似乎是多余的，然而，這是有現實意義的。

我不知道現在還在搬64個盤子的僧人是怎么搬的，不過我猜想一定不是先遞歸到1個盤子，然后再搬——等遞歸出來，估計胡子一打把了（能不能在人世還兩說）。我們一定是馬上決定下一步怎么搬，就如我上面寫的那樣，這才是人的正常思維，而用遞歸來思考，想出來怎么搬的時候，黃瓜菜都涼了。

　　正像我們做事的方法，雖然我今生今世完不成這項事業，但我一定要為后人完成我能完成的，而不是在那空想后人應該怎么完成——假如達不到最終的結果，那也一定保證向正確的方向前進，而不是呆在原地空想。

　　由此看出，計算機編程實際上和正常的做事步驟的差距還是很大的——我們的做事步驟假如直接用計算機來實現的話，其實并不能最優，原因就是，實際中的相關性在計算機中可能并不存在——比如人腦的逆推深度是有限的，而計算機要比人腦深很多，論記憶的準確性，計算機要比人腦強很多。這也導致了一個普通的程序員和一個資深的程序員寫的算法的速度經常有天壤之別。因為，后者知道計算機喜歡怎么思考。

更多內容請看C/C++技術專題數據結構數據結構教程專題，或

上一篇：C++數據結構學習:遞歸(3)

下一篇：C++數據結構學習:遞歸(3.1)