數(shù)據(jù)結(jié)構(gòu)(c++)--遞歸-文庫(kù)吧
2025-07-10 09:07 本頁(yè)面
【正文】 軸移動(dòng)至 c軸，可遞歸求解 Hanoi(n1, b, a, c)。 a b c1 號(hào)盤(pán)2 號(hào)盤(pán)3 號(hào)盤(pán)12/44 例： 分析 Hanoi塔問(wèn)題移動(dòng)圓盤(pán)的次數(shù) 設(shè) T(n)表示 n個(gè)圓盤(pán)的 Hanoi塔問(wèn)題移動(dòng)圓盤(pán)的次數(shù)，顯然 T(0)=0，對(duì)于 n0的一般情況采用如下分治策略： （ 1）將 1至 n1號(hào)盤(pán)從 a 軸移動(dòng)至 b 軸，可遞歸求解Hanoi(n1, a, c, b)； （ 2）將 n號(hào)盤(pán)從 a 軸移動(dòng)至 c 軸； （ 3）將 1至 n1號(hào)盤(pán)從 b軸移動(dòng)至 c軸，可遞歸求解 Hanoi(n1, b, a, c)。 在（ 1）與（ 3）中需要移動(dòng)圓盤(pán)次數(shù) T(n1)，（ 2）需要移動(dòng)一次圓盤(pán)?？傻萌缦碌年P(guān)系： T(n)=2T(n1)+1 展開(kāi)上式可得： T(n) =2T(n1)+1 =2[2T(n2)+1]+1 =22T(n2)+1+2 …… =2nT(nn)+1+2+…+2 n1 =2n1 13/44 二、漢諾塔問(wèn)題的遞歸算法 void Hanoi(int n, char x, char y, char z) { if(n = = 1) move(x, 1, z)。 else{ Hanoi(n1, x, z, y)。 move(x, n, z)。 Hanoi(n1, y, x, z)。 } } 0 1 2 3 4 5 6 7 8 9 void move (char x, int n, char y) { cout移動(dòng) n號(hào)盤(pán)子 從柱子 x到柱子 y。 } 14/44 Hanoi(n, x, y, z) 可以分成三個(gè)子問(wèn)題： 問(wèn)題 (n1, x, z, y) //將 X柱上的 n1個(gè)圓盤(pán)借助 Z柱移到 Y柱上，此時(shí) X柱只剩下第 n個(gè)圓盤(pán)； 問(wèn)題 ( n, x， z) //將 X柱上的第 n個(gè)移動(dòng)到 Z柱 問(wèn)題 (n1, y, x, z) //將 Y柱上的 n1個(gè)圓盤(pán)借助 X柱移到 Z柱上； n=1時(shí)可以直接求解 15/44 void Hanoi(int n, char x, char y, char z) { if(n = = 1) move(x, 1, z)。 else{ Hanoi(n1, x, z, y)。 move(x, n, z)。 Hanoi(n1, y, x, z)。 } } 01 2 3 4 5 6 7 8 9 0,3,a,b,c a b c 1,2,4,5 1 遞歸 層次 運(yùn)行語(yǔ) 句序號(hào) 遞歸工作棧狀態(tài) （返址，盤(pán)號(hào)， x,y,z） 塔與圓盤(pán)的狀態(tài) 盤(pán)號(hào) 1 2 3 16/44 void Hanoi(int n, char x, char y, char z) { if(n = = 1) move(x, 1, z)。 else{ Hanoi(n1, x, z, y)。 move(x, n, z)。 Hanoi(n1, y, x, z)。 } } 01 2 3 4 5 6 7 8 9 0,3,a,b,c a b c 1,2,4,5 2 遞歸 層次 運(yùn)行語(yǔ) 句序號(hào) 遞歸工作棧狀態(tài) （返址，盤(pán)號(hào)， x,y,z） 塔與圓盤(pán)的狀態(tài) 6,2,a,c,b 盤(pán)號(hào) 1 2 3 17/44 void Hanoi(int n, char x, char y, char z) { if(n = = 1) move(x, 1, z)。 else{ Hanoi(n1, x, z, y)。 move(x, n, z)。 Hanoi(n1, y, x, z)。 } } 01 2 3 4 5 6 7 8 9 0,3,a,b,c a b c 1,2,3,9 3 遞歸 層次 運(yùn)行語(yǔ) 句序號(hào) 遞歸工作棧狀態(tài) （返址，盤(pán)號(hào)， x,y,z） 塔與圓盤(pán)的狀態(tài) 6,2,a,c,b 6,1,a,b,c 盤(pán)號(hào) 1 2 3 18/44 void Hanoi(int n, char x, char y, char z) { if(n = = 1) move(x, 1, z)。 else{ Hanoi(n1, x, z, y)。 move(x, n, z)。 Hanoi(n1, y, x, z)。 } } 01 2 3 4 5 6 7 8 9 0,3,a,b,c a b c 6,7 2 遞歸 層次 運(yùn)行語(yǔ) 句序號(hào) 遞歸工作棧狀態(tài) （返址，盤(pán)號(hào)， x,y,z） 塔與圓盤(pán)的狀態(tài) 6,2,a,c,b 盤(pán)號(hào) 1 2 3 19/44 void Hanoi(int n, char x, char y, char z) { if(n = = 1)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1