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

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

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

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

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

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

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

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

對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。23周口師范學(xué)院計算機科學(xué)系算法總體思想對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jì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ī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。24周口師范學(xué)院計算機科學(xué)系算法總體思想將求出的小規(guī)模的問題的解合并為一個更大規(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)25周口師范學(xué)院計算機科學(xué)系算法總體思想將求出的小規(guī)模的問題的解合并為一個更大規(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)

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

26周口師范學(xué)院計算機科學(xué)系1.4.1遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。下面來看幾個實例。27周口師范學(xué)院計算機科學(xué)系1.4.1遞歸的概念例1階乘函數(shù)

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

fibonacci(intn){

if(n<=1)return1;

return

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

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é)院計算機科學(xué)系遞歸小結(jié)優(yōu)點：結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。34周口師范學(xué)院計算機科學(xué)系求最大公約數(shù)例子Example1

35周口師范學(xué)院計算機科學(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é)院計算機科學(xué)系1.5遞歸和消去遞歸遞歸直接調(diào)用自己或間接通過一些語句調(diào)用自己優(yōu)點：描述某些數(shù)學(xué)問題非常自然，證明算法很容易。缺點：執(zhí)行時間、空間消耗多一個遞歸問題可分為“回推”和“遞推”兩個階段未知已知遞推回推37周口師范學(xué)院計算機科學(xué)系用遞歸實現(xiàn)求最大公因數(shù)ProcedureGCD(a,b)ifb=0thenreturn(a)elsereturn(GCD(b,amodb))

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

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