資源描述：
《遞歸與分治法sch1》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析DesignandAnalysisofAlgorithmsDesignandAnalysisofAlgorithmsDesignandAnalysisofAlgorithms主講人主講人徐徐云云Fall2010Fall2010,USTC,USTC第第11章章((補(bǔ)充補(bǔ)充))遞歸與分治法遞歸與分治法1.11.1遞歸設(shè)計(jì)技術(shù)遞歸設(shè)計(jì)技術(shù)1.21.2二分查找二分查找1.31.3大整數(shù)乘法大整數(shù)乘法1.41.4StrassenStrassen矩陣乘法矩陣乘法1.51.5導(dǎo)線和開關(guān)導(dǎo)線和開關(guān)1.1遞歸設(shè)計(jì)技術(shù)ò遞歸的概念和種類ò遞歸方法的三種應(yīng)
2、用ò一個(gè)簡單示例：n!ò遞歸算法的非遞歸實(shí)現(xiàn)ò遞歸算法設(shè)計(jì)舉例2010-10-12算法設(shè)計(jì)與分析3遞歸的概念和種類ò遞歸的定義若一個(gè)對(duì)象部分地包含它自己,或用它自己給自己定義,則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過程直接地或間接地調(diào)用自己,則稱這個(gè)過程是遞歸的過程。ò遞歸有兩種直接遞歸：自己調(diào)用自己間接遞歸：A調(diào)用B，B調(diào)用A2010-10-12算法設(shè)計(jì)與分析4遞歸方法的三種應(yīng)用ò以下三個(gè)方面常用到遞歸方法①遞歸定義如，自然數(shù)定義：-1是自然數(shù)；-一個(gè)自然數(shù)加1(后繼)仍是自然數(shù)；注：“1是自然數(shù)”是遞歸的臨界條件②遞歸的數(shù)據(jù)結(jié)構(gòu)如，單鏈表節(jié)點(diǎn)是遞歸擴(kuò)展的③問題的遞歸解
3、法如，漢諾塔問題的直觀解法2010-10-12算法設(shè)計(jì)與分析5一個(gè)簡單示例：n!?1n=0òn階乘的定義：n!=??n*(n?1)！n>0ò以求3！為例的計(jì)算過程Fact(3)Fact(3)逐層調(diào)用3*Fact(2)=6逐層返回Fact(2)Fact(2)2*Fact(1)=2Fact(1)112010-10-12算法設(shè)計(jì)與分析6遞歸算法的非遞歸實(shí)現(xiàn)ò示例：n!的遞歸和非遞歸算法Fact1(n)//遞歸程序Fact2(intn)//非遞歸程序{ifn=0return1;{p=1;elsereturnn*fact1(n-1);fori←1tondop←p*i;}r
4、eturnp;}òRemark：(1)遞歸算法易設(shè)計(jì)和分析，但執(zhí)行效率較低，常要轉(zhuǎn)化為非遞歸程序；(2)遞歸算法的非遞歸實(shí)現(xiàn)通常有三種實(shí)現(xiàn)方法：①利用棧消除遞歸②利用迭代法消除遞歸③末尾遞歸消除法2010-10-12算法設(shè)計(jì)與分析7遞歸算法的非遞歸實(shí)現(xiàn)ò思考題：Fibonacci數(shù)遞歸和非遞歸算法Fibonacci(n)?0n=0{//非遞歸算法?ifn=0orn=1thenFn=?1n=1?returnn;F+Fn≥2?n?1n?2s1=0;s2=1;fori←2tondoFibonacci(n){{//遞歸算法sum←s1+s2;ifn=0orn=1then
5、s1←s2;returnn;s2←sum;else}returnFibonacci(n-1)+Fibonacci(n-2);returnsum;}}2010-10-12算法設(shè)計(jì)與分析8遞歸算法設(shè)計(jì)舉例:漢諾塔（1）ò漢諾塔（HanoiTower）問題：這是一個(gè)流傳很久的游戲。1.有三根桿子A,B,C。A桿上有n只碟子2.每次移動(dòng)一塊碟子,小的只能疊在大的上面3.把所有碟子從A桿經(jīng)C桿全部移到B桿上.Peg#1Peg#2Peg#32010-10-12算法設(shè)計(jì)與分析9遞歸算法設(shè)計(jì)舉例:漢諾塔（2）ò遞歸求解：1.若只有一只碟子，直接將它從A桿移到B桿；2.把n-1只
6、碟子從A桿經(jīng)B桿移動(dòng)到C桿，將A桿上第n只碟子移到B桿；然后再將n-1只碟子從C桿經(jīng)A桿移到B桿。2010-10-12算法設(shè)計(jì)與分析10遞歸算法設(shè)計(jì)舉例:漢諾塔（3）ò遞歸算法Hanoi(n,A,B,C){//將從小到大的n個(gè)圓盤從A移到Bifn>0then{Hanoi(n-1,A,C,B);//將從小到大的n-1個(gè)圓盤從A移到CMove(n,A,B);//將第n大的圓盤從A移到BHanoi(n-1,C,B,A);//將從小到大的n-1個(gè)圓盤從C移到B}}ò算法分析?正確性：用歸納法證明；?時(shí)間復(fù)雜性：T(n)=1+2T(n-1)?O(2n)?算法的最優(yōu)性：為最
7、優(yōu)的2010-10-12算法設(shè)計(jì)與分析11遞歸算法設(shè)計(jì)舉例:再論Fib數(shù)（1）ò基于Fibonacci數(shù)遞歸定義的算法：T(n)=Ω((3/2)n)ò改進(jìn)的算法：利用公式?0n=0??1n=1Fn=?()2()2F+Fn≥2且為奇數(shù)???n/2??n/2?12?()F+2FFn≥2且為偶數(shù)???n/2????n/2n/2?1-算法：Fibonacci(intn)a←Fibonacci((n+1)/2);{ifn=0orn=1thenb←Fibonacci((n+1)/2-1);returnn;ifnmod2=0thenelse{returna*(a+2*b);e
8、lsereturna*a
