漢諾塔1到9最快分別是幾次?？梢愿嬖V我計(jì)算方法嗎？河內(nèi)塔是一個(gè)迭代問(wèn)題。假設(shè)河內(nèi)塔從第一列移動(dòng)到最后一列（目標(biāo)列）的最快次數(shù)是f（x）。顯然，f（1）=1，f（2）=3。然后我們可以把整個(gè)過(guò)程分為三個(gè)

漢諾塔1到9最快分別是幾次?？梢愿嬖V我計(jì)算方法嗎？

河內(nèi)塔是一個(gè)迭代問(wèn)題。假設(shè)河內(nèi)塔從第一列移動(dòng)到最后一列（目標(biāo)列）的最快次數(shù)是f（x）。顯然，f（1）=1，f（2）=3。然后我們可以把整個(gè)過(guò)程分為三個(gè)部分。首先，我們可以將第一層和第二層移動(dòng)到中間列（過(guò)渡列），用最快的f（2）步驟2，將第三層移動(dòng)到最后一列（目標(biāo)列），最快的步驟是3，將第一層和第二層移動(dòng)到最后一列，最快的步驟是f（2），因此f（3）=f（2）1f（2）=7，依此類推，f（4）=f（3）1f（3）=15 f（5）=f（4）1 f（4）=31 f（6）=f（5）1 f（5）=63 f（7）=f（6）1 f（6）=127 f（8）=f（7）1 f（7）=255 f（9）=f（8）1 f（8）=511 PS。如果學(xué)習(xí)了序列，則可以得到更一般的遞推公式f（x1）=2*f（x）1。此外，還可以得到通式F（x）=2^x-1

漢諾塔遞歸算法？

1//河內(nèi)塔

2#include<stdio。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）//移動(dòng)借助C列

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

12 Hanoi（N-1，B，a，c） //然后將B列上的N-1個(gè)板移到c

13}

14}

15 int main（）

16{int N

17 printf（“input the number of disks:”）

18 scanf（%d“，&n）

19 Hanoi（N，“a”，“B”，“c”）

20 return 0

21}

]復(fù)制代碼

理論上是可能的，但是有些算法使用遞歸描述將更加簡(jiǎn)潔和清晰，盡管性能比迭代慢。目前，一些用遞歸轉(zhuǎn)化為迭代的算法比較復(fù)雜，如典型的漢諾塔問(wèn)題。雖然在線流程圖例已通過(guò)迭代求解，但其正確性尚未得到研究者的證實(shí)。目前，遞歸仍然被廣泛地用于實(shí)現(xiàn)它。