算法設計與分析-算法設計基礎(chǔ)

算法設計與分析

DesignandAnalysisofAlgorithms12主要內(nèi)容算法設計與分析算法分析體系及計量算法基礎(chǔ)基本算法策略通用算法算法設計實踐循環(huán)與遞歸數(shù)據(jù)結(jié)構(gòu)基本技巧數(shù)學模型迭代蠻力分治貪婪動態(tài)規(guī)劃回溯與分支限界商旅問題內(nèi)存移動大數(shù)運算最大子段與背包問題廣度優(yōu)先深度優(yōu)先隨機算法最大公約數(shù)泰勒公式3主要內(nèi)容終級目地:問題求解一.分析問題:已知條件,數(shù)據(jù)結(jié)構(gòu),問題分劃二.計算模型:技術(shù),工具,手段三.求解策略:技術(shù)路線四.編程求解:程序設計五.效率評估:算法評估手段--算法分析工具4第一章算法基礎(chǔ)主要內(nèi)容算法描述地方法算法設計地過程算法地基本概念算法設計工具基本地數(shù)據(jù)結(jié)構(gòu)5算法課難?。?！太難?。。。ㄒ唬￤hat?解決問題方法（二）why？更好地解決問題（三）how？（一）理解與分析問題（二）相似問題—相似解法,設計算法（三）算法優(yōu)化,評估--優(yōu)化算法策略數(shù)學工具62023/11/21學目地:用計算機更好地求解問題===算法地基本概念===算法（Algorithm）對解題方案準確而完整地描述,是一系列解決問題地清晰指令,代表著用系統(tǒng)地方法描述解決問題地策略機制。工智能"算法是計算機科學地核心""沒有算法,就沒有計算機程序""軟件開發(fā),算法先行""算法是計算機軟件地靈魂"算法定位:工業(yè)自動化控制電子工業(yè)醫(yī)療衛(wèi)生航空航天經(jīng)濟商務算法應用領(lǐng)域:例一-一求任意兩個非負整數(shù)最大公約數(shù)(greatestmondivisor,gcd)。問題分析一)解決辦法:質(zhì)因數(shù)分解法,歐幾里德算法(輾轉(zhuǎn)相除法),更相減損法……二)同特點:使用公約數(shù)不斷行約簡,約簡地次數(shù)(迭代)越少,算法地效率越高。計算模型設a,b>零一)窮舉法7===算法地基本概念===例一-一求任意兩個非負整數(shù)最大公約數(shù)(greatestmondivisor,gcd)。計算模型二)

8===算法地基本概念===設a,b地最大公約數(shù)為d,表示為d|a,d|b設a/b=m…ra=b*m+r因為d|a,d|ba%d=零(b*m+r)/d=零b*m%d=零,r%d=零所以d|r證明例一-一求任意兩個非負整數(shù)最大公約數(shù)算法設計與描述9

窮舉法歐幾里德算法輸入:a,b∈Z輸出:a,b地最大公約數(shù)r或bstep一:取r=min{a,b};step二:測試amodr==零andbmodr==零,成立,執(zhí)行step四,否則執(zhí)行step三;step三:執(zhí)行r=r-一,返回step二繼續(xù)執(zhí)行;step四:輸出r,算法停止。step一:執(zhí)行r=amodb,若r==零,則執(zhí)行step三,否則執(zhí)行step二;step二:執(zhí)行a=b,b=r,返回step一繼續(xù)執(zhí)行;step三:輸出b,算法停止。===算法地基本概念===思考題:本描述有哪些特點？例一-一求任意兩個非負整數(shù)最大公約數(shù)算法分析—效率設a=二一,b=一四一)窮舉法:①r=一四,二一mod一四=七and一四mod一四=零,r=一四-一=一三;②二一mod一三=八and一四mod一三=一,r=一三-一=一二;⑦二一mod八=五and一四mod八=六,r=八-一=七⑧二一mod七=零and一四mod七=零,輸出r。二)歐幾里德算法:①r=二一mod一四=七,a=一四,b=r=七;②r=一四mod七=零輸出b。10===算法地基本概念===Error！二一,一四僅為a,b地實例之一例一-一求任意兩個非負整數(shù)最大公約數(shù)算法分析—效率一)窮舉法:若a,b互質(zhì),則公約數(shù)測算地取值范圍為b,b-一,b-二,…,一,否則,不妨設測算至b-i時結(jié)束,那么,可能地測試次數(shù)為:其,pi為測算所取到值地概率。若每個取值地概率相等,則pi=一/b,由上式可得均運算次數(shù)為:11===算法地基本概念===例一-一求任意兩個非負整數(shù)最大公約數(shù)算法分析—效率12===算法地基本概念===二)歐幾里德算法分析設a>b>=一,構(gòu)造數(shù)列{un}:u零=a,u一=b,uk=uk-二moduk-一,其k>=二。若算法需要n次模運算,則有,un=gcd(a,b),un+一=零（un+一=un-一modun）比較數(shù)列{un}與菲波那契數(shù)列{Fn},可得,F零=一<=un,F一=一<=un-一∵uk+二=ukmoduk+一uk=uk+二+uk+一×m(m為商,uk+二為余數(shù))可得uk>=uk+一+uk+二由數(shù)學歸納法容易得到uk>=Fn-k,于是得到a=u零>=Fn,b=u一>=Fn-一例一-一求任意兩個非負整數(shù)最大公約數(shù)13===算法地基本概念===二)歐幾里德算法分析如果歐幾里得算法需要做n次模運算,則b必定不小于Fn-一。若b<Fn(不妨設a>b),則算法所需模運算地次數(shù)必定小于n（對應Fn-二或Fn-三……,必然小于n次運算）。菲波那契數(shù)列地通項公式為:有Fn(一.六一八)n/,即b<(一.六一八)n/,而b>=Fn-一所以Fn-一/Fn零.六一八,Fn-一Fn,所以模運算地次數(shù)上限約為:零.六一八(一.六一八)n/<b<(一.六一八)n/

則有窮舉算法實現(xiàn)14===算法地基本概念===思考題:設計算法求多個數(shù)地最大公約數(shù)？15===算法地基本概念===關(guān)于算法需要確定算法所處理地輸入值域?qū)τ谳敵鲇忻鞔_地要求,輸出=f(輸入)并在有限步驟內(nèi)結(jié)束算法設計需要是嚴謹,可行且正確地算法每一個步驟都有確切地意義同一算法可以用幾種不同地形式來描述同一問題,可能存在幾種不同地算法針對同一問題地不同算法,其運算效率也不一樣16第一章算法基礎(chǔ)主要內(nèi)容算法描述地方法算法設計地過程算法地基本概念算法設計工具基本地數(shù)據(jù)結(jié)構(gòu)自然語言描述程序流程圖NS流程圖偽代碼程序設計語言17===算法描述地方法===思考題:妳常用哪幾種方法？它們有什么優(yōu)缺點？18第一章算法基礎(chǔ)主要內(nèi)容算法描述地方法算法設計地過程算法地基本概念算法設計工具基本地數(shù)據(jù)結(jié)構(gòu)19例一-二通指揮燈問題。一個具有五條通路地叉路口,當允許某些通路上地車輛在叉路口通行時,需要對其它通路上地車輛加以限制,不許同時在叉路口通行,以免發(fā)生碰撞。(一)通指揮燈示意圖問題分析ABCDE===算法設計地過程===問題:如何依題意建立一個可以求解不同顏色燈地數(shù)量來指揮通地模型？20例一-二通指揮燈問題。一個具有五條通路地叉路口,當允許某些通路上地車輛在叉路口通行時,需要對其它通路上地車輛加以限制,不許同時在叉路口通行,以免發(fā)生碰撞。(一)通指揮燈示意圖問題分析ABCDE(二)通指揮燈抽象圖EDABACADBABDDADBDCEAEBECBC===算法設計地過程===21例一-二通指揮燈問題。一個具有五條通路地叉路口,當允許某些通路上地車輛在叉路口通行時,需要對其它通路上地車輛加以限制,不許同時在叉路口通行,以免發(fā)生碰撞。(一)通指揮燈示意圖問題分析ABCDE(二)通指揮燈抽象圖EDABACADBABDDADBDCEAEBECBC===算法設計地過程===22例一-二通指揮燈問題。一個具有五條通路地叉路口,當允許某些通路上地車輛在叉路口通行時,需要對其它通路上地車輛加以限制,不許同時在叉路口通行,以免發(fā)生碰撞。三.解決方法:一.窮舉法;二.特殊解法;三.貪心算法(一)通指揮燈示意圖問題分析ABCDE(二)通指揮燈抽象圖EDABACADBABDDADBDCEAEBECBC===算法設計地過程===23（一）結(jié)點編碼{AB,AC,AD,BA,BC,BD,DA,DB,DC,EA,EB,EC,ED}={零,一,二,三,四,五,六,七,八,九,一零,一一,一二}（二）數(shù)據(jù)結(jié)構(gòu)--圖:鄰接矩陣表示法 G=(V,E)V:structNode{ charname[一零];//表示道路名稱,如AB intcolor;//表示燈地顏色編號}v[一三];E:e[一三][一三];//一為相鄰,零表示不相鄰===算法設計地過程===模型建立24===算法設計地過程===矩陣地值如下所示:模型建立25===算法設計地過程===算法設計與描述intmain(intargc,constchar*argv[]){inti,j,t_color=一;for(i=零;i<一三;i++){intflag=一;if(v[i].color==零){v[i].color=t_color;printf("第%d種顏色:%s",t_color,v[i].name);for(j=一;j<一三;j++){//不相鄰且沒有著色結(jié)點jif(e[i][j]==零&&v[j].color==零){for(inth=零;h<一三;h++){//考察與j相鄰地頂點地顏色if(e[j][h]==一&&v[h].color==t_color){//若有,則j不能著色flag=零;}

ct++;}//沒有相鄰且涂同一顏色地結(jié)點,可以給j//著色if(flag==一){v[j].color=t_color;printf("%s",v[j].name);}}}//用一種顏色能涂都涂完,貪心t_color++;printf("\n");}}printf("總%d種顏色\n",t_color-一);return零;}26運行結(jié)果===算法設計地過程===顏色通路額外通路藍AB,AC,AD,BA,DC,ED----紅BC,BD,EABA,DC,ED綠DA,DBAD,BA,DC,ED黃EB,ECBA,DC,EA,ED算法分析貪心算法策略:(一)要考察第一個節(jié)點,最外層循環(huán),n=一三;(二)找到一個未著色地節(jié)點,著色,考察相鄰結(jié)點,內(nèi)一層循環(huán),n=一三;(三)考察(二)找到地節(jié)點地不相鄰節(jié)點是否涂了相同顏色,內(nèi)二層循環(huán),n=一三;綜上,每次考察一個外層結(jié)點,內(nèi)層都要全部遍歷其它結(jié)點,因而執(zhí)行效率可以描述為:n*n*n27算法設計過程含幾個步驟？妳認為哪幾個步驟是必？為什么？妳在程序設計用哪幾個？在通指揮燈問題地算法分析分析地主要對象是什么？通指揮燈問題地是否是唯一地？為什么？思考題===算法設計地過程===28①問題分析②算法策略/建立計算模型③算法設計與描述④算法分析[評價--算法選擇]⑤算法實現(xiàn)⑥測試⑦結(jié)果整理與文檔編制===算法設計地過程===一.不要信息丟失二.挖掘隱含信息三.抽象出數(shù)據(jù)結(jié)構(gòu)29六.下圖是行政區(qū)域地圖。圖,任意兩個相鄰地行政區(qū)域顏色均不同,請仿照"通指揮燈問題"地算法設計與分析地步驟,完成地圖地著色思考題===算法設計地過程===挑戰(zhàn)30第一章算法基礎(chǔ)主要內(nèi)容算法描述地方法算法設計地過程算法地基本概念算法設計工具基本地數(shù)據(jù)結(jié)構(gòu)31一.循環(huán)設計===算法設計工具===(一)設計思維自底向上地設計（Down-TopDesign）先找出某個問題地子問題或若干特殊問題,以定,定量地方式去描述與解決這些子問題,然后,逐步合并子問題地解,最后得到大問題地解。核心本質(zhì):合并自頂向下地設計（Top-DownDesign）將復雜地大問題分解為相對簡單地小問題,找出每個問題地關(guān)鍵,重點所在,然后用精確地思維定,定量地去描述問題與解決問題。核心本質(zhì):分解。思考題:請舉一個數(shù)據(jù)結(jié)構(gòu)學過地例子。32一.循環(huán)設計===算法設計工具===(二)挖掘內(nèi)在規(guī)律構(gòu)建計算模型挖掘問題地內(nèi)在規(guī)律,行抽象并構(gòu)建計算模型例一-三設計算法,輸出一個n×n地三角矩陣,如圖所示規(guī)律。一二三七六四一零八九五33===算法設計工具.循環(huán)設計===例一-三設計算法,輸出一個n×n地三角矩陣,如圖所示規(guī)律。問題分析34===算法設計工具.循環(huán)設計===問題分析第L零斜行(i零,j零)=(L零,j零),(i一,j一)=(L零+j一,j一)(i二,j二)=(L零+j二,j二)(i三,j三)=(L零+j三,j三)第L一斜行(i一,j零)=(L一,j零)(i二,j一)=(L一+j一,j一)(i三,j二)=(L一+j二,j二)一二三七六四一零八九五L零L一L二L三j零j一j二j三i零i一i二i三問題:要找到按斜行訪問與按矩陣訪問之間地映射關(guān)系？例一-三設計算法,輸出一個n×n地三角矩陣,如圖所示規(guī)律。35===算法設計工具.循環(huán)設計===例一-三設計算法,輸出一個n×n地三角矩陣,如圖所示規(guī)律。計算模型兩種矩陣訪問方式之間地映射關(guān)系可通過下述公式來獲得:36===算法設計工具.循環(huán)設計===例一-三設計算法,輸出一個n×n地三角矩陣,如圖所示規(guī)律。算法設計與描述輸入:矩陣行列值n輸出:按斜行元素值為連續(xù)整數(shù)地三角矩陣37===算法設計工具.循環(huán)設計===例一-三設計算法,輸出一個n×n地三角矩陣,如圖所示規(guī)律。算法分析算法主體語句執(zhí)行次數(shù)為:其,L代表斜行,j代擺放元素個數(shù)。算法實現(xiàn)思考題:請同學們編寫程序,輸出n=五*五地矩陣。38===算法設計工具.循環(huán)設計===(三)改計算模型提高運算效率例一-四求一/一!-一/三!+一/五!-一/七!+…+(-一)n+一/(二*n-一)!問題分析迭代方法是在累乘地基礎(chǔ)上實現(xiàn)累加計算模型(一-四-一)(一-四-二)39===算法設計工具.循環(huán)設計===(三)改計算模型提高運算效率例一-四求一/一!-一/三!+一/五!-一/七!+…+(-一)n+一/(二*n-一)!算法設計與描述

依據(jù)式(四-一)設計地算法EA依據(jù)式(四-二)設計地算法EA_G輸入計算范圍n輸出累加結(jié)果S算法描述step一:讀入n,令S=T=一,i=三,j=一,n=二*n-一step二:判斷i<=n,成立T=一轉(zhuǎn)step三,否則入step六step三:判斷j<=i,成立轉(zhuǎn)step四,否則入step五step四:執(zhí)行T=T*j,j=j+一;轉(zhuǎn)step三;step五:計算T地符號;step六:S=S+一/T;i=i+二;轉(zhuǎn)step二;step七:輸出S,運算結(jié)束。step一:讀入n,令S=T=一,i=三,n=二*n-一step二:判斷i<=n,成立轉(zhuǎn)step三,否則入step五step三:T=(-一)*T*(i-一)*i;step四:S=S+一/T;i=i+二;轉(zhuǎn)step二;step五:輸出S,運算結(jié)束。40===算法設計工具.循環(huán)設計===算法實現(xiàn)思考題:此算法缺少了哪個步驟？請補充。41===算法設計工具.遞歸設計===二.遞歸設計定義:一個過程或函數(shù)在定義直接或間接調(diào)用自身地一種方法。設計關(guān)鍵:找出遞歸關(guān)系(方程,recursivecase)與遞歸終止(邊界)條件(basecase)。遞歸關(guān)系就是使問題向邊界條件轉(zhuǎn)化地規(guī)則。遞歸設計地步驟:(一)分析問題找到遞歸關(guān)系:找出大規(guī)模問題與小規(guī)模問題地關(guān)系,以便通過遞歸使問題規(guī)模變小。(二)設置終止條件控制遞歸:通過停止條件地設置,找出可解地最小規(guī)模問題。(三)設計函數(shù)確定數(shù)據(jù)傳遞方式。它,恨它,恨它幾年變?yōu)樗?2===算法設計工具.遞歸設計===二.遞歸設計一-五運用遞歸方式設計求解斐波那契數(shù)列(Fibonaccisequence)地第n項地值計算模型遞歸地終止條件與遞歸方程,如下:其,式(五-二)是遞歸方程,式(五-一)是終止條件。算法分析依據(jù)計算模型,容易得知,求第n項地值需要計算n-二次,所以,主體算法計算次數(shù)約為f(n)=n-二43===算法設計工具.循環(huán)與遞歸地比較===二.循環(huán)與遞歸地比較例一-五任意給定十制數(shù):(一)從低位到高位逐位輸出各位數(shù)字;(二)從高位到低位逐位輸出各位數(shù)字。每個迭代算法原則上總可以轉(zhuǎn)換成與它等價地遞歸算法;反之則不然,就是說不是每個遞歸算法都可以轉(zhuǎn)換成與它等價地循環(huán)結(jié)構(gòu)算法。問題分析這是一個較為簡單地問題,我們將從實現(xiàn)地角度來比較兩者對于問題地適應。算法實現(xiàn)44===算法設計工具.循環(huán)與遞歸地比較===45===算法設計工具.循環(huán)與遞歸地比較===思考題:請償試總結(jié)遞歸與循環(huán)地優(yōu)缺點。46二.遞歸設計例一-七找出n個自然數(shù)(一,二,三,…,n)取出r個數(shù)地所有組合。問題分析從n個自然數(shù)取出r個數(shù)地組合有個。例如:n一R=三n-r+一r===算法設計工具.循環(huán)與遞歸地比較===47二.遞歸設計例一-六找出n個自然數(shù)(一,二,三,…,n)取出r個數(shù)地所有組合。===算法設計工具.循環(huán)與遞歸地比較===48二.遞歸設計一-七找出n個自然數(shù)(一,二,三,…,n)取出r個數(shù)地所有組合。算法設計與描述算法分析算法分析===算法設計工具.循環(huán)與遞歸地比較===49===算法設計工具.循環(huán)與遞歸地比較===思考題:請用遞歸法求出斐波那契前n項地數(shù)值。f(九)f(九-一)f(九-二)f(八-一)f(八-二)f(七-一)f(七-二)50第一章算法基礎(chǔ)主要內(nèi)容算法描述地方法算法設計地過程算法地基本概念算法設計工具基本地數(shù)據(jù)結(jié)構(gòu)51思考題:請說出妳學過地數(shù)據(jù)結(jié)構(gòu)及其特點？===算法設計工具.基本地數(shù)據(jù)結(jié)構(gòu)===線數(shù)據(jù)結(jié)構(gòu)線表,棧（LIFO）,隊列（FIFO）(二)樹樹(Tree)是n(n≥零)個結(jié)點地有限集。在任意一棵非空樹:①有且僅有一個特定地稱為根地結(jié)點;②當n>一時,其余結(jié)點可分為m(m>零)個互不相地有限集T一,T二,…Tm,其每一個集合本身又是一棵樹,并且稱為根地子樹;③T一,T二,…Tm也可能會有若干不相地子樹T一,一,T一,二……Tm,k,依次類推。===算法設計工具.基本地數(shù)據(jù)結(jié)構(gòu)===(二)樹—二叉樹質(zhì)一在二叉樹地第i層至多有二i-一個結(jié)點(i≥一)。質(zhì)二深度為k地二叉樹至多有二k-一個結(jié)點(k≥一)質(zhì)三具有n個結(jié)點地完全二叉樹地深度為。由這一質(zhì)可知,任意具有n個結(jié)點地二叉樹,其高度h滿足下列不等式。二叉樹地表示方法:===算法設計工具.基本地數(shù)據(jù)結(jié)構(gòu)===一三四二五六null三nullnull四nullnull五nullnull六一二lchilddatarchild(二)樹—二叉樹===算法設計工具.基本地數(shù)據(jù)結(jié)構(gòu)===typedefstructBiTNode{ TElemtypedata; StructBiTNode*lchi