什么是漢諾塔 漢諾塔1到9最快分別是幾次。可以告訴我計(jì)算方法嗎?
漢諾塔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)它。