算法與程序設(shè)計(jì)課件

演算法與程式設(shè)計(jì)第1章演算法基礎(chǔ)學(xué)習(xí)要點(diǎn):理解演算法的概念。理解什麼是程式，程式與演算法的區(qū)別和內(nèi)在聯(lián)繫。掌握演算法的計(jì)算複雜性概念。掌握演算法漸近複雜性的數(shù)學(xué)表述。掌握用偽代碼描述演算法的方法。第1章演算法基礎(chǔ)1.1演算法（Algorithm）1.2演算法分析1.3演算法的運(yùn)行時(shí)間1.1演算法(Algorithm)1.演算法的定義2.演算法的性質(zhì)3.演算法的表示4.演算法舉例5.程式6.冒泡排序演算法7.演算法正確性證明演算法通常指可以用來(lái)解決的某一類問(wèn)題的步驟，這些步驟必須是明確的和有效的，而且能夠在有限步之內(nèi)完成的。1.演算法的定義一般來(lái)說(shuō)，“用演算法解決問(wèn)題”可以利用電腦幫助完成。1.1演算法(Algorithm)“演算法”的大陸中文名稱出自西元前1世紀(jì)成書(shū)的《周髀算經(jīng)》；英文名稱Algorithm來(lái)自於9世紀(jì)波斯數(shù)學(xué)家al-Khwarizmi；歐幾裏得演算法被人們認(rèn)為是史上第一個(gè)演算法。1.演算法的定義1.1演算法(Algorithm)2.演算法的性質(zhì)1）可行性2）確定性3）有窮性4）有輸入資訊的說(shuō)明5）有輸出結(jié)果的說(shuō)明3.演算法的表示

描述演算法可以有不同的方式,常用的有自然語(yǔ)言、程式框圖、程式設(shè)計(jì)語(yǔ)言、偽代碼等.1.1演算法(Algorithm)可行性：演算法中描述的操作都可通過(guò)有限次的基本運(yùn)算來(lái)實(shí)現(xiàn)。確定性：演算法中每個(gè)步驟含義明確，無(wú)二義性。有窮性：一個(gè)演算法必須保證在有限個(gè)操作步驟執(zhí)行後終止。輸入：一個(gè)演算法應(yīng)具有零個(gè)或多個(gè)輸入。輸出：一個(gè)演算法應(yīng)具有一個(gè)或多個(gè)輸出。2.演算法的性質(zhì)1.1演算法(Algorithm)自然語(yǔ)言就是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，可以是漢語(yǔ)或英語(yǔ)或其他語(yǔ)言。除了那些很簡(jiǎn)單的問(wèn)題外，一般不用自然語(yǔ)言描述演算法。（1）自然語(yǔ)言3.演算法的表示1.1演算法(Algorithm)1.1演算法(Algorithm)概念：偽代碼是用介於自然語(yǔ)言和電腦語(yǔ)言之間的文字和符號(hào)來(lái)描述演算法。特點(diǎn)：它如同一篇文章一樣，自上而下地寫(xiě)下來(lái)。每一行(或幾行)表示一個(gè)基本操作。用處：適用於設(shè)計(jì)過(guò)程中需要反復(fù)修改時(shí)的流程描述。（2）偽代碼3.演算法的表示1.1演算法(Algorithm)偽代碼規(guī)則說(shuō)明：見(jiàn)教材P3a）縮進(jìn)形式表示塊結(jié)構(gòu)，主要體現(xiàn)在迴圈和條件控制結(jié)構(gòu)上。b）while,do-while,for迴圈結(jié)構(gòu)，以及if-then-else條件結(jié)構(gòu)採(cǎi)用類似高級(jí)語(yǔ)言中相應(yīng)表示。c）符號(hào)“//”後是注釋部分。d）多重賦值表達(dá)為i←j←e。e）所有變數(shù)不經(jīng)顯式說(shuō)明均為局部變數(shù)。f）通過(guò)數(shù)組名後跟下標(biāo)訪問(wèn)數(shù)組元素；符號(hào)“..”表示數(shù)組中元素的範(fàn)圍。A[i]A[i..j]3.演算法的表示1.1演算法(Algorithm)g）複合數(shù)據(jù)可以組織成由屬性或域組成的對(duì)象，通過(guò)功能變數(shù)名稱後跟方括號(hào)括住的對(duì)象名訪問(wèn)某個(gè)特定域。Length[A]h）通過(guò)傳值將參數(shù)傳給一個(gè)過(guò)程；當(dāng)傳遞一個(gè)對(duì)象時(shí)，只拷貝指向表示對(duì)象的數(shù)據(jù)的指針，不拷貝它的各個(gè)域。i）“and”和“or”是布爾運(yùn)算符。j）break語(yǔ)句表示將控制轉(zhuǎn)移到含有break的最內(nèi)層迴圈語(yǔ)句後面的第一條語(yǔ)句。3.演算法的表示令士兵從1～3報(bào)數(shù)，結(jié)果最後一個(gè)士兵報(bào)2；令士兵從1～5報(bào)數(shù)，結(jié)果最後一個(gè)士兵報(bào)3；令士兵從1～7報(bào)數(shù)，結(jié)果最後一個(gè)士兵報(bào)2；【例1】韓信點(diǎn)兵你能算出韓信至少有多少兵嗎？1.1演算法(Algorithm)4.演算法舉例【例1】韓信點(diǎn)兵1.列出除以3餘2的數(shù)：2，5，8，11，14，17，20，23，26…2.列出除以5餘3的數(shù)：3，8，13，18，23，28…3.這兩列數(shù)中，首先出現(xiàn)的公共數(shù)是8，3與5的最小公倍數(shù)是15。兩個(gè)條件合併成一個(gè)就是8＋15×整數(shù)，列出這一串?dāng)?shù)是8，23，38，…，4.列出除以7餘2的數(shù)

：9，16，23，30…5.得出符合題目條件的最小數(shù)是23。6.我們已把題目中三個(gè)條件合併成一個(gè)：被105除餘23的數(shù)。1.1演算法(Algorithm)4.演算法舉例【例1】韓信點(diǎn)兵演算法描述三人同行七十稀，五樹(shù)梅花廿一枝，七子團(tuán)圓正半月，除百零五便得知。

這首詩(shī)的意思是：用3除所得的餘數(shù)乘上70，加上用5除所得餘數(shù)乘以21，再加上用7除所得的餘數(shù)乘上15，結(jié)果大於105就減去105的倍數(shù)，這樣就知道所求的數(shù)了。1.1演算法(Algorithm)4.演算法舉例最初記述這類演算法的是一本名叫《孫子算經(jīng)》的書(shū)。這類演算法的名稱也很多，宋朝周密叫它“鬼穀算”，又名“隔牆算”；楊輝叫它“剪管術(shù)”；而比較通行的名稱是“韓信點(diǎn)兵”。這在數(shù)學(xué)史上是極有名的問(wèn)題，外國(guó)人一般把它稱為“中國(guó)剩餘定理”?！纠?】韓信點(diǎn)兵1.1演算法(Algorithm)4.演算法舉例【點(diǎn)評(píng)】瞭解一些經(jīng)典演算法是我們的學(xué)習(xí)目標(biāo)。

【例2】

求1+2+3+4+5+6累加和演算法1.按照逐一相加的演算法進(jìn)行.第一步:計(jì)算1+2,得3;第二步:將第一步中的運(yùn)算結(jié)果3與3相加得6;第三步:將第二步中的運(yùn)算結(jié)果6與4相加得10;第四步:將第三步中的運(yùn)算結(jié)果10與5相加得15;第五步:將第四步中的運(yùn)算結(jié)果15與6相加得21.4.演算法舉例太繁瑣1.1演算法(Algorithm)演算法2.可以運(yùn)用下麵公式直接計(jì)算.第一步:取n=6;第二步:計(jì)算;第三步:輸出計(jì)算結(jié)果.【點(diǎn)評(píng)】演算法1繁瑣,步驟較多;演算法2簡(jiǎn)單，步驟較少。找出好的演算法是我們的學(xué)習(xí)目標(biāo)。4.演算法舉例

【例2】

求1+2+3+4+5+6累加和1.1演算法(Algorithm)4.演算法舉例【例3】

求1×2×3×4×5S1：先求1×2，得到結(jié)果2S2：將步驟1得到的乘積2再乘以3，得到結(jié)果6S3：將6再乘以4，得24S4：將24再乘以5，得120如果要求1×2×…×1000，則要寫(xiě)999個(gè)步驟太繁瑣1.1演算法(Algorithm)

S1：令p=1S2：令i=2S3：計(jì)算p×i，乘積仍放在變數(shù)p中，可表示為：p=p×iS4：i的值加1，即i=i+1。S5：如果i不大於5，返回重新執(zhí)行步驟S3以及其後的步驟S4和S5；否則，演算法結(jié)束。最後得到p的值就是結(jié)果。4.演算法舉例【例3】

求1×2×3×4×51.1演算法(Algorithm)

如果題目改為：求1×3×5×……×1000：S1：p=1S2：i=3S3：p=p×iS4：i=i+2S5：若i≤1000，返回S3。否則，結(jié)束。演算法簡(jiǎn)練4.演算法舉例1.1演算法(Algorithm)Jiechen(n)p←1i←2whilei<=ndop←p*ii=i+1returnpLianchen(n)p←1i←3whilei<=ndop←p*ii=i+2returnp*n4.演算法舉例1.1演算法(Algorithm)5.程式（program）程式是演算法用某種程式設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程式可以不滿足演算法的性質(zhì)(3)。例如操作系統(tǒng)，是一個(gè)在無(wú)限迴圈中執(zhí)行的程式，因而不是一個(gè)演算法。史上第一次編寫(xiě)程式是AdaByron於1842年為巴貝奇分析機(jī)編寫(xiě)求解伯努利方程的程式，因此AdaByron被大多數(shù)人認(rèn)為是世界上第一位程式員。1.1演算法(Algorithm)6.冒泡排序（bubblesort）（1）自然語(yǔ)言描述將相鄰的兩個(gè)元素進(jìn)行比較，如果左邊的元素大於右邊元素值，則將這兩個(gè)元素進(jìn)行交換，否則不改變位置，重複這個(gè)過(guò)程，直到比較到最後一個(gè)元素為止。1.1演算法(Algorithm)6.冒泡排序（bubblesort）（2）偽代碼描述BUBBLE-SORT(A)1fori←1tolength[A]2doforj←lenth[A]downtoi+13doifA[j]<A[j-1]4thenexchangeA[j]?A[j-1]1.1演算法(Algorithm)6.冒泡排序（bubblesort）【例】已知序列A={5，2，4，6，1，3}1524

631253

461235

4612345

612345

6用程式如何描述冒泡排序演算法？1.1演算法(Algorithm)6.冒泡排序（bubblesort）voidbubblesort(intA[],intn){inti,j,temp;for(i=0;i<n;i++)for(j=n-1;j>i;j--)if(A[j]<A[j-1]){temp=A[j];A[j]=A[j-1];A[j-1]=temp;}}1.1演算法(Algorithm)（3）程式描述7.演算法正確性證明迴圈中始終為真值的部分被稱為迴圈不變式。利用迴圈不變式的結(jié)果可以證明演算法的正確性。迴圈不變式1.1演算法(Algorithm)1.2演算法分析

演算法分析是對(duì)一個(gè)演算法所需的計(jì)算資源進(jìn)行預(yù)測(cè)。最重要的計(jì)算資源是時(shí)間和空間資源。時(shí)間和空間資源=演算法複雜度演算法的時(shí)間複雜度T(n)；（所需時(shí)間資源）演算法的空間複雜度S(n)。（所需空間資源）其中n是問(wèn)題的規(guī)模（輸入大?。?。[注]不特別說(shuō)明情況下，對(duì)演算法只分析時(shí)間複雜度。1.2演算法分析1.演算法分析的基本法則2.

冒泡排序演算法分析3.不同情況下的演算法時(shí)間複雜度1.演算法分析的基本法則（1）for/while迴圈循環(huán)體內(nèi)計(jì)算時(shí)間*迴圈次數(shù)；（2）嵌套迴圈循環(huán)體內(nèi)計(jì)算時(shí)間*所有迴圈次數(shù)；（3）順序語(yǔ)句各語(yǔ)句計(jì)算時(shí)間相加；（4）if-else語(yǔ)句if語(yǔ)句計(jì)算時(shí)間和else語(yǔ)句計(jì)算時(shí)間的較大者。1.2演算法分析2.

冒泡排序演算法分析BUBBLE-SORT(A)cost

1fori←1tolength[A]c12doforj←lenth[A]downtoi+1c13doifA[j]<A[j-1]c24thenexchangeA[j]?A[j-1]c31.2演算法分析timesn+1sum(n-i+1)sum(n-i)ti3.不同情況下的演算法時(shí)間複雜度（1）最壞情況下的時(shí)間複雜度Tmax(n)=max{T(I)|size(I)=n}（2）最好情況下的時(shí)間複雜度

Tmin(n)=min{T(I)|size(I)=n}（3）平均情況下的時(shí)間複雜度

Tavg(n)=

其中I是問(wèn)題的規(guī)模為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率。1.2演算法分析3.不同情況下的演算法時(shí)間複雜度BUBBLE-SORT(A)cost

1fori←1tolength[A]c12doforj←lenth[A]downtoi+1c13doifA[j]<A[j-1]c24thenexchangeA[j]?A[j-1]c31.2演算法分析timesn+1sum(n-i+1)sum(n-i)ti演算法最壞情況下的運(yùn)行時(shí)間是任一輸入運(yùn)行時(shí)間的上界並且經(jīng)常出現(xiàn)，所以對(duì)一個(gè)演算法我們關(guān)心的是最壞情況下的時(shí)間複雜度。3.不同情況下的演算法時(shí)間複雜度1.2演算法分析1.3演算法的運(yùn)行時(shí)間1.演算法漸近複雜性2.漸近表示3.演算法分析中常見(jiàn)的複雜性函數(shù)4.演算法分類1.3演算法的運(yùn)行時(shí)間T(n)

,asn

;(T(n)-t(n))/T(n)0

，asn;稱t(n)是T(n)的漸近性態(tài)，為演算法的漸近複雜度。在數(shù)學(xué)上，t(n)是T(n)的漸近運(yùn)算式，是T(n)略去低階項(xiàng)留下的主項(xiàng)。它比T(n)簡(jiǎn)單。1.演算法漸近複雜性1.演算法漸近複雜性舉例：T（N）=3N2+4NlogN+7t（N）=3N21.3演算法的運(yùn)行時(shí)間2.漸近表示在下面的討論中，對(duì)所有n，f(n)

0，g(n)

0。（1）漸近上界記號(hào)OO(g(n))={f(n)|存在正常數(shù)c和n0使得對(duì)所有n

n0有：0

f(n)

cg(n)}（2）漸近下界記號(hào)

(g(n))={f(n)|存在正常數(shù)c和n0使得對(duì)所有n

n0有：0

cg(n)

f(n)}1.3演算法的運(yùn)行時(shí)間（3）緊漸近界記號(hào)

(g(n))={f(n)|存在正常數(shù)c1,c2和n0使得對(duì)所有n

n0有：c1g(n)

f(n)

c2g(n)}

2.漸近表示1.3演算法的運(yùn)行時(shí)間3.演算法分析中常見(jiàn)的複雜性函數(shù)1.3演算法的運(yùn)行時(shí)間小規(guī)模數(shù)據(jù)大規(guī)模數(shù)據(jù)4.演算法分類多項(xiàng)式時(shí)間演算法（polynomialtimealgorithm)：用多項(xiàng)式來(lái)對(duì)計(jì)算時(shí)間限界的演算法。O(1)<O(lbn)<O(n)<O(nlbn)<O(n2)<O(n3)指數(shù)時(shí)間演算法（exponentialtimealgorithm)：計(jì)算時(shí)間用指數(shù)函數(shù)限界的演算法。O(2n)<O(n!)<O(nn)1.3演算法的運(yùn)行時(shí)間第1章演算法基礎(chǔ)學(xué)習(xí)要點(diǎn):理解演算法的概念。理解什麼是程式，程式與演算法的區(qū)別和內(nèi)在聯(lián)繫。掌握演算法的計(jì)算複雜性概念。掌握演算法漸近複雜性的數(shù)學(xué)表述。掌握用偽代碼描述演算法的方法。練習(xí)1.下麵的程式段違反了演算法的()原則。

voidsam()

{intn=2;

while(!odd(n))n+=2;

printf(n);

}A.有窮性B.確定性C.可行性D.健壯性練習(xí)2.下面函數(shù)中漸進(jìn)時(shí)間最小的是()。A.T1(n)=n+nlogn

B.T2(n)=2n+nlogn

C.T3(n)=n2-logn

D.T4(n)=n+100logn3.下述函數(shù)中漸進(jìn)時(shí)間最小的是()。A.T1(n)=nlog2n+100log2n

B.T2(n)=2nlog2n-100log2n

C.T3(n)=n2-100log2n

D.T4(n)=4nlog2n-100log2n51第2章分治法2.1遞歸2.2分治法2.3分治法應(yīng)用實(shí)例遞推與遞歸報(bào)數(shù)問(wèn)題一隊(duì)士兵從排頭向排尾報(bào)數(shù)是一個(gè)遞推問(wèn)題an=an-1+1如果要求從排尾向排頭報(bào)數(shù)呢？要求排頭報(bào)數(shù)為1是一個(gè)遞歸問(wèn)題an=an-1+1a1=1德羅斯特效應(yīng)德羅斯特效應(yīng)（Drosteeffect）是指一張圖片的某個(gè)部分與整張圖片相同，如此產(chǎn)生無(wú)限迴圈。它是遞歸的一種視覺(jué)形式。2.1遞歸

2.1.1遞歸的概念【定義】若一個(gè)對(duì)象部分地包含它自己，或用它自己給自己定義，則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過(guò)程直接地或間接地調(diào)用自己，則稱這個(gè)過(guò)程是遞歸的過(guò)程。2.1.1遞歸的概念2.1.1遞歸的概念二叉樹(shù)：二叉樹(shù)是數(shù)據(jù)元素的有窮集合，它或者為空集（空二叉樹(shù)），或者由一個(gè)根元素和其下的兩棵互不相交的二叉左子樹(shù)和右子樹(shù)構(gòu)成。單鏈表結(jié)點(diǎn)：

typedefstructnode {datatypedata

structnode*Link; }slnode2.1.2遞歸的應(yīng)用能採(cǎi)用遞歸解決的問(wèn)題通常有這樣的特徵：為求解規(guī)模為N的問(wèn)題，設(shè)法將它分解成一些規(guī)模較小的問(wèn)題，這些規(guī)模較小的問(wèn)題也能採(cǎi)用同樣的分解和綜合方法，分解為規(guī)模更小的問(wèn)題，當(dāng)N=1時(shí)，能直接得到解。下麵來(lái)看幾個(gè)實(shí)例。582.1.2遞歸的應(yīng)用【例1】階乘函數(shù)

階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸的二個(gè)要素59【例1】階乘函數(shù)Factorial(n)ifn=0thenreturn1returnn*Factorial(n-1)Factorial(n)fn=f1=1fori←2tondofn=i*f1f1=fnreturnfn2.1.2遞歸的應(yīng)用2.1.2遞歸的應(yīng)用【例2】Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：

fibonacci(n)if(n<=1)thenreturn1returnfibonacci(n-1)+fibonacci(n-2)

斐波那契數(shù)列的遞歸調(diào)用樹(shù)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)2.1.2遞歸的應(yīng)用遞歸演算法的一般形式：p(參數(shù)表)if（遞歸結(jié)束條件）可直接求解步驟；-----邊界條件

elsep（較小的參數(shù)）；------遞歸方程2.1.2遞歸的應(yīng)用【例3】整數(shù)劃分問(wèn)題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。例如，正整數(shù)6有如下不同的劃分：

6；

5+1；

4+2，4+1+1；

3+3，3+2+1，3+1+1+1；

2+2+2，2+2+1+1，2+1+1+1+1；

1+1+1+1+1+1。整數(shù)劃分問(wèn)題：求正整數(shù)n的不同劃分個(gè)數(shù)。

64(2)q(n,m)=q(n,n),mn;最大加數(shù)n1實(shí)際上不能大於n。因此，q(1,m)=1。(1)q(n,1)=1,n1;當(dāng)最大加數(shù)n1不大於1時(shí)，任何正整數(shù)n只有一種劃分形式，即

(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整數(shù)n的最大加數(shù)n1不大於m的劃分由n1=m的劃分和n1≤m-1的劃分組成。(3)q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1≤n-1的劃分組成。2.1.2遞歸的應(yīng)用【例3】整數(shù)劃分問(wèn)題如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，難以找到遞歸關(guān)係。因此考慮增加一個(gè)引數(shù)：將最大加數(shù)n1不大於m的劃分個(gè)數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸關(guān)係。2.1.2遞歸的應(yīng)用【例3】整數(shù)劃分問(wèn)題如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，難以找到遞歸關(guān)係。因此考慮增加一個(gè)引數(shù)：將最大加數(shù)n1不大於m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)係。正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。

2.1.2遞歸的應(yīng)用【例4】Hanoi塔問(wèn)題

設(shè)A,B,C是3個(gè)塔座。開(kāi)始時(shí)，在塔座A上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1,2,…,n,現(xiàn)要求將塔座A上的這一疊圓盤移到塔座C上，並仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤移至A,B,C中任一塔座上。2.1.2遞歸的應(yīng)用【例4】Hanoi塔問(wèn)題hanoi(n,A,B,C)ifn=1thenmove(A,1,C)elsehanoi(n-1,A,C,B)move(A,n,C)hanoi(n-1,B,A,C)

2.1.2遞歸的應(yīng)用當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單。此時(shí)，只要將編號(hào)為1的圓盤從塔座A直接移至塔座C上即可。當(dāng)n＞1時(shí)，①借C塔將A上的n-1盤子移到B塔座上；②將A上的第n個(gè)盤子移到C塔座上；③借A塔將B上的n-1盤子移到C塔座上。由此可見(jiàn)，n個(gè)圓盤的移動(dòng)問(wèn)題可分為2次n-1個(gè)圓盤的移動(dòng)問(wèn)題，這又可以遞歸地用上述方法來(lái)做。69運(yùn)行過(guò)程：⑴只有一個(gè)盤子的情況：(最簡(jiǎn)1步)⒈A---->C⑵有二個(gè)盤子的情況：(最簡(jiǎn)3步)⒈A---->B⒉A---->C⒊B---->C⑶有三個(gè)盤子的情況：(最簡(jiǎn)7步)⒈A---->C⒌B---->A⒉A---->B⒍B---->C⒊C---->B⒎A---->C⒋A---->C

2.1.2遞歸的應(yīng)用⑶有四個(gè)盤子的情況：(最簡(jiǎn)15步)

不同的盤子數(shù)運(yùn)行步驟是不一樣的，它是以一種2N-1的規(guī)律來(lái)遞增的。於是所以我們得出h(n)=2N-1，當(dāng)n=64時(shí)，需要的時(shí)間為18446744073709551615=5849億年2.1.2遞歸的應(yīng)用2.1.2遞歸的應(yīng)用

漢諾塔演算法的時(shí)間複雜度計(jì)算公式如下：【例4】Hanoi塔問(wèn)題該遞歸方程的解為O(2n)。遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明演算法的正確性，因此它為設(shè)計(jì)演算法、調(diào)試程式帶來(lái)很大方便。缺點(diǎn)：遞歸演算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是佔(zhàn)用的存儲(chǔ)空間都比非遞歸演算法要多。將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2.2分治法2.2.1分治法的基本思想2.2.1分治法的基本思想對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.2.1分治法的基本思想將求出的小規(guī)模的問(wèn)題的解合併為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.2.1分治法的基本思想將求出的小規(guī)模的問(wèn)題的解合併為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。

分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。

凡治眾如治寡，分?jǐn)?shù)是也。

----孫子兵法2.2.2分治法的適用條件分治法所能解決的問(wèn)題一般具有以下幾個(gè)特徵：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題；利用該問(wèn)題分解出的子問(wèn)題的解可以合併為該問(wèn)題的解；該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。因?yàn)閱?wèn)題的計(jì)算複雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特徵。這條特徵是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特徵反映了遞歸思想的應(yīng)用能否利用分治法完全取決於問(wèn)題是否具有這條特徵，如果具備了前兩條特徵，而不具備第三條特徵，則可以考慮貪心演算法或動(dòng)態(tài)規(guī)劃。這條特徵涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重複地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。DIVIDE&CONQUER(P)if(|P|<=c)thenreturnDSOLVE(P)//解決小規(guī)模的問(wèn)題

elsedividePintoksmallersubinstancesP1,P2,...,Pk

//分解問(wèn)題

fori←1tokdosi←DIVIDE&CONQUER(Pi)//遞歸的解各子問(wèn)題

S←COMBINE(s1,...,sk)//將各子問(wèn)題的解合併為原問(wèn)題的解

returnS}2.2.3分治法的基本步驟將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題的處理方法出自一種平衡(balancing)子問(wèn)題的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。792.2.4分治法的複雜性分析用分治法求解一個(gè)問(wèn)題，所需的時(shí)間是由四部分組成：（1）子問(wèn)題的個(gè)數(shù)k；（2）子問(wèn)題的大小n/m；（3）把這個(gè)問(wèn)題分解為子問(wèn)題所需時(shí)間f(n)；（4）子問(wèn)題合併為原問(wèn)題所需時(shí)間f(n)。

當(dāng)n等於m的冪時(shí)，通過(guò)迭代法求得該遞歸方程的解：2.2.4分治法的複雜性分析2.2.4分治法的複雜性分析對(duì)於T(n)=a*T(n/b)+c*nk;T(1)=c這樣的遞歸關(guān)係，有這樣的結(jié)論：當(dāng)(a>bk)

T(n)=O(n^(logb(a)));

當(dāng)(a=bk)

T(n)=O(nk*logn);

當(dāng)(a<bk)

T(n)=O(nk);2.3分治法應(yīng)用實(shí)例由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在演算法設(shè)計(jì)之中，並由此產(chǎn)生許多高效演算法。下麵來(lái)看幾個(gè)實(shí)例。83【例1】二叉查找演算法給定已按昇冪排好序的n個(gè)元素a[1:n]，現(xiàn)要在這n個(gè)元素中找出一特定元素v。若找到了返回在表中的位置；否則返回NIL表示查找不成功。分析：該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;分解出的子問(wèn)題的解可以合併為原問(wèn)題的解；分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。2.3.1二叉查找演算法842.3.1二叉查找演算法【實(shí)例】已知序列A={5，7，12，25，34，37，43，46，58，80，92，105}，要求查找v=46。第一步：設(shè)定i=1，j=12mid=└(i+j)/2┘=6v=46>A[mid]=37第二步：設(shè)定i=7,j=12mid=└(i+j)/2┘=9v=46<A[mid]=58第三步:設(shè)定i=7,j=8mid=└(i+j)/2┘=7v=46>A[mid]=43第四步：設(shè)定i=8,j=8mid=└(i+j)/2┘=8v=46=A[mid]=46返回8，找到。下取整若要查找35呢？【例1】二叉查找演算法偽代碼BinarySearch描述演算法：BinarySearch(A,v,low,high)whilelow<=highdomid←(low+high)/2ifv=A[mid]thenreturnmidelseifv>A[mid]thenlow←mid+1elsehigh←mid-1returnNIL演算法複雜度分析86【例1】二叉查找演算法A={5，7，12，25，34，37，43，46，58，80，92，105}二叉查找演算法的運(yùn)行過(guò)程可以形成是一棵二叉判定樹(shù)。試一下運(yùn)行過(guò)程，查找v=25v=5763124597128101158374392468010512572534在含有n個(gè)不同元素的集合中同時(shí)找出最大值和最小值。MAXMIN(A)max←min←A[1]fori←2tondoifA[i]>maxthenmax←A[i]elseifA[i]<minthenmin←A[i]returnmax&min2.3.2找最大值與最小值【例2】【問(wèn)題】最好情況下，最壞情況下，時(shí)間複雜度是？【例2】找最大值與最小值將分治策略應(yīng)用於此問(wèn)題，每次將問(wèn)題分解為大致相等的兩部分，分別找出最大最小值，再將這兩個(gè)子問(wèn)題的解組合成原問(wèn)題的解。當(dāng)每個(gè)子序列只含有1個(gè)或2個(gè)元素時(shí)，視為分解結(jié)束。子序列依次兩兩合併找出較長(zhǎng)序列的最大最小值，直到合併成原始序列?！纠?】找最大值與最小值給定元素集A={5，4，6，3，8}用分治演算法找出最大值和最小值。第一步：i=1,j=5mid=(1+5)/2=3第二步：i=1,j=3mid=(1+3)/2=2第三步：i=1,j=2

比較一次得到gmax=5,gmin=4第四步：i=3,j=3得到hmax=hmin=6邊界第五步：i=1,j=3

比較gmax和hmax

比較gmin和hmin

得到fmax=6，fmin=4第六步：i=4，j=5

比較一次，得到hmax=8,hmin=3第七步：i=1，j=5

比較得到全序列fmax=8，fmin=3【例2】找最大值與最小值合併【例2】找最大值與最小值Rec_MAXMIN(i,j,fmax,fmin)ifi=jthenfmax←fmin←A[i]ifi=(j-1)thenif(A[i]>A[j])thenfmax←A[i]fmin←A[j]elsefmax←A[j]fmin←A[i]【例2】找最大值與最小值elsemid←(i+j)/2Rec_MAXMIN(i,mid,gmax,gmin)Rec_MAXMIN(mid+1,j,hmax,hmin)fmax←max(gmax,hmax)fmin←min(gmin,hmin)【例2】找最大值與最小值該演算法元素比較次數(shù)即時(shí)間複雜度遞歸方程為：2.3.3Strassen矩陣乘法【例3】?jī)蓚€(gè)n×n的矩陣A和B的乘積矩陣C中的元素C[i,j]定義為:

依此定義來(lái)計(jì)算矩陣A和B的乘積矩陣C，則每計(jì)算C的一個(gè)元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的n2個(gè)元素所需的計(jì)算時(shí)間為O(n3)。矩陣相乘傳統(tǒng)方法：O(n3)【例3】Strassen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個(gè)大小相等的子矩陣。由此可將方程C=AB重寫(xiě)為：傳統(tǒng)方法：O(n3)分治法:由此可得：復(fù)雜度分析T(n)=O(n3)【例3】Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:為了降低時(shí)間複雜度，必須減少乘法的次數(shù)。復(fù)雜度分析T(n)=O(nlb7)=O(n2.81)較大的改進(jìn)【例3】Strassen矩陣乘法【例3】Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:O(n2.81)更快的方法??在Strassen之後又有許多演算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間複雜性。目前最好的計(jì)算時(shí)間上界是O(n2.376)是否能找到O(n2)的演算法？992.3.4整數(shù)相乘【例4】請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的演算法，可以進(jìn)行兩個(gè)n位整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)

效率太低分治法:X=Y=X=a10n/2+bY=c10n/2+d

XY=ac10n+(ad+bc)10n/2+bd

abcd複雜度分析T(n)=O(n2)

沒(méi)有改進(jìn)【例4】整數(shù)相乘請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的演算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)

效率太低分治法:XY=ac10n+(ad+bc)10n/2+bd

為了降低時(shí)間複雜度，必須減少乘法的次數(shù)。XY=ac10n+((a-b)(d-c)+ac+bd)10n/2+bdXY=ac10n+((a+b)(c+d)-ac-bd)10n/2+bd複雜度分析T(n)=O(nlb3)=O(n1.59)

較大的改進(jìn)細(xì)節(jié)問(wèn)題：兩個(gè)XY的複雜度都是O(nlb3)，但考慮到a+c,b+d可能得到m+1位的結(jié)果，使問(wèn)題的規(guī)模變大，故不選擇第2種方案。101【例4】整數(shù)相乘【例4】整數(shù)相乘請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的演算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)

效率太低分治法:O(n1.59)

較大的改進(jìn)更快的方法??如果將大整數(shù)分成更多段，用更複雜的方式把它們組合起來(lái)，將有可能得到更優(yōu)的演算法。最終的，這個(gè)思想導(dǎo)致了快速傅利葉變換(FastFourierTransform)的產(chǎn)生。該方法也可以看作是一個(gè)複雜的分治演算法。在一個(gè)2k×2k個(gè)方格組成的棋盤中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問(wèn)題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。覆蓋一個(gè)2k×2k棋盤要用到多少個(gè)L型骨牌？怎麼放置骨牌？2.3.5棋盤覆蓋【例5】當(dāng)k>0時(shí)，將2k×2k棋盤分割為4個(gè)2k-1×2k-1子棋盤(a)所示。遞歸地使用這種分割，直至棋盤簡(jiǎn)化為棋盤1×1。

【例5】棋盤覆蓋2.3.6歸並排序【例6】基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合併成為所要求的排好序的集合。【例】已知初始序列如下：（49，38，65，97，76，13，27）請(qǐng)利用歸併排序讓其昇冪有序?！纠?】歸並排序歸併的遞歸過(guò)程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]107【例6】歸並排序基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合併成為所要求的排好序的集合。

MergeSort(A,p,r)if(p<r)//至少有2個(gè)元素

thenq←(p+r)/2//取中點(diǎn)

MergeSort(A,p,q)MergeSort(A,q+1,r)Merge(A,p,q,r)複雜度分析T(n)=O(nlbn)漸進(jìn)意義下的最優(yōu)演算法歸併兩個(gè)已排好序的子序列Merge(A,p,q,r)n1←q-p+1n2←r-qcreatearraysL[1..n1+1]andR[1..n2+1]fori←1ton1doL[i]←A[p+i-1]forj←1ton2doR[j]←A[q+j]L[n1+1]←∞R[n2+1]←∞i←1j←1歸併兩個(gè)已排好序的子序列fork←ptordoifL[i]<R[j]thenA[k]←L[i]i←i+1elseA[k]←R[j]j←j+1時(shí)間複雜度分析：Merge過(guò)程的運(yùn)行時(shí)間O(n)歸並排序複雜性最壞時(shí)間複雜度：O(nlbn)平均時(shí)間複雜度：O(nlbn)輔助空間：O(n)【基本思想】對(duì)給定的初始數(shù)組a通常存在多個(gè)長(zhǎng)度大於1的已自然排好序的子數(shù)組段，將這些自然有序子數(shù)組段找出來(lái)，然後將相鄰的排好序的子數(shù)組段兩兩合併，構(gòu)成更大的排好序的子數(shù)組段；繼續(xù)合併相鄰排好序的子數(shù)組段，直至整個(gè)數(shù)組已排好序。自然歸並排序【例6】歸並排序【練習(xí)】利用歸併排序使序列A={5,2,4,7,1,3,2,6}昇冪有序。排序過(guò)程演示：S1:{5，2，4，7}{1，3，2，6}S2:{5，2}{4，7}{1，3}{2，6}S3:{5}{2}{4}{7}{1}{3}{2}{6}S4:{2，5}{4，7}{1，3}{2，6}S5:{2,4,5,7}{1,2,3,6}S6:{1,2,2,3,4,5,6,7}2.3.7快速排序【例7】【基本思想】對(duì)輸入的數(shù)組a[p:r]，按以下三個(gè)步驟進(jìn)行排序：（2）遞歸求解：通過(guò)遞歸調(diào)用快速排序演算法分別對(duì)A[p:q-1]和A[q+1:r]進(jìn)行排序。（3）合併：由於對(duì)A[p:q-1]和A[q+1:r]的排序是就地進(jìn)行的，所以在A[p:q-1]和A[q+1:r]都已排好的序後不需要執(zhí)行任何計(jì)算，A[p:r]就已排好序。（1）劃分：以A[r]（或A[p]）為基準(zhǔn)元素將A[p:r]劃分為3段A[p:q-1],A[q]和A[q+1:r]，使得A[p:q-1]中任何一個(gè)元素小於等於A[q],A[q+1:r]中任何一個(gè)元素大於等於A[q]。下標(biāo)q在劃分過(guò)程中確定?！纠?】快速排序【例】初始序列｛38，14，58，26，31｝，請(qǐng)利用快速排序使其昇冪有序?！纠?】快速排序在快速排序中，關(guān)鍵字較大的記錄一次就能交換到後面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少。QuickSort(A，p,r)if(p<r)q←Partition(A,p,r)QuickSort(A,p,q-1)//對(duì)左半段排序

QuickSort(A,q+1,r)//對(duì)右半段排序

【例7】快速排序

Partition(A，p,r)x←A[r]//基準(zhǔn)元素i←p-1forj←ptor-1doifA[j]<=xtheni←i+1exchangeA[i]?A[j]exchangeA[i+1]?A[r]returni+1快速排序示例初始

[722657884280724860]1：[26574248]60[80728872]2：[2642]48[57]60[80728872]3：[26]42485760[80728872]4：2642485760[72]72[8088]5：2642485760[72]72[80]886：[264248576072728088]快速排序可能會(huì)對(duì)相等值的記錄改變相對(duì)順序，所以是不穩(wěn)定排序演算法?！纠?】快速排序快速排序演算法的性能取決於劃分的對(duì)稱性。通過(guò)修改演算法partition，可以設(shè)計(jì)出採(cǎi)用隨機(jī)選擇策略的快速排序演算法。最壞時(shí)間複雜度：O(n2)平均時(shí)間複雜度：O(nlbn)輔助空間：O(n)或O(lbn)RANDOMIZED-PARTITION(A,p,r)i←RANDOM(p,r)exchangeA[r]?A[i]returnPARTITION(A,p,r)【例7】快速排序【練習(xí)】已知初始序列如下：（49，38，65，97，76，13，27）請(qǐng)利用快速排序讓其昇冪有序。2.3.8線性時(shí)間選擇【例8】【元素選擇問(wèn)題】給定線性序集中n個(gè)互不相同元素和一個(gè)整數(shù)i，1≤i≤n，要求找出這n個(gè)元素中第i小的元素?！纠恳阎蛄蠥={2,8,9,10,1,5,3,20,6,12,35,14,18},要求找出第8小元素。2.3.8線性時(shí)間選擇【例8】【元素選擇問(wèn)題】給定線性序集中n個(gè)互不相同元素和一個(gè)整數(shù)i，1≤i≤n，要求找出這n個(gè)元素中第i小的元素。

RandomizedSelect(A,p,r,i)if(p==r)thenreturnA[p]q←RandomizedPartition(A,p,r)k=q-p+1ifi=kthenreturnA[q]elseif(i<k)thenreturnRandomizedSelect(A,p,q-1,i)elsereturnRandomizedSelect(A,q+1,r,i-k)在最壞情況下，演算法RandomizedSelect需要O(n2)計(jì)算時(shí)間但可以證明，演算法RandomizedSelect可以在O(n)平均時(shí)間內(nèi)找出n個(gè)輸入元素中的第i小元素。方法一將n個(gè)輸入元素劃分成

n/5個(gè)組，每組5個(gè)元素，只可能有一個(gè)組不是5個(gè)元素。用任意一種排序演算法，將每組中的元素排好序，並取出每組的中位數(shù)，共n/5個(gè)。遞歸調(diào)用select來(lái)找出這n/5

個(gè)元素的中位數(shù)。如果

n/5

是偶數(shù)，就找它的2個(gè)中位數(shù)中較大的一個(gè)。以這個(gè)元素作為劃分基準(zhǔn)。【例8】線性時(shí)間選擇方法二122

Select(A,p,r,i)1.將n個(gè)元素分成

n/5個(gè)組，每組5個(gè)元素，另一組由剩餘的nmod5個(gè)元素組成。2.利用任一種排序演算法對(duì)

n/5個(gè)組進(jìn)行排序，並找出每組元素的中值。

3.對(duì)第2步找出的

n/5個(gè)中值，利用select遞歸找出這

n/5個(gè)中值的中值x4.利用修改的partition過(guò)程，以中值的中值作為劃分元素，對(duì)輸入數(shù)組進(jìn)行劃分。設(shè)k是劃分後左半部分元素?cái)?shù)再加上1。因此，x是第k小元素，且右半部分有n-k個(gè)元素。

5如果i=k，則返回x；如果i<k，則利用select在劃分的左半部分找第i個(gè)最小元素；如果i>k，則在右半部分找第i-k個(gè)最小元素。複雜度分析T(n)=O(n)【例8】線性時(shí)間選擇【例】已知序列A={2,8,9,10,1,5,3,20,6,12,35,14,18},要求找出第8小元素。2.3.9最接近點(diǎn)對(duì)問(wèn)題【例9】【最接近點(diǎn)對(duì)問(wèn)題】給定n(n≥2)個(gè)點(diǎn)的集合Q，找集合Q中一對(duì)點(diǎn)p1，p2，使得它們的距離在歐氏距離意義下最小。集合中的兩個(gè)點(diǎn)有可能重合，在這種情況下，這兩個(gè)點(diǎn)的歐氏距離為0。應(yīng)用在交通控制系統(tǒng)中，來(lái)檢測(cè)可能發(fā)生的碰撞?！纠?】最接近點(diǎn)對(duì)問(wèn)題先來(lái)考慮一維的情形：S中n個(gè)點(diǎn)化為x軸上的n個(gè)實(shí)數(shù)x1,x2,…,xn。最接近點(diǎn)對(duì)即為這n個(gè)實(shí)數(shù)中相差最小的2個(gè)實(shí)數(shù)。假設(shè)我們用x軸上某個(gè)點(diǎn)m將S劃分為2個(gè)子集S1和S2，基於平衡子問(wèn)題的思想，用S中各點(diǎn)座標(biāo)的中位數(shù)來(lái)作分割點(diǎn)。遞歸地在S1和S2上找出其最接近點(diǎn)對(duì){p1,p2}和{q1,q2}，並設(shè)d=min{|p1-p2|,|q1-q2|}，S中的最接近點(diǎn)對(duì)或者是{p1,p2}，或者是{q1,q2}，或者是某個(gè){p3,q3}，其中p3∈S1且q3∈S2。能否線上性時(shí)間內(nèi)找到p3,q3？S1={x∈S|x≤m}；S2={x∈S|x>m}【例9】最接近點(diǎn)對(duì)問(wèn)題如果S的最接近點(diǎn)對(duì)是{p3,q3}，即|p3-q3|<d，則p3和q3兩者與m的距離不超過(guò)d，即p3∈(m-d,m]，q3∈(m,m+d]。複雜度分析T(n)=O(nlbn)【例10】循環(huán)賽日程表有n=2k個(gè)運(yùn)動(dòng)員進(jìn)行網(wǎng)球循環(huán)賽，設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過(guò)為n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地用z這種對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。1234567821436587341278564321876556781234658721437856341287654321學(xué)習(xí)要點(diǎn)理解遞歸的概念。掌握設(shè)計(jì)有效演算法的分治策略。通過(guò)下麵的範(fàn)例學(xué)習(xí)分治策略設(shè)計(jì)技巧。（1）二分搜索技術(shù)；（2）找最大值與最小值；（3）Strassen矩陣乘法；（4）整數(shù)相乘；（5）歸併排序和快速排序；（6）線性時(shí)間選擇；（7）最接近點(diǎn)對(duì)問(wèn)題；（8）循環(huán)賽日程表。練習(xí)1.若總是以待排序列的最後一個(gè)元素作為基準(zhǔn)元素進(jìn)行快速排序，那麼最好情況下的時(shí)間複雜度是（）

A.O(lbn)B.O(n)C.O(nlbn)D.O(n2)2.若對(duì)27個(gè)元素只進(jìn)行三趟多路歸併排序，則選取的歸併路數(shù)是（）

A.2B.3C.4D.53.某演算法的計(jì)算時(shí)間可以用遞推式T(n)=2T(n/2)+n表示，則該演算法的時(shí)間複雜度為

A.O(lbn)B.O(nlbn)C.O(n)D.O(n2)練習(xí)4.演算法的有窮性指的是（）。

A.演算法程式的運(yùn)行時(shí)間是有限的

B.演算法程式所處理的數(shù)據(jù)是有限的

C.演算法程式的長(zhǎng)度是有限的

D.演算法只能被有限的用戶使用練習(xí)對(duì)於給定的一組關(guān)鍵字（18，2，16，30，8，28，4，10，20，6，12），按照下列演算法進(jìn)行遞增排序，寫(xiě)出每種演算法第一趟排序後得到的結(jié)果：快速排序（選最後一個(gè)記錄為基準(zhǔn)元素）得到__5__，二路歸併排序得到__6__。(5)A.10,6,18,8,4,2,12,20,16,30,28

B.4,2,6,10,8,12,28,30,20,16,18

C.2,8,4,10,612,16,30,20,18,28

D.6,10,8,28,20,18,2,4,12,30,16(6)A.2,12,16,8,28,30,4,6,10,18,20

B.2,12,16,30,8,28,4,10,6,20,18

C.12,2,16,8,28,30,4,6,10,28,18

D.12,2.10,20,6,18,4,16,30,8,28

7.將兩個(gè)長(zhǎng)度為n的遞增有序表歸併成一個(gè)長(zhǎng)度為2n的遞增有序表，最少需要進(jìn)行關(guān)鍵字比較()次。A.i

B.n-1

C.n

D.2n8.對(duì)n個(gè)元素進(jìn)行快速排序時(shí)，最壞情況下的時(shí)間複雜度為()。A．O(1og2n)

B．O(n)

C．O(nlog2n)

D．O(n2)練習(xí)練習(xí)9.根據(jù)Hanoi問(wèn)題的分治解決演算法，將下列程式補(bǔ)充完整。#include<iostream.h>(1);voidmain(){intm;cout<<"ThisApplicationistoHanoiproblem"<<endl;cout<<"Inputthenumberofplates"<<endl;

(2);cout<<"Thestepofmovingis:"<<endl;hanoi(m,'A','B','C');}練習(xí)voidhanoi(intn,charone,chartwo,charthree){if((3))cout<<"from"<<one<<"to"<<three;else{(4);cout<<"from"<<one<<"to"<<three;

(5);}}練習(xí)10.設(shè)A[0..n-1]是一個(gè)已經(jīng)排好序的數(shù)組。請(qǐng)改寫(xiě)二分查找演算法，使得當(dāng)查找元素x不在數(shù)組中時(shí)，返回小於x的最大元素位置i和大於x的最小元素位置j。當(dāng)查找元素在數(shù)組中時(shí)，i和j相同，均為x在數(shù)組中的位置。作業(yè)2-11，2-121.求整數(shù)5的劃分個(gè)數(shù)2.A={12，2，16，30，8，28，4，10，20，6}用分治法找出A中的最大和最小值。3.分別使用歸併排序和快速排序使下述序列昇冪有序A={12，2，16，30，8，28，4，10，20，6}。4.利用線性時(shí)間選擇演算法，求下列序列中的第8小元素。A={2,6,18,1,4,10,20,6,22,13,9,5,24,3,7,12,16,11,20,28,23,14,15,21,125,34,19}5.閱讀下麵C代碼，回答問(wèn)題1至3?！菊f(shuō)明】採(cǎi)用歸併排序?qū)個(gè)元素進(jìn)行遞增排序時(shí)，首先將n個(gè)元素的數(shù)組分成各含n/2個(gè)元素的子數(shù)組，然後用歸併排序?qū)蓚€(gè)子數(shù)組進(jìn)行遞歸排序，最後合併兩個(gè)已經(jīng)排好序的子數(shù)組得到排序結(jié)果。下麵的C代碼是對(duì)上述歸併演算法的實(shí)現(xiàn)，其中的常量和變數(shù)說(shuō)明如下：arr:待排序數(shù)組p,q,r：一個(gè)子數(shù)組的位置從p到q，另一個(gè)子數(shù)組的位置從q+1到r作業(yè)begin，end：待排序數(shù)組的起止位置left，right：臨時(shí)存放待合併的兩個(gè)子數(shù)組n1，n2：兩個(gè)子數(shù)組的長(zhǎng)度i,j,k：迴圈變數(shù)mid：臨時(shí)變數(shù)作業(yè)【C代碼】#include<stdio.h>#include<stdlib.h>#defineMAX655536voidmerge(intarr[],intp,intq,intr){int*left,*right;intn1,n2,I,j,k;n1=q-p+1;n2=r-q;作業(yè)for(i=0;i<n1;i++){left[i]=arr[p+i];}left[i]=MAX;for(i=0;i<n2;i++){right[i]=arr[q+i+1];}right[i]=MAX;作業(yè)i=0;j=0;for(k=p;(1);k++){if(left[i]>right[j]){(2);j++;}作業(yè)else{arr[k]=left[i];i++;}}}voidmergesort(intarr[],intbegin,intend){intmid;if((3)){作業(yè)mid=(begin+end)/2;mergesort(arr,begin,mid);(4);merge(arr,begin,mid,end);}}【問(wèn)題一】根據(jù)以上說(shuō)明和C代碼，填充1-4。作業(yè)144通過(guò)應(yīng)用範(fàn)例學(xué)習(xí)動(dòng)態(tài)規(guī)劃演算法設(shè)計(jì)策略（1）斐波那契數(shù)列；（2）0-1背包問(wèn)題；（3）矩陣連乘問(wèn)題；（4）最長(zhǎng)公共子序列；（5）最優(yōu)二分檢索樹(shù)；（6）裝配線調(diào)度問(wèn)題；（7）凸多邊形最優(yōu)三角剖分；（8）最大子段和問(wèn)題。145動(dòng)態(tài)規(guī)劃（DynamicProgramming）1957年，RichardBellman創(chuàng)造了這個(gè)名字該方法利用表格技術(shù)，用多項(xiàng)式複雜度代替指數(shù)複雜度。典型應(yīng)用是組合優(yōu)化問(wèn)題，求解最優(yōu)值和最優(yōu)解。146動(dòng)態(tài)規(guī)劃演算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題演算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=147但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重複計(jì)算了許多次。演算法總體思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)148如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重複計(jì)算，從而得到多項(xiàng)式時(shí)間演算法。演算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)149學(xué)習(xí)內(nèi)容3.1用表代替遞歸3.2

0-1背包問(wèn)題3.3矩陣鏈乘問(wèn)題3.4動(dòng)態(tài)規(guī)劃演算法的基本要素3.5