算法引論概要PPT課件

-,1,算法設計與分析（ACM/ICPC程序設計方法論）,廣東江門五邑大學信息學院高宏賓,2007年8月,-,2,主要內容介紹,第1章算法引論第2章遞歸與分治策略第3章動態(tài)規(guī)劃第4章貪心算法第5章回溯法第6章分支限界法第7章概率算法第8章NP完全性理論第9章近似算法第10章算法優(yōu)化策略,-,3,第1章算法引論,1.1算法與程序算法設計實例例1.按遞增次序生成M的最小的n個元素，M定義為：1MxM，則y=2x+1My=3x+1M,本章主要知識點,1.1算法與程序1.2表達算法的抽象機制1.3描述算法1.4算法復雜性分析,-,4,0123456789p2p3i,134713,if(2*mp2=3*mp3)mi=2*mp2+1;p2+;p3+;elseif(2*mp2eps)e+=t;/*加當前項*/i+=1;n*=i;/*計算i的階乘*/t=1/n;/*計算下一項*/printf(e=%fn,e);,例2.計算e的值,-,6,例3.螺旋方陣的生成,10,13,11,12,25,21,20,19,18,17,16,15,14,9,8,7,6,5,4,3,2,1,24,23,22,#defineM64main()inti,j,num,n,aMM;num=1;scanf(%d,-,7,例4.方陣的旋轉,10,13,11,12,25,21,20,19,18,17,16,15,14,9,8,7,6,5,4,3,2,1,24,23,22,aijjijn-i+1an-i+1j,temp,for(j=i;jn-i+1;j+)temp=aij;aij=ajn-i-1;ajn-i-1=an-i-1n-j-1;an-i-1n-j-1=an-j-1i;an-j-1i=temp;,-,8,#include#defineM64main()inti,j,temp,n,aMM;scanf(%d,for(i=0;in;i+)for(j=0;jn;j+)printf(%d,aij);printf(n);,-,9,例5.幻方陣的生成,13,6,4,16,14,7,5,23,15,17,24,8,2,1,19,12,10,22,20,25,18,9,11,3,21,#defineM64main()inti,j,n,aMM;scanf(%d,for(i=0;in;i+)for(j=0;jn;j+)printf(%5d,aij);printf(n);,-,10,2.算法設計方法與實踐,遞歸方法分治方法動態(tài)規(guī)劃方法貪心方法回溯方法分支限界方法概率方法NP完全性近似方法算法優(yōu)化方法,-,11,3.算法的概念,算法是為解決某個特定問題而設計的由一些命令組成的序列，該序列具備5大特征：1.有窮性算法中命令的個數(shù)是有限的；每個命令的執(zhí)行時間是有限的。2.確定性算法中每個命令的含義是確切的。3.有效性算法中每個命令是可行的。4.輸入算法需要從外界接受數(shù)據(jù),且個數(shù)0。5.輸出算法必須產生一組數(shù)據(jù)作為其結果，且個數(shù)0。,-,12,4.簡單算法舉例,例6.計算12345的值。推廣：計算i(i=1,n)的值。分析：為了計算12(i-1)i(i+1)n，我們不妨設p=12i并稱p為部分積。此時，對于當前的i,若做操作i+1i,然后對部分積p做操作pip，則p的值順增一個因子。因此，反復進行i+1i；pip；可使p逐漸接近計算目標。再考慮p，i的初始狀態(tài)以及能夠進行上述操作的條件，可以設計出如右所示算法：,S0:輸入n；S1:1p;S2:0i;S3:i+1i;S4:pip;S5:ifinthengotoS3;elseoutputp;要點:部分積的概念及其表示;循環(huán)變量及其增量的確定;進入循環(huán)的初始值的確定;退出循環(huán)的條件。,-,13,類比：計算i(i=1,n)的值S0:輸入n；S1:0s;S2:0i;S3:i+1i;S4:s+is;S5:ifinthengotoS3;elseoutputs;,要點:部分和的概念及其表示;循環(huán)變量及其增量的確定;進入循環(huán)的初始值的確定;退出循環(huán)的條件。,-,14,例7.判斷20002500年中的每一年是否是閏年?此問題的算法設計思路:假設year是年份,則:S1:year=2000;S2:如果year是閏年則輸出year“是閏年”;否則輸出year“不是閏年”;S3:year=year+1;S4:如果year=2500則轉向S2;否則終止該算法;,要點:逐步求精_逐步細化。,-,15,例8.計算(-1)/i(a=i+1,i=1,n)的值問題的性質:部分和問題,S0:輸入n；S1:1sign;S2:1sum;S3:2deno;S4:(-1)signsign;產生當前項符號S5:sign(1/deno)term;生成當前項S6:sum+termsum;累加當前項S7:deno+1deno;產生下一項的分母S8:ifdeno=n要點:當前項正負號的轉換thengotoS4;elseoutputsum;,-,16,1.2表達算法的抽象機制,1.從機器語言到高級語言的抽象,高級程序設計語言的主要好處是：,（4）把繁雜瑣碎的事務交給編譯程序，所以自動化程度高，開發(fā)周期短，程序員可以集中時間和精力從事更重要的創(chuàng)造性勞動，提高程序質量。,（1）高級語言更接近算法語言，易學、易掌握，一般工程技術人員只需要幾周時間的培訓就可以勝任程序員的工作；,（2）高級語言為程序員提供了結構化程序設計的環(huán)境和工具，使得設計出來的程序可讀性好，可維護性強，可靠性高；,（3）高級語言不依賴于機器語言，與具體的計算機硬件關系不大，因而所寫出來的程序可植性好、重用率高；,-,17,2.抽象數(shù)據(jù)類型,抽象數(shù)據(jù)類型是算法的一個數(shù)據(jù)模型連同定義在該模型上并作為算法構件的一組運算。,抽象數(shù)據(jù)類型帶給算法設計的好處有：,（1）算法頂層設計與底層實現(xiàn)分離；（2）算法設計與數(shù)據(jù)結構設計隔開，允許數(shù)據(jù)結構自由選擇；（3）數(shù)據(jù)模型和該模型上的運算統(tǒng)一在ADT中，便于空間和時間耗費的折衷；（4）用抽象數(shù)據(jù)類型表述的算法具有很好的可維護性；（5）算法自然呈現(xiàn)模塊化；（6）為自頂向下逐步求精和模塊化提供有效途徑和工具；（7）算法結構清晰，層次分明，便于算法正確性的證明和復雜性的分析。,-,18,1.3算法的描述,1.自然語言描述問題：二義性問題。例：1.張先生對李先生講他的兒子考上了大學。2.下雨天留客天留我不留2.流程圖描述結論：用三種控制結構可以描述一切可計算的問題。3.改進的流程圖描述原則：單一出入口原則。4.N-S流程圖描述,S1,S2,S1,S2,S,con,con,S1S2,yconnS1S2,WhileconS,Suntilcon,S,con,-,19,5.偽代碼描述6.程序設計語言描述產生用程序設計語言描述的算法程序是程序設計的最終目標。,-,20,1.4算法復雜性分析,算法復雜性是算法運行所需要的計算機資源的量，需要時間資源的量稱為時間復雜性，需要空間資源的量稱為空間復雜性。這個量應該是只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用C表示復雜性，那么，應該有C=F(N,I,A)。一般把時間復雜性和空間復雜性分開，并分別用T和S來表示，則有：T=T(N,I)和S=S(N,I)。（通常，讓A隱含在復雜性函數(shù)名當中）,-,21,最壞情況下的時間復雜性：,最好情況下的時間復雜性：,平均情況下的時間復雜性：,其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N,I*)達到Tmax(N)的合法輸入；是中使T(N,)達到Tmin(N)的合法輸入；而P(I)是在算法的應用中出現(xiàn)輸入I的概率。,-,22,算法復雜性在漸近意義下的階：,漸近意義下的記號：O、o設f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。,O的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當NN0時有f(N)Cg(N)，則稱函數(shù)f(N)當N充分大時上有界，且g(N)是它的一個上界，記為f(N)=O(g(N)。即f(N)的階不高于g(N)的階。,根據(jù)O的定義，容易證明它有如下運算規(guī)則：(1)O(f)+O(g)=O(max(f,g)；(2)O(f)+O(g)=O(f+g)；(3)O(f)O(g)=O(fg)；(4)如果g(N)=O(f(N)，則O(f)+O(g)=O(f)；(5)O(Cf(N)=O(f(N)，其中C是一個正的常數(shù)；(6)f=O(f)。,-,23,的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當NN0時有f(N)Cg(N)，則稱函數(shù)f(N)當N充分大時下有界，且g(N)是它的一個下界，記為f(N)=(g