基本的算法策略ppt課件

1、第四章 根本的算法戰(zhàn)略4.1 迭代算法概念 用變量的舊值遞推出新值的處理問(wèn)題的方法適宜的范圍 數(shù)值計(jì)算類(lèi)型1遞推法 sn=sn-1+An2倒推法411 遞推法 【例1】兔子繁衍問(wèn)題問(wèn)題描畫(huà)：一對(duì)兔子從出生后第三個(gè)月開(kāi)場(chǎng)，每月生一對(duì)小兔子。小兔子到第三個(gè)月又開(kāi)場(chǎng)生下一代小兔子。假假設(shè)兔子只生不死，一月份抱來(lái)一對(duì)剛出生的小兔子，問(wèn)一年中每個(gè)月各有多少只兔子。問(wèn)題分析：那么繁衍過(guò)程如下： 一月 二月 三月 四月 五月 六月 1 1 1+1=2 2+1=3 3+2=5 5+3=8 數(shù)學(xué)建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，。算法1： main( ) int i,a=1,b=1

2、; print(a,b); for(i=1;i=10;i+) c=a+b; print (c); a=b; b=c； 4.1.2 倒推法 所謂倒推法：是對(duì)某些特殊問(wèn)題所采用的違反通常習(xí)慣的，從 后向前推解問(wèn)題的方法。【例】猴子吃桃問(wèn)題一只小猴子摘了假設(shè)干桃子，每天吃現(xiàn)有桃的一半多一個(gè)，到第10天時(shí)就只需一個(gè)桃子了，求原有多少個(gè)桃？數(shù)學(xué)模型：每天的桃子數(shù)為：a10=1, a9=1+a10*2, a8=1+a9*2,a10=1， 遞推公式為：ai=1+ai+1*2 I = 9,8,7,61算法如下 ： main( ) int i,s; s=1; for (i=9 ;i=1;i=i-1) s=(s+

3、1*2 print (s)； 4.2 蠻力法 蠻力法是基于計(jì)算機(jī)運(yùn)算速度快這一特性，在處理問(wèn)題時(shí)采取的一種“懶惰的戰(zhàn)略。這種戰(zhàn)略不經(jīng)過(guò)或者說(shuō)是經(jīng)過(guò)很少的思索，把問(wèn)題的一切情況或一切過(guò)程交給計(jì)算機(jī)去一一嘗試，從中找出問(wèn)題的解。 運(yùn)用 蠻力戰(zhàn)略的運(yùn)用很廣，詳細(xì)表現(xiàn)方式各異，數(shù)據(jù)構(gòu)造課程中學(xué)習(xí)的：選擇排序、冒泡排序、插入排序、順序查找、樸素的字符串匹配等，都是蠻力戰(zhàn)略詳細(xì)運(yùn)用。421 枚舉法 枚舉 enumerate法窮舉法是蠻力戰(zhàn)略的一種表現(xiàn)方式，也是一種運(yùn)用非常普遍的思想方法。它是根據(jù)問(wèn)題中的條件將能夠的情況一一列舉出來(lái)，逐一嘗試從中找出滿(mǎn)足問(wèn)題條件的解。但有時(shí)一一列舉出的情況數(shù)目很大，假設(shè)超越

4、了我們所能忍受的范圍，那么需求進(jìn)一步思索，排除一些明顯不合理的情況，盡能夠減少問(wèn)題能夠解的列舉數(shù)目。用枚舉法處理問(wèn)題，通?？梢詮膬蓚€(gè)方面進(jìn)展算法設(shè)計(jì)： 1找出枚舉范圍：分析問(wèn)題所涉及的各種情況。 2找出約束條件：分析問(wèn)題的解需求滿(mǎn)足的條件，并用邏輯表達(dá)式表示。【例】解數(shù)字迷： A B C A B A D D D D D D算法設(shè)計(jì)1：按乘法枚舉1)枚舉范圍為： A：39A=1，2時(shí)積不會(huì)得到六位數(shù),B：09, C：09 六位數(shù)表示為A*10000+B*1000+C*100+A*10+B， 共嘗試800次。2)約束條件為： 每次嘗試，先求5位數(shù)與A的積，再測(cè)試積的各位能否相 同，假設(shè)一樣那么找到

5、了問(wèn)題的解。 測(cè)試積的各位能否一樣比較簡(jiǎn)單的方法是，從低位開(kāi)場(chǎng)， 每次都取數(shù)據(jù)的個(gè)位，然后整除10，使高位的數(shù)字不斷變 成個(gè)位，并逐一比較。 算法1如下：main int A,B,C,D,E,E1,F,G1,G2,i; for(A=3; A=9; A+) for(B=0; B=9; B+) for(C=0; C=9; C+) F=A*10000+B*1000+C*100+A*10+B; E=F*A； E1=E; G1=E1 mod 10; for(i=1; i=5; i+) G2=G1; E1=E1/10; G1= E1 mod 10; if(G1G2 ) break; if(i=6) pri

6、nt( F，*，A，=，E); 4.3 分而治之算法431 分治算法框架 1算法設(shè)計(jì)思想分治法求解問(wèn)題的過(guò)程是，將整個(gè)問(wèn)題分解成假設(shè)干個(gè)小問(wèn)題后分而治之。假設(shè)分解得到的子問(wèn)題相對(duì)來(lái)說(shuō)還太大，那么可反復(fù)運(yùn)用分治戰(zhàn)略將這些子問(wèn)題分成更小的同類(lèi)型子問(wèn)題，直至產(chǎn)生出方便求解的子問(wèn)題，必要時(shí)逐漸合并這些子問(wèn)題的解，從而得到問(wèn)題的解。分治法的根本步驟在每一層遞歸上都有三個(gè)步驟： 1分解：將原問(wèn)題分解為假設(shè)干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題方式一樣的子問(wèn)題； 2處理：假設(shè)子問(wèn)題規(guī)模較小而容易被處理那么直接解，否那么再繼續(xù)分解為更小的子問(wèn)題，直到容易處理； 3合并：將已求解的各個(gè)子問(wèn)題的解，逐漸合并為原問(wèn)題的解

7、。闡明： 有時(shí)問(wèn)題分解后，不用求解一切的子問(wèn)題，也就不用作第三步的操作。比如折半查找，在判別出問(wèn)題的解在某一個(gè)子問(wèn)題中后，其它的子問(wèn)題就不用求解了，問(wèn)題的解就是最后最小的子問(wèn)題的解。分治法的這類(lèi)運(yùn)用，又稱(chēng)為“減治法。 多數(shù)問(wèn)題需求一切子問(wèn)題的解，并由子問(wèn)題的解，運(yùn)用恰當(dāng)?shù)姆椒ê喜⒊蔀檎麄€(gè)問(wèn)題的解，比如合并排序，就是不斷將子問(wèn)題中已排好序的解合并成較大規(guī)模的有序子集。 2適宜用分治法戰(zhàn)略的問(wèn)題當(dāng)求解一個(gè)輸入規(guī)模為n且取值又相當(dāng)大的問(wèn)題時(shí)，用蠻力戰(zhàn)略效率普通得不到保證。假設(shè)問(wèn)題能滿(mǎn)足以下幾個(gè)條件，就能用分治法來(lái)提高處理問(wèn)題的效率。1 能將這n個(gè)數(shù)據(jù)分解成k個(gè)不同子集合，且得到k個(gè)子集合是可以獨(dú)立求

8、解的子問(wèn)題，其中1kn；2 分解所得到的子問(wèn)題與原問(wèn)題具有類(lèi)似的構(gòu)造，便于利用遞歸或循環(huán)機(jī)制；在求出這些子問(wèn)題的解之后，就可以推解出原問(wèn)題的解； 432 二分法 不同于現(xiàn)實(shí)中對(duì)問(wèn)題或任務(wù)的分解，能夠會(huì)思索問(wèn)題或任務(wù)的重點(diǎn)、難點(diǎn)、承當(dāng)人員的才干等來(lái)進(jìn)展問(wèn)題的分解和分配。在算法設(shè)計(jì)中每次一個(gè)問(wèn)題分解成的子問(wèn)題個(gè)數(shù)普通是固定的，每個(gè)子問(wèn)題的規(guī)模也是平均分配的。當(dāng)每次都將問(wèn)題分解為原問(wèn)題規(guī)模的一半時(shí)，稱(chēng)為二分法。二分法是分治法較常用的分解戰(zhàn)略，數(shù)據(jù)構(gòu)造課程中的折半查找、歸并排序等算法都是采用此戰(zhàn)略實(shí)現(xiàn)的。分治法的普通的算法設(shè)計(jì)方式如下：Divide-and-Conquer(int n) /n為問(wèn)題規(guī)模

9、/ if nn0 /n0 為可解子問(wèn)題的規(guī)模/ 解子問(wèn)題； return(子問(wèn)題的解)；for i=1 ;i=k;i+ /分解為較小子問(wèn)題p1,p2,pk/ yi=Divide-and-Conquer(|Pi|); /遞歸處理Pi/ T =MERGE(y1,y2,.,yk); /合并子問(wèn)題/ return(T); 【例1】金塊問(wèn)題： 老板有一袋金塊(共n塊)，最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺(tái)比較分量的儀器，我們希望用最少的比較次數(shù)找出最重的金塊。算法設(shè)計(jì)1：比較簡(jiǎn)單的方法是逐個(gè)的進(jìn)展比較查找。先拿兩塊比較分量，留下重的一個(gè)與下一塊比較，直到全部比較終了，

10、就找到了最重的金子。算法類(lèi)似于一趟選擇排序， 算法如下：maxmin( float a,int n) max=min=a1; for(i=2; i=n ;i+ ) if(max ai) min=ai; 算法分析1：算法中需求n-1次比較得到max。最好的情況是金塊是由小到大取出的，不需求進(jìn)展與min的比較，共進(jìn)展n-1次比較。最壞的情況是金塊是由大到小取出的，需求再經(jīng)過(guò)n-1次比較得到min算法設(shè)計(jì)2:在含nn是2的冪n=2個(gè)元素的集合中尋覓極大元和極小元。用分治法二分法：1 將數(shù)據(jù)等分為兩組兩組數(shù)據(jù)能夠差1，2遞歸分解直到每組元素的個(gè)數(shù)2，可簡(jiǎn)單地找到最大小值。3回溯時(shí)將分解的兩組解大者取大

11、，小者取小，合并為當(dāng)前問(wèn)題的解。算法2 遞歸求取最大和最小元素 float an;maxmin int i, int j ,float &fmax, float &fminint mid; float lmax, lmin, rmax, rmin;if (i=j) fmax= ai; fmin=ai;else if (i=j-1) if(airmax) fmax=lmax;else fmax=rmax;if(lminrmin) fmin=rmin;else fmin=lmin; 【例】大整數(shù)乘法在某些情況下，我們需求處置很大的整數(shù)，它無(wú)法在計(jì)算機(jī)硬件能直接允許的范圍內(nèi)進(jìn)展表示和處置。假設(shè)用浮點(diǎn)

12、數(shù)來(lái)存儲(chǔ)它，只能近似地參與計(jì)算，計(jì)算結(jié)果的有效數(shù)字會(huì)遭到限制。假設(shè)要準(zhǔn)確地表示大整數(shù)，并在計(jì)算結(jié)果中要求準(zhǔn)確地得到一切位數(shù)上的數(shù)字，就必需用軟件的方法來(lái)實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算。請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)展兩個(gè)n位大整數(shù)的乘法運(yùn)算。算法設(shè)計(jì)：設(shè)X和Y都是n位的二進(jìn)制整數(shù)，如今要計(jì)算它們的乘積X*Y。圖4-10 大整數(shù)X和Y的分段按照乘法分配律，分解后的計(jì)算過(guò)程如下：記：X=A*2n/2+B ，Y=C*2n/2+D。這樣，X和Y的乘積為：X*Y=(A*2n/2+B)(C*2n/2+D)=A*C*2n+(AD+CB)*2n/2+B*D(1) T1=1 Tn=4T(n/2) 2 由此遞歸式迭代過(guò)程如下

13、：T(n)=4T(n/2) =4(4T(n/4)T(n/4) =16*T(n/8) = =O4k= O(nlog4) =On2所以可得算法的時(shí)間復(fù)雜度為T(mén)(n)=O(n2)。模型改良：可以把X*Y寫(xiě)成另一種方式：X*Y=A*C*2n+(A-B)(D-C)+AC+BD*2n/2+B*D (3)式(3)看起來(lái)比式(1)復(fù)雜，但它僅需做3次n/2位整數(shù)的乘法：AC，BD和(A-B)(D-C)，6次加、減法和2次移位。由此可得: (4)用解遞歸方程的迭代公式法，無(wú)妨設(shè)n=2k： T(n)=3T(n/2) =3(3T(n/4) =9(T(n/8) = =3k +3k-1 *2c+3k-2 *4c+3c2k-1+c2k = O(nlog3)那么得到T(n)=O(nlog3)=O(n1.59)。434 其它分治方法 【例】選擇問(wèn)題： 對(duì)于給定的n 個(gè)元素的數(shù)組a0:n-1，要求從中找出第k小的元