漢諾塔的遞歸算法不理解？讓河內(nèi)塔板為D1、D2、D3，。。。DN從上到下，（n>0）記住，前k個(gè)板是s（k）（k>1）遞歸。假設(shè)前n-1個(gè)板是s（n-1）。要把板從a移到C，我們只需要使用橋B

漢諾塔的遞歸算法不理解？

讓河內(nèi)塔板為D1、D2、D3，。。。DN從上到下，（n>0）記住，前k個(gè)板是s（k）（k>1）遞歸。假設(shè)前n-1個(gè)板是s（n-1）。要把板從a移到C，我們只需要使用橋B。具體的移動方法如下：（1）s（n-1）：a=>B（2）DN:a=>C（3）s（n-1）：B=>C實(shí)際上是一個(gè)有四個(gè)參數(shù)f（n，a，B，C）的函數(shù)。第一步和第三步實(shí)際上又回到了n-1層河內(nèi)塔的問題。以第一步為例，將前n-2個(gè)板看作一個(gè)整體s（n-2），問題變成將板從a移到B，此時(shí)需要以C為橋。移動方法如下：（4）s（n-2）：a=>C（5）d（n-1）：a=>B（6）s（n-2）：a=>C（5）d（n-1）：a=>B（6）s（n-2）：s（n-1）：a=>C實(shí)際上，C=>B和（1）、（2）、（3）的步驟沒有區(qū)別，只是[bridge]B和C被交換：通過（1）、（2）、（3）總結(jié)函數(shù)：（1）f（n-1，a，C，B）//參數(shù)a是原始位置，C是橋，B是目的地（2）n:a=>C//從原始位置取底板=>目的地（3）f（n-1，B，a，C）//參數(shù)B是原始位置，a是橋，C是目的地。遞歸解很容易理解。更困難的是使用非遞歸方法。實(shí)際上，所有的遞歸算法都可以轉(zhuǎn)化為非遞歸算法。一些低級語言（如匯編）沒有遞歸算法。