算法分析：傻瓜式理解漢諾塔遞歸問題

一、漢諾塔問題規(guī)則

設(shè)a、b、c是三個塔座，
開始時，a上有n個圓盤自下而上，從大到小地疊放在一起。
現(xiàn)要求將a上的圓盤移到b上，仍按相同順序疊放

規(guī)則1：每次只能移動一個圓盤
規(guī)則2：任何時刻都不許將較大的圓盤壓在較小的圓盤上
規(guī)則1：在滿足規(guī)則1和2的基礎(chǔ)上，可將圓盤移動至a、b、c任一塔座上

二、漢諾塔問題算法原理分析

1. 將n-1個圓盤放到輔助塔c上去
2. 將塔a上第n個最大的圓盤放到最終塔b上去
3. 最后將輔助塔c上的n-1個圓盤放到最終塔b上去

看到這也許還很懵，不著急，下面我來簡要地講解下
第一步，我們可以將問題簡化為只有兩部分圓盤的問題即，
n-1部分的圓盤和第n個的圓盤（這里我們把n-1個圓盤看作一個整體）
第二步，現(xiàn)在問題就簡化為只有兩個圓盤的漢諾塔問題，一個大圓盤和一個小圓盤，那么現(xiàn)在我們通過畫圖來簡要看下他們之間如何進行移動


這里值得注意的是我們并不去考慮如何移動這n-1個圓盤的具體過程，而是理清其遞歸算法。
這樣我們非常清晰明了地將漢諾塔問題中n個圓盤的移動問題分解成了兩次n-1個圓盤的移動問題，這里可以采取遞歸的方式去完成。

三、漢諾塔問題的遞歸算法

總結(jié)

以上是生活随笔為你收集整理的算法分析：傻瓜式理解汉诺塔递归问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。