第1章算法求解基礎(chǔ)課件

計(jì)算機(jī)算法分析與設(shè)計(jì)

任課教師：周文剛周口師范學(xué)院計(jì)算機(jī)科學(xué)系1周口師范學(xué)院計(jì)算機(jī)科學(xué)系學(xué)習(xí)目標(biāo)掌握算法分析與設(shè)計(jì)的基本理論掌握進(jìn)行算法分析與設(shè)計(jì)的基本方法（時(shí)間、空間復(fù)雜度分析，算法正確性的證明）掌握計(jì)算機(jī)領(lǐng)域中常用的非數(shù)值計(jì)算方法，并學(xué)會(huì)用這些算法解決實(shí)際問(wèn)題2周口師范學(xué)院計(jì)算機(jī)科學(xué)系課程要求教學(xué)方式：理論(72學(xué)時(shí))考核方式：考試(70%)+實(shí)驗(yàn)作業(yè)(30%)先修課程：《數(shù)據(jù)結(jié)構(gòu)》《C語(yǔ)言程序設(shè)計(jì)》3周口師范學(xué)院計(jì)算機(jī)科學(xué)系授課教材選用教材：《算法設(shè)計(jì)與分析》

陳慧南電子工業(yè)出版社參考書(shū)目：《算法引論》張益新，沈雁國(guó)防科技大學(xué)出版社《計(jì)算機(jī)算法設(shè)計(jì)與分析》王曉東電子工業(yè)出版社4周口師范學(xué)院計(jì)算機(jī)科學(xué)系第一章導(dǎo)引

---計(jì)算機(jī)算法分析與設(shè)計(jì)是面向設(shè)計(jì)的、處于核心地位的教育課程

---計(jì)算機(jī)算法是計(jì)算機(jī)科學(xué)和計(jì)算機(jī)應(yīng)用的核心。1.什么是算法？2.如何分析算法？3.如何表示算法？4.基本數(shù)據(jù)結(jié)構(gòu)5周口師范學(xué)院計(jì)算機(jī)科學(xué)系1.什么是算法算法數(shù)值計(jì)算方法（求解數(shù)值問(wèn)題，插值計(jì)算、數(shù)值積分等）非數(shù)值計(jì)算方法（求解非數(shù)值問(wèn)題，主要進(jìn)行判斷比較）算法籠統(tǒng)的定義：求解確定一類問(wèn)題的任意一種特殊方法。非形式描述：算法就是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算。6周口師范學(xué)院計(jì)算機(jī)科學(xué)系算法(Algorithm)算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。算法是若干指令的有窮序列，滿足性質(zhì)：(1)輸入：有外部提供的量作為算法的輸入。(2)輸出：算法產(chǎn)生至少一個(gè)量作為輸出。(3)確定性：組成算法的每條指令是清晰，無(wú)歧義的。(4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。7周口師范學(xué)院計(jì)算機(jī)科學(xué)系程序(Program)程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)(4)。例如操作系統(tǒng)，是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問(wèn)題，每一個(gè)問(wèn)題由操作系統(tǒng)中的一個(gè)子程序通過(guò)特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。8周口師范學(xué)院計(jì)算機(jī)科學(xué)系問(wèn)題求解(ProblemSolving)證明正確性分析算法設(shè)計(jì)程序理解問(wèn)題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法9周口師范學(xué)院計(jì)算機(jī)科學(xué)系算法復(fù)雜性分析

算法復(fù)雜性=算法所需要的計(jì)算機(jī)資源算法的時(shí)間復(fù)雜性T(n)；算法的空間復(fù)雜性S(n)。其中n是問(wèn)題的規(guī)模（輸入大小）。10周口師范學(xué)院計(jì)算機(jī)科學(xué)系描述算法的方法自然語(yǔ)言偽代碼流程圖程序特別注意算法描述≠程序特別在科技論文寫(xiě)作時(shí)，一般不能寫(xiě)原程序，而應(yīng)通過(guò)偽代碼或流程圖描述11周口師范學(xué)院計(jì)算機(jī)科學(xué)系例1求兩個(gè)正整數(shù)m,n的最大公因子算法1-1歐幾里得算法輸入：正整數(shù)m和n輸出：m和n的最大公因子第一步：求余數(shù)。rm%n第二步：判斷r=0?，若是，終止(n為答案)，否則，轉(zhuǎn)第三步。第三步：互換,mn,nr,返回第一步。BeginRm%nr=0？Swap(m.n)EndNY12周口師范學(xué)院計(jì)算機(jī)科學(xué)系例1求兩個(gè)正整數(shù)最大公因子的一個(gè)實(shí)例假設(shè)m=21和n=45，求21和45的最大公因子第一步：r=m%n=21%45=21；第二步：r不等于0，轉(zhuǎn)入第三步；第三步：互換，m=n=45,n=r=21，返回第一步。第一步：r=m%n=45%21=3；第二步：r不等于0，轉(zhuǎn)入第三步；第三步：互換，m=n=21,n=r=3，返回第一步。第一步：r=m%n=21%3=0；第二步：r等于0，算法結(jié)束，3即為21和45的最大公因子。13周口師范學(xué)院計(jì)算機(jī)科學(xué)系算法的五個(gè)重要特性確定性每一種運(yùn)算必須要有確切的定義，無(wú)二義性可行性運(yùn)算都是基本運(yùn)算，原理上能在有限時(shí)間內(nèi)完成輸入有 1個(gè)或多個(gè)輸入輸出一個(gè)或多個(gè)輸出有窮性在執(zhí)行了有窮步運(yùn)算后終止14周口師范學(xué)院計(jì)算機(jī)科學(xué)系算法的特性凡是算法，都必須滿足以上五條特性。只滿足前四條特性的一組規(guī)則不能稱之為算法，只能叫做計(jì)算過(guò)程。操作系統(tǒng)就是計(jì)算過(guò)程的一個(gè)典型例子。設(shè)計(jì)操作系統(tǒng)的目的是為了控制作業(yè)的運(yùn)行，當(dāng)沒(méi)有作業(yè)時(shí)，這一計(jì)算過(guò)程并不終止，而是處于等待狀態(tài)，一直等到一個(gè)新的作業(yè)的進(jìn)入。15周口師范學(xué)院計(jì)算機(jī)科學(xué)系算法學(xué)習(xí)的五個(gè)內(nèi)容如何設(shè)計(jì)算法運(yùn)用一些基本設(shè)計(jì)策略規(guī)劃算法如何表示算法用恰當(dāng)?shù)姆绞奖硎舅惴ㄈ绾未_認(rèn)算法算法正確性的證明(算法確認(rèn)algorithmvalidation)如何分析算法通過(guò)時(shí)間和空間復(fù)雜度的分析，確定算法的優(yōu)劣如何測(cè)試程序測(cè)試程序是否會(huì)產(chǎn)生錯(cuò)誤的結(jié)果16周口師范學(xué)院計(jì)算機(jī)科學(xué)系1.1.2為什么學(xué)習(xí)算法只有具有良好的算法基礎(chǔ)才能成為訓(xùn)練有素的軟件人才能讓人更聰明，掌握更多的解決問(wèn)題的方法17周口師范學(xué)院計(jì)算機(jī)科學(xué)系1.2問(wèn)題求解方法算法是問(wèn)題的程序化解決方案1、問(wèn)題和問(wèn)題求解2、問(wèn)題求解過(guò)程理解問(wèn)題設(shè)計(jì)方案編程實(shí)現(xiàn)復(fù)查18周口師范學(xué)院計(jì)算機(jī)科學(xué)系3、系統(tǒng)生命周期分析設(shè)計(jì)編碼測(cè)試維護(hù)19周口師范學(xué)院計(jì)算機(jī)科學(xué)系1.3算法設(shè)計(jì)與分析1、問(wèn)題求解過(guò)程精確算法啟發(fā)式算法（近似算法）－－簡(jiǎn)化和智能猜測(cè)可行解最優(yōu)解啟發(fā)式算法并不總能導(dǎo)致理想解，但常常能在合理的時(shí)間內(nèi)求得令人滿意的結(jié)果20周口師范學(xué)院計(jì)算機(jī)科學(xué)系4、如何確認(rèn)算法數(shù)學(xué)歸納法證明或?qū)嵗?yàn)證21周口師范學(xué)院計(jì)算機(jī)科學(xué)系1.4遞歸和歸納1、遞歸直接或間接引用自己的定義方法包括基礎(chǔ)情況和遞歸部分longFib(longn){

if(n<=1)returnn;elsereturnFib(n-2)+Fib(n-1);}22周口師范學(xué)院計(jì)算機(jī)科學(xué)系將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=

對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。23周口師范學(xué)院計(jì)算機(jī)科學(xué)系算法總體思想對(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)

將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。24周口師范學(xué)院計(jì)算機(jī)科學(xué)系算法總體思想將求出的小規(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)25周口師范學(xué)院計(jì)算機(jī)科學(xué)系算法總體思想將求出的小規(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è)擊破，分而治之。

26周口師范學(xué)院計(jì)算機(jī)科學(xué)系1.4.1遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(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í)例。27周口師范學(xué)院計(jì)算機(jī)科學(xué)系1.4.1遞歸的概念例1階乘函數(shù)

階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。28周口師范學(xué)院計(jì)算機(jī)科學(xué)系1.4.1遞歸的概念例2Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：int

fibonacci(intn){

if(n<=1)return1;

return

fibonacci(n-1)+fibonacci(n-2);}29周口師范學(xué)院計(jì)算機(jī)科學(xué)系2.1遞歸的概念例3Ackerman函數(shù)當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：30周口師范學(xué)院計(jì)算機(jī)科學(xué)系Hanoi塔問(wèn)題設(shè)a,b,c是3個(gè)塔座。開(kāi)始時(shí)，在塔座a上有一疊共n個(gè)圓盤(pán)，這些圓盤(pán)自下而上，由大到小地疊在一起。各圓盤(pán)從小到大編號(hào)為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤(pán)移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤(pán)；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤(pán)移至a,b,c中任一塔座上。31周口師范學(xué)院計(jì)算機(jī)科學(xué)系hanio(n,A,B,C)盤(pán)子數(shù)，原在桿，目標(biāo)桿，借助桿32周口師范學(xué)院計(jì)算機(jī)科學(xué)系在問(wèn)題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來(lái)解決這個(gè)問(wèn)題。當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單。此時(shí)，只要將編號(hào)為1的圓盤(pán)從塔座a直接移至塔座b上即可。當(dāng)n＞1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)較小的圓盤(pán)依照移動(dòng)規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤(pán)從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤(pán)依照移動(dòng)規(guī)則從塔座c移至塔座b。由此可見(jiàn)，n個(gè)圓盤(pán)的移動(dòng)問(wèn)題可分為2次n-1個(gè)圓盤(pán)的移動(dòng)問(wèn)題，這又可以遞歸地用上述方法來(lái)做。由此可以設(shè)計(jì)出解Hanoi塔問(wèn)題的遞歸算法如下。Hanoi塔問(wèn)題例6Hanoi塔問(wèn)題

voidhanoi(intn,inta,intb,intc){

if(n>0){

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);}}33周口師范學(xué)院計(jì)算機(jī)科學(xué)系遞歸小結(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í)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。34周口師范學(xué)院計(jì)算機(jī)科學(xué)系求最大公約數(shù)例子Example1

35周口師范學(xué)院計(jì)算機(jī)科學(xué)系遞歸例子：Fibonacci數(shù)列定義F(n)=1, n=01, n=1F(n-1)+F(n-2), n>1非遞歸部分,終止條件遞歸部分,起始條件求Fibonacci數(shù)列算法ProcedureF(n) integern ifn≤1thenreturn(1) elsereturn(F(n-1)+F(n-2)) endifEndF36周口師范學(xué)院計(jì)算機(jī)科學(xué)系1.5遞歸和消去遞歸遞歸直接調(diào)用自己或間接通過(guò)一些語(yǔ)句調(diào)用自己優(yōu)點(diǎn)：描述某些數(shù)學(xué)問(wèn)題非常自然，證明算法很容易。缺點(diǎn)：執(zhí)行時(shí)間、空間消耗多一個(gè)遞歸問(wèn)題可分為“回推”和“遞推”兩個(gè)階段未知已知遞推回推37周口師范學(xué)院計(jì)算機(jī)科學(xué)系用遞歸實(shí)現(xiàn)求最大公因數(shù)ProcedureGCD(a,b)ifb=0thenreturn(a)elsereturn(GCD(b,amodb))

endifEndGCD例如：a=22,b=8求GCD(22,8)=？38周口師范學(xué)院計(jì)算機(jī)科學(xué)系GCD(22,8)GCD(8,6)GCD(6,2)GCD(2,0)2回推回推回推回推遞歸遞歸遞歸遞歸用遞歸實(shí)現(xiàn)求最大公因數(shù)結(jié)果為GCD(22,8)=239周口師范學(xué)院計(jì)算機(jī)科學(xué)系消去遞歸遞歸的優(yōu)點(diǎn)：與數(shù)學(xué)定義相似，容易編寫(xiě)算法遞歸的缺點(diǎn)：計(jì)算時(shí)間長(zhǎng)，很多值都被重復(fù)計(jì)算了多次消去遞歸目的是克服遞歸時(shí)間空間的開(kāi)銷解決方法：先使用遞歸，然后證明所設(shè)計(jì)的遞歸算法正確并且確信是一個(gè)好算法，再把遞歸消去，翻譯成與之等價(jià)的只使用迭代的算法。直接遞規(guī)翻譯成迭代過(guò)程的規(guī)則40周口師范學(xué)院計(jì)算機(jī)科學(xué)系小結(jié)算法就是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算。算法的五個(gè)重要特性確定性、可行性、輸入、輸出、有窮性算法分析是對(duì)一個(gè)算法需要多少時(shí)間和存儲(chǔ)空間作定量分析。遞歸和消去遞歸41周口師范學(xué)院計(jì)算機(jī)科學(xué)系作業(yè)

1－11－91－1442周口師范學(xué)院計(jì)算機(jī)科學(xué)系第2章算法分析基礎(chǔ)2.1算法復(fù)雜度好的算法應(yīng)該具備：正確簡(jiǎn)明高效最優(yōu)健壯43周口師范學(xué)院計(jì)算機(jī)科學(xué)系2.如何分析算法算法分析是對(duì)一個(gè)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量的分析。算法分析步驟：首先確定使用那些運(yùn)算以及執(zhí)行這些運(yùn)算所用的時(shí)間。(運(yùn)算包括基本數(shù)值運(yùn)算和一些更基本的任意長(zhǎng)序列的運(yùn)算)其次是要確定出能反映算法在各種情況下工作的數(shù)據(jù)集。（即要求我們編造出能產(chǎn)生最好、最壞和有代表性情況的數(shù)據(jù)配置，通過(guò)使用這些數(shù)據(jù)來(lái)運(yùn)行算法，以更了解算法的性能）44周口師范學(xué)院計(jì)算機(jī)科學(xué)系全面分析一個(gè)算法的兩個(gè)階段事前分析(apriorianalysis)求出該算法的一個(gè)時(shí)間限界函數(shù)(一些關(guān)于參數(shù)的函數(shù))事前分析只限于每條語(yǔ)句的頻率計(jì)數(shù)(frequencyc