漢諾塔遞歸算法？1//河內(nèi)塔2#包括和酒店。H>3 void Hanoi（int n，char a，char b，char c）//這里表示在b列的幫助下將a列上的圖版移到c列4{if（1==n）

漢諾塔遞歸算法？

1//河內(nèi)塔

2#包括和酒店。H>

3 void Hanoi（int n，char a，char b，char c）//這里表示在b列的幫助下將a列上的圖版移到c列

4{if（1==n）//如果是圖版，將a列上的圖版移到c列

5{

6 Printf（%c-->%cn，a，c）

7}

8 else

9{

10 Hanoi n-1，a，c，b）//move n-1 plates on column a to column B with the column C

11 printf（%C-->%Cn“，a，C）//將a列的最后一塊板移到C列

12 Hanoi（n-1，B，a，C）//然后將B列的n-1板移到C

13}

14}

15 int main（）

16{int n

17 printf輸入磁盤數(shù)：”）

18 scanf（%d“，&n）

19 Hanoi（n，%a”，%B“，%C”）

20 return 0

21}

復(fù)制代碼

讓Hanoi塔板為D1，D2，D3，。。。DN自上而下，n>0。注意，前k個板是s（k）（k>1）遞歸。假設(shè)前n-1塊板是s（n-1）塊。要將板從a移到C，只需要使用橋B。具體的移動方法是：（1）s（n-1）：a=>B（2）DN:a=>C（3）s（n-1）：B=>C實際上是一個具有四個參數(shù)f（n，a，B，C）的函數(shù)。第一步和第三步實際上又回到了n-1層河內(nèi)塔的問題。以第一步為例，將前n-2個板看作一個整體s（n-2），問題變成將板從a移到B，此時需要以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實際上，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是目的地。遞歸解很容易理解。更困難的是使用非遞歸方法。實際上，所有的遞歸算法都可以轉(zhuǎn)化為非遞歸算法。一些低級語言（如匯編）沒有遞歸算法。