算法引論概要PPT課件

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