C++數據結構學習:遞歸(2-1)

2019-11-17 05:04:06

字體：大中小

來源：轉載

供稿：網友

漢諾塔的非遞歸解法

似乎這個問題的最佳解法就是遞歸，假如你想用棧來消解掉遞歸達到形式上的消除遞歸，你還是在使用遞歸的思想，因此，他本質上還是一個遞歸的算法。我們這本黃皮書在談論到“什么情況使用遞歸”的時候，在“3.問題的解法是遞歸的”這里面，就這樣說了“有些問題只能用遞歸的方法來解決，一個典型的例子就是漢諾塔”。
C++數據結構學習:遞歸(2-1)

但我堅信，假如一個問題能用分析的辦法解決——遞歸實際上就是一個分析解法，能將問題分解成－1規模的同等問題和移動一個盤子，假如這樣分解下去一定會有解，最后分解到移動1號盤子，問題就解決了——那么我也應該能用綜合的辦法解決，就是從當前的狀態來確定怎樣移動，而不是逆推得到決定。這是對實際工作過程的一個模擬，試想假如讓我們去搬盤子，我們肯定不會用遞歸來思考現在應該怎么搬——只要8個盤子，我們腦子里的“工作棧”恐怕就要溢出了——我們要立即決定怎么搬，而不是從多少步之后的情景來知道怎么搬。下面我們通過模擬人的正向思維來尋找這個解法。

假設如下搬7個盤子的初始狀態（選用7個是因為我曾經寫出了一個1～6結果正確的算法，而在7個的時候才發現一個條件的選擇錯誤，具體大家自己嘗試吧），我們唯一的選擇就是搬動1號盤子，但是我們的問題是向B搬還是向C搬？

顯然，我們必須將7號盤子搬到C，在這之前要把6號搬到B，5號就要搬到C，……以此類推，就會得出結論（規律1）：當前柱最上面的盤子的目標柱應該是，從當前柱上“需要搬動的盤子”最下面一個的目標柱，向上交替交換目標柱到它時的目標柱。

就是說，假如當前柱是A，需要移動m個盤子，從上面向下數的第m個盤子的目標柱是C，那么最上面的盤子的目標柱就是這樣：if (m % 2) 目標和第m個盤子的目標相同（C）;else 目標和第m個盤子的目標不同（B）。接下來，我們需要考慮假如發生了阻塞，該怎么辦，請繼續關注下一期的文章。