C++遞歸問(wèn)題--羅漢塔

我覺(jué)得這樣可能比較好理解一點(diǎn)

創(chuàng)新互聯(lián)主要從事做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)來(lái)安,10年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來(lái)電咨詢建站服務(wù):18980820575

有三根柱子，標(biāo)記為A, B, C

先要理解函數(shù)hanoi(n,A,B,C) 的意思是借助于B柱子將A上面的n個(gè)盤(pán)子移到C上面，必須充分對(duì)應(yīng)到各個(gè)參數(shù)。

如果想將n個(gè)盤(pán)子從A柱子移動(dòng)到C柱子

可以分為這樣幾個(gè)步驟

（1）必須將A最下面也就是最大的那個(gè)盤(pán)子移動(dòng)到C最下面

首先需要借助C柱子將A上面的n-1個(gè)盤(pán)子移動(dòng)到B上面

就是hanoi(n-1,A,C,B) 。

此時(shí)A上面只有一個(gè)最大的盤(pán)子，B上面按序放著n-1個(gè)盤(pán)子，C上面有0個(gè)盤(pán)子。

（2）將A上面的盤(pán)子移動(dòng)到C上面，只需要1步。

此時(shí)A上面有0個(gè)盤(pán)子，B上面按序放著n-1個(gè)盤(pán)子，C上面只有一個(gè)最大的盤(pán)子。

（3）最后借助于A柱子將B上面n-1個(gè)盤(pán)子移到C上面即可

就是hanoi(n-1,B,A,C) 。

所以實(shí)際上數(shù)學(xué)推導(dǎo)公式為f(n)=2f(n-1)+1，其中f(1)=1，f(n)表示將n個(gè)盤(pán)子從A柱子移到C柱子的步數(shù)

如果還不明白的歡迎h(huán)i我 啊

6塊羅漢塔a移動(dòng)到c,每次只能移動(dòng)1個(gè)

move from A?to B

move from A?to C

move from B?to C

move from A?to B

move from C?to A

move from C?to B

move from A?to B

move from A?to C

move from B?to C

move from B?to A

move from C?to A

move from B?to C

move from A?to B

move from A?to C

move from B?to C

move from A?to B

move from C?to A

move from C?to B

move from A?to B

move from C?to A

move from B?to C

move from B?to A

move from C?to A

move from C?to B

move from A?to B

move from A?to C

move from B?to C

move from A?to B

move from C?to A

move from C?to B

move from A?to B

move from A?to C

move from B?to C

move from B?to A

move from C?to A

move from B?to C

move from A?to B

move from A?to C

move from B?to C

move from B?to A

move from C?to A

move from C?to B

move from A?to B

move from C?to A

move from B?to C

move from B?to A

move from C?to A

move from B?to C

move from A?to B

move from A?to C

move from B?to C

move from A?to B

move from C?to A

move from C?to B

move from A?to B

move from A?to C

move from B?to C

move from B?to A

move from C?to A

move from B?to C

move from A?to B

move from A?to C

move from B?to C

運(yùn)用遞歸的辦法：

A為當(dāng)前位置，C為目標(biāo)位置，B為臨時(shí)存放位置。

base case: 只有1個(gè)方塊，則直接 move from A to C（直接從A移動(dòng)到C）。

other case: 當(dāng)不止1個(gè)方塊時(shí)的遞歸： 假如有N個(gè)方塊，把 （1,2,3,4...到N-1）的方塊看成一個(gè)整體，第N個(gè)方塊看做一個(gè)個(gè)體。想把它們?nèi)繌腁轉(zhuǎn)移到C則要3個(gè)步驟：

先把 (1.2,3,4...N-1) 大整體放到臨時(shí)位置B。（此時(shí)n 頭上無(wú)障礙，且C為空）

把N（最大方塊）從 A 移動(dòng)到C。

最后把?(1.2,3,4...N-1) 大整體 也放到C。

遞歸時(shí)需要注意的點(diǎn)： 3個(gè)位置（當(dāng)前位置，目標(biāo)位置，臨時(shí)存放位置）

（1）當(dāng)要把 （1到N-1）大整體轉(zhuǎn)移到? ！臨時(shí)位置！時(shí)， （1到N-1）大塊的當(dāng)前位置和 N 的位置相同， 但（1到N-1）的 ！目標(biāo)位置！ 是 N 的 臨時(shí)存放位置。

（2）當(dāng)要把（1到N-1）大整體 從 臨時(shí)位置 放回 N 頭上的時(shí)候， （1到N-1）的當(dāng)前位置為 N 的臨時(shí)位置，?（1到N-1）的 目標(biāo)位置與 N 的目標(biāo)位置一致。

//c++ 代碼：

#include iostream

using namespace std;

void hm(int cu, int mb, int wa, int num)

{

if (num == 1)

{

? cout "move from " cu " to " mb endl; //基礎(chǔ)情況

}

else

{

? hm(cu, wa, mb, num - 1);//把1 到 N-1 的大整體移動(dòng)到N的臨時(shí)位置，大方塊目前和N在一起，所以當(dāng)前位置一致，N的臨時(shí)位置則為大方塊的目標(biāo)位置。同理可得大方塊的臨時(shí)位置為N的目標(biāo)位置。

? cout "move from " cu " to " mb endl;//再把N 從 現(xiàn)在的位置移動(dòng)到 目標(biāo)位置

? hm(wa, mb, cu, num - 1);//把大方塊移回N頭上，大方塊目前在N的臨時(shí)位置，所以N的臨時(shí)位置=大方塊的當(dāng)前位置，單目標(biāo)位置一致。 同理可得大方塊的臨時(shí)位置為N的當(dāng)前位置

}

}

void main()

{

int num;

cout "塔有幾層？" endl;

cin num;

int cu = 1, mb = 2, wa = 3;? // cr:目前， mb：目標(biāo), wa：臨時(shí)

hm(1, 2, 3, num);

}

怎樣用C語(yǔ)言編羅漢塔？

你可以看看這里的評(píng)論：

有我的程序在下面：

void?NuoYiWei(int?FromTa,int?ToTa)//只挪動(dòng)最上面一個(gè)的子函數(shù)

{

TopPoint[FromTa]--;//這是個(gè)每個(gè)塔層高度的記錄數(shù)組，從哪個(gè)塔挪走一個(gè)，哪個(gè)塔高就減少一個(gè)。

DuiZhan[ToTa][TopPoint[ToTa]]=DuiZhan[FromTa][TopPoint[FromTa]];//這是三個(gè)塔上面數(shù)據(jù)的記錄，沒(méi)有用0表示，這里把數(shù)據(jù)從挪出的塔傳到挪到的塔上。

DuiZhan[FromTa][TopPoint[FromTa]]=0;//原來(lái)挪出的塔的最上層沒(méi)有東西了，恢復(fù)0值。

TopPoint[ToTa]++;//挪到的那個(gè)塔層數(shù)自加1

}

void?Nuo(int?FromTa,int?MidTa,int?ToTa,int?NeedMove)//漢諾塔主程序，給定初始條件和塔高度

{

if(NeedMove=2)//如果需要挪動(dòng)的塔層高度還大于等于2層

{

Nuo(FromTa,ToTa,MidTa,(NeedMove-1));//先把最下面一個(gè)除外的上面的N-1個(gè)都挪到中間的塔，怎么挪的，就是迪歸調(diào)用這個(gè)函數(shù)實(shí)現(xiàn)的。

NuoYiWei(FromTa,ToTa);//然后把最低下一個(gè)諾到目標(biāo)塔上。

Nuo(MidTa,FromTa,ToTa,(NeedMove-1));//最后把挪到中間塔上的N-1個(gè)都挪到目標(biāo)塔上（這里你要先假設(shè)這樣的函數(shù)能實(shí)現(xiàn)本功能）

}

else

{

NuoYiWei(FromTa,ToTa);//就剩一個(gè)要挪動(dòng)了就直接挪動(dòng)

}

}

這個(gè)函數(shù)是在C++里寫(xiě)的，如果用C語(yǔ)言還要注意些。

我這里還有用C寫(xiě)的漢諾塔的程序，你給我郵箱sxt9840210@163.com發(fā)郵件索要吧，說(shuō)清楚要些什么。

網(wǎng)頁(yè)名稱：羅漢塔函數(shù)python,什么是羅漢塔
網(wǎng)頁(yè)鏈接：http://chinadenli.net/article35/dsijopi.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、搜索引擎優(yōu)化、軟件開(kāi)發(fā)、網(wǎng)站營(yíng)銷、外貿(mào)網(wǎng)站建設(shè)、小程序開(kāi)發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)