2015算法-第三章遞歸

遞歸的例子從前有座山，山上有座廟，廟里有個老和尚講故事，講的是從前有座山，山上有座廟，廟里有個老和尚講故事，講的是從前有座山，山上有座廟，廟里有個老和尚講故事，講的是……

……遞歸定義一個過程直接地或間接地調(diào)用自己，則稱這個過程是遞歸的過程。遞歸算法在計算機理論和實際應(yīng)用中都具有重要意義。設(shè)計和分析思路清晰，實現(xiàn)容易，但效率較低主要內(nèi)容遞歸算法實現(xiàn)機制遞歸轉(zhuǎn)非遞歸(略)遞歸算法設(shè)計遞歸關(guān)系式的計算(略)3.1

遞歸算法實現(xiàn)機制子程序?qū)崿F(xiàn)原理子程序調(diào)用的一般形式值回傳方式子程序調(diào)用的

操作遞歸程序?qū)崿F(xiàn)原理5子程序調(diào)用的一般形式主程序Call

A1：子程序A主程序子程序ACall

A1：Call

A2：6(b)n次調(diào)用(a)1次調(diào)用一子程序調(diào)用的主程序Call

A1：子程序A子程序BCall

B2：子程序A主程序子程序BCall

A2：Call

B1：(c)嵌套調(diào)用(d)平行調(diào)用子程序調(diào)用時，用棧方式管理調(diào)用子程序時的返回地址7（包括局部變量）。值回傳方式實參與形參的兩種數(shù)據(jù)傳送方式：值參與變參變參回傳值，有兩種方法：兩次值傳送方式按指定類型為變參設(shè)置相應(yīng)的

空間。執(zhí)行調(diào)用時，實參值傳送給變參，返回時變參值傳送給實參。地址傳送方式在

將變參設(shè)置成一個地址，調(diào)用時將實參的地址傳送給變參。本章

的遞歸問題對變參采用兩次值傳送方8式。procedure

f(integer

n)integer

y;if

(n0)then

return

1;else

y

nf

(n1);return

y;endifend

f遞歸求階乘的算法procedure

g(n)：integer

fn;fn

f(4);return

fn;end

g9子程序調(diào)用的

操作執(zhí)行調(diào)用時：返回地址進(jìn)棧，開辟子程序的局部變量空間為子程序準(zhǔn)備數(shù)據(jù)，即將實參值賦值給形參指令流轉(zhuǎn)入子程序執(zhí)行返回操作時：將變參或函數(shù)的值保存到回傳變量中從棧頂取出返回地址按地址返回將回傳變量中的值傳送給相應(yīng)的變量或位置上1011遞歸程序?qū)崿F(xiàn)原理原理：一個遞歸過程的執(zhí)行類似于多個子程序的嵌套調(diào)用。定義：遞歸過程直接地或間接地調(diào)用自己本身代碼。特征：有遞歸調(diào)用、有遞歸出口。特點：設(shè)計和分析思路清晰，實現(xiàn)容易，效率較低。為了保證遞歸調(diào)用的正確性，需要保存調(diào)用點的現(xiàn)場（返回地址、局部變量、被調(diào)用函數(shù)的參數(shù)等），以便正確地返回，并且按先進(jìn)后出的原則來管理這些信息。高級語言編譯程序是利用棧來實現(xiàn)的。f(n)

f(n1)

f(n2)

f(1)

f(0)…調(diào)用返回調(diào)用點PnPn-1Pn-2P11調(diào)用時執(zhí)行入棧操作保存現(xiàn)場，返回時執(zhí)行出棧操作恢復(fù)現(xiàn)場.12procedure

f(integer

n)integer

y;if

(n0)

then

return

1endify

n

f(n1);return

y;end

f遞歸求階乘的算法主程序：integer

fn;fn

f(4);13計算4!遞歸過程圖示：下圖中Pi

代表現(xiàn)場信息，棧元素由現(xiàn)場信息和參數(shù)構(gòu)成f(4)4f(3)Push(e4)f(3)3f(2)Push(e3)f(2)2f(1)Push(e2)f(4)4f(3)f(3)

3f(2)f(2)

2f(1)

24

6f(1)

1f(0)

12P4

4P3

3P4

4P11Pop(P22P33P44f(1)1f(0)

f(0)1Push(e1)e1)Pop(P2

2P3

3P4

4e2)Pop(e3)Pop(e4)14153.3

遞歸算法設(shè)計遞歸設(shè)計需滿足的要求遞歸求解的通用表現(xiàn)形式遞歸的幾個典型例子16遞歸設(shè)計需滿足的要求可以用遞歸求解的問題應(yīng)滿足：問題P的描述涉及規(guī)模，即P(size)；規(guī)模發(fā)生變化后，問題的性質(zhì)不變；問題的解決有出口。遞歸求解的通用表現(xiàn)形式Procedure

P(參數(shù)表)if

遞歸出口簡單操作thenelse簡單操作call

P簡單操作endifend

P規(guī)?；蚺c規(guī)模相關(guān)的參數(shù)降低規(guī)模的處理對遞歸結(jié)果的處理1718幾個典型例子簡單的0/1背包問題n階Hanoi塔問題棋子移動問題n個元素的全排列自然數(shù)拆分（正整數(shù)拆分）19例3.3

簡單的0/1背包問題背包可容納物品的最大質(zhì)量為m，現(xiàn)有n件物品，質(zhì)量分別為m1,m2,,mn，mi均為正整數(shù)，要從n件物品中挑選若干件，使放入背包的質(zhì)量之和正好為m.簡單的0/1背包問題例：m20,

n5,(m1,

m2,

m3,

m4,

m5)(3,5,8,9,10)(x1,x2,x3,x4,x5)(1,0,1,1,0)m18?

m28?注：對于第i件物品要么取，要么舍，不能取一部分，因此這個問題可能有解，也可能無解。布爾函數(shù)20問題分析knap(m,n)m初始：……m1

m2

….

…mn1mnm…….m1

m2

……mn1nm

mtruemnmmn1,即還有可選物品…….m1

m2

……knap(mmn,

n1)mn1有解

knap(m,n)

true無解

knap(m,n)

knap(m,n1)mn

mm…….m1

m2

……mn1knap(m,n1)n1否則

false21function

knap(m,

n)case:mmn0:

knap

true:mmn0:

if

n1

thenif

knap(mmn,n1)

true

thenknap

trueelse knap

knap(m,n1)endifelse

knap

false

endif:mmn0:

if

n1

then

knap

knap(m,n1)else

knap

false

;

endifendcase22例3.4

一個

的古老

_

漢諾塔在貝拿勒斯（在三根寶石針。北部）的圣廟里，一塊黃銅板上插著教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔(Tower

of

Hanoi）。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。假如每秒鐘一次，移完這些金片需要5845億年以上。n階Hanoi塔問題有n個圓盤依半徑從小到大自上而下地套在柱子A上，柱子B和C沒有圓盤。要求將A上的盤子換到C上，每次只移動一個，且不允許將大圓盤壓在小圓盤的上面。24尋找遞歸出口XYZHanoi(n,X,Y,Z)圓盤數(shù)量源柱

輔助

目標(biāo)柱

柱25n1,

X1Zn2,

X1YX2ZY1Zn階Hanoi問題Hanoi(n,X,Y,Z)n3,Hanoi(2,X,Z,Y)X3ZHanoi(2,Y,X,Z)X26YZ27CABCABABC(1)Hanoi(n1,X,Z,Y)(2)

Xn

Z(3)

Hanoi(n1,Y,X,Z)XYZ圓盤

源柱

輔助

目標(biāo)數(shù)量

柱

柱Hanoi(n,X,Y,Z)28n階Hanoi問題procedure

Hanoi(n,

X,

Y,

Z)if

(n1)

then

move(X,

Z)elseHanoi(n1,

X,

Z,

Y)move(X,

Z)Hanoi(n1,

Y,

X,

Z)endifEnd

Hanoi例3.5

棋子移動問題有2n個棋子(n4)排成一行，白子用0表示，黑子用1表示，例如n5時初始狀態(tài)為0

0

0

00

1

1

1

1

1

_

_（右邊至少有兩個空位），要求通過棋子移動最終成為0

1

0

1

0

1

0

1

0

1.29棋子移動問題移動規(guī)則每次必須同時移動相鄰兩個棋子顏色不限，移動方向不限每次移動必須跳過若干棋子不能調(diào)換這兩個棋子的位置30尋找遞歸出口n400001111_

_step1000_

_11101(4,5)

(9,10)step20001011_

_1(8,9)

(4,5)step30_

_1011001(2,3)

(8,9)step4010101_

_01(7,8)

(2,3)step5_

_01010101(1,2)

(7,8)31n50000011111_

_step10000_

_111101(5,6)

(11,12)step200001111_

_01(9,10)

(5,6)32n6step1step2000000111111_

_00000_

_1111101 (6,7)

(13,14)0000011111__01

(11,12)

(6,7)chess(n)遞歸出口：n4;遞歸過程：n4時；move (n,n1)

(2n1,2n2)；move

(2n1,2n)

(n,n1);call

chess(n1);A(9)A(4)A(10)A(5)棋子的移動問題Procedure

Chess(n)if

n4

thenmove (4,5)

(9,10)move (8,9)

(4,5)move (2,3)

(8,9)move (7,8)

(2,3)move (1,2)

(7,8)elsemove (n,

n+1)

(2n+1,

2n+2)move (2n1,

2n)

(n,

n+1)call

Chess(n1)endif33遞歸出口遞歸調(diào)用End

Chess例3.6

求n個元素的全排列設(shè)A={a1,a2,…,an}是要進(jìn)行排列的n個元素的集合，n1n2輸出a1輸出a1a2a2a1輸出a1a2a3a1a3a2a2a1a3a2a3a1a3a2a1a3a1a2n3分析n3，排列按如下步驟進(jìn)行：a1之后跟a2,a3的所有全排列；在上述全排列里，a1和a2位置互換；(3)在上述全排列里，a1和a3位置互換。34求n個元素的全排列range(A)

a1range(A1),

a2range(A2),,

anrange(An)集合A用數(shù)組實現(xiàn)range(A,1,n)：遞歸出口：range(A,n,n)遞歸調(diào)用：使得集合所有元素都可以作為前綴出現(xiàn)Aa1Aa2Aan35求n個元素的全排列if

kn

then

print(A)elseA(k)

A(i)repeatendifprocedure

range(A,k,n)

遞歸出口，打印整個數(shù)組A。for

i

k

to

n

do

A(i)與A(k)值互換A(k)

A(i)call

range(A,k1,n)缺省時，認(rèn)為形參是in型，其值變化時不回傳end

range36ocall

range(A,1,n)range(A,1,3)If

13

then

print(A)elsefor

i

1

to

3

doA(1)A(i);call

range(A,2,3)

略abcA={a,

b,

c}1)

i1,

aa

A{a,b,c}2)

i2,

bb

A{a,b,c}acb3)

i3,

bc

A{a,c,b}bac4)

i2,

a

b

A{b,a,c}5)

i2,

aa

A{b,a,c}bca6)

i3,

ac

A{b,c,a}range(A,2,3)…for

i2

to

3doA(2)A(i);call

range(A,3,3)

略range(A,3,3)if

33

print(A)略7)

i3,

ac

A{c,b,a}cba8)

i2,

bb

A{c,b,a}cab9)

i3,

ba

A{c,a,b}例3.7

自然數(shù)拆分任何一個大于1的自然數(shù)n，總可以拆分成若干個小于n的自然數(shù)之和，試求n的所有拆分。n2n3211312111413112111122n438自然數(shù)拆分（正整數(shù)拆分）n66

15114

113

1112111111112212324222333940自然數(shù)拆分（正整數(shù)拆分）拆分的結(jié)果用一維數(shù)組A保存；對任意自然數(shù)的所有拆分方式，依據(jù)A(1)的值，可以分為n/2類；第i類第一行元素是A[1]i，A[2]ni；為保證拆分不重復(fù)，A中元素是非降的；下一次的拆分，用A的下標(biāo)來控制，而不是A中的元素值；發(fā)生下一次拆分（遞歸調(diào)用）的判斷條件。自然數(shù)拆分（正整數(shù)拆分）算法procedure

split(t)j

t;

L

A(j)end

splitprocedure

main(n)end

main41輸出已產(chǎn)生的一種拆分本次拆分的起始位置本次拆分的數(shù)值split(2)Print:1,3j2;

L3i在1~3/2之間

i1:

A[2]1;A[3]

2;main(4)i在1~4/2之間

i1:

A[1]1;A[2]3;i2:

A[1]2;A[2]2;1split(3)Print:1,1,2j3;

L2i在1~2/2之間

i1:

A[3]

1;A[4]

12split(4)Print:1,1,1,1j4;

L1i在1~1/2之間3split(2)Print:2,2j2;

L3i在2~2/2之間442433.4

遞歸關(guān)系式的計算遞歸算法的時間復(fù)雜度分析K階線性齊次遞歸關(guān)系式的解法求n個元素的最大元問題Procedure MAX

(A,i,

j)if

ij

then

return

A(i)

endifif

ji1

thenif

A(i)A(j)

then

return

A(i)else

return

A(j)

;

endifelsek

(ij)/2m1

MAX(i,

k)m2

MAX(k1,

j)if

m1m2

then

return

m1else

return

m2;

endifendifend

MAX44遞歸算法的時間復(fù)雜度分析求n個元素的最大元問題二分法Max(A,1,n)A(1)A(2)

A(n/2)

A(n/21)

A(n)Max(A,1,

n/2)Max(A,n/21,n)max45時間復(fù)雜性46n

2

2

C

n

2T

C1T

n

n

2247臺階問題一個樓有n個臺階，有一個人上樓時有時一次跨一個臺階，有時跨兩個臺階，寫算法，計算此人有幾種不同的上樓方法，并分析算法的時間復(fù)雜度。48臺階問題procedure

H(n)if

n2

then

HnelseHH(n1)H(n2)endifend

H49時間復(fù)雜性

n

2T n

1

T

n

2

n

2T

(n)

2T

(n

1)

22

T

(n

2)

...

2n1T

(1)

(2n

)T

n

C所以，50k階線性齊次遞歸關(guān)系式的解法定義3.1

遞歸關(guān)系式其中，ck0，ci1，bi是給定常數(shù)，稱為k階線性常系數(shù)遞歸關(guān)系式。當(dāng)d(n)0時，稱此