2015算法-第三章遞歸

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

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

遞歸算法實(shí)現(xiàn)機(jī)制子程序?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)用時(shí)，用棧方式管理調(diào)用子程序時(shí)的返回地址7（包括局部變量）。值回傳方式實(shí)參與形參的兩種數(shù)據(jù)傳送方式：值參與變參變參回傳值，有兩種方法：兩次值傳送方式按指定類型為變參設(shè)置相應(yīng)的

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

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

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

f(n1)

f(n2)

f(1)

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

f(integer

n)integer

y;if

(n0)

then

return

1endify

n

f(n1);return

y;end

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

fn;fn

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

代表現(xiàn)場(chǎng)信息，棧元素由現(xiàn)場(chǎng)信息和參數(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è)計(jì)遞歸設(shè)計(jì)需滿足的要求遞歸求解的通用表現(xiàn)形式遞歸的幾個(gè)典型例子16遞歸設(shè)計(jì)需滿足的要求可以用遞歸求解的問(wèn)題應(yīng)滿足：?jiǎn)栴}P的描述涉及規(guī)模，即P(size)；規(guī)模發(fā)生變化后，問(wèn)題的性質(zhì)不變；問(wèn)題的解決有出口。遞歸求解的通用表現(xiàn)形式Procedure

P(參數(shù)表)if

遞歸出口簡(jiǎn)單操作thenelse簡(jiǎn)單操作call

P簡(jiǎn)單操作endifend

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

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

n5,(m1,

m2,

m3,

m4,

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

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

m2

….

…mn1mnm…….m1

m2

……mn1nm

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

m2

……knap(mmn,

n1)mn1有解

knap(m,n)

true無(wú)解

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

一個(gè)

的古老

_

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

of

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

輔助

目標(biāo)柱

柱25n1,

X1Zn2,

X1YX2ZY1Zn階Hanoi問(wèn)題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問(wèn)題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

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

0

0

00

1

1

1

1

1

_

_（右邊至少有兩個(gè)空位），要求通過(guò)棋子移動(dòng)最終成為0

1

0

1

0

1

0

1

0

1.29棋子移動(dòng)問(wèn)題移動(dòng)規(guī)則每次必須同時(shí)移動(dòng)相鄰兩個(gè)棋子顏色不限，移動(dòng)方向不限每次移動(dòng)必須跳過(guò)若干棋子不能調(diào)換這兩個(gè)棋子的位置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;遞歸過(guò)程：n4時(shí)；move (n,n1)

(2n1,2n2)；move

(2n1,2n)

(n,n1);call

chess(n1);A(9)A(4)A(10)A(5)棋子的移動(dòng)問(wèn)題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個(gè)元素的全排列設(shè)A={a1,a2,…,an}是要進(jìn)行排列的n個(gè)元素的集合，n1n2輸出a1輸出a1a2a2a1輸出a1a2a3a1a3a2a2a1a3a2a3a1a3a2a1a3a1a2n3分析n3，排列按如下步驟進(jìn)行：a1之后跟a2,a3的所有全排列；在上述全排列里，a1和a2位置互換；(3)在上述全排列里，a1和a3位置互換。34求n個(gè)元素的全排列range(A)

a1range(A1),

a2range(A2),,

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

kn

then

print(A)elseA(k)

A(i)repeatendifprocedure

range(A,k,n)

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

i

k

to

n

do

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

A(i)call

range(A,k1,n)缺省時(shí)，認(rèn)為形參是in型，其值變化時(shí)不回傳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ù)拆分任何一個(gè)大于1的自然數(shù)n，總可以拆分成若干個(gè)小于n的自然數(shù)之和，試求n的所有拆分。n2n3211312111413112111122n438自然數(shù)拆分（正整數(shù)拆分）n66

15114

113

1112111111112212324222333940自然數(shù)拆分（正整數(shù)拆分）拆分的結(jié)果用一維數(shù)組A保存；對(duì)任意自然數(shù)的所有拆分方式，依據(jù)A(1)的值，可以分為n/2類；第i類第一行元素是A[1]i，A[2]ni；為保證拆分不重復(fù)，A中元素是非降的；下一次的拆分，用A的下標(biāo)來(lái)控制，而不是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)系式的計(jì)算遞歸算法的時(shí)間復(fù)雜度分析K階線性齊次遞歸關(guān)系式的解法求n個(gè)元素的最大元問(wè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遞歸算法的時(shí)間復(fù)雜度分析求n個(gè)元素的最大元問(wè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時(shí)間復(fù)雜性46n

2

2

C

n

2T

C1T

n

n

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

H(n)if

n2

then

HnelseHH(n1)H(n2)endifend

H49時(shí)間復(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時(shí)，稱此