算法設(shè)計(jì)與分析第3-4講

《算法設(shè)計(jì)與分析第3-4講》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、智能信息處理研究中心（RCIIP）第第22章章遞歸與分治策略遞歸與分治策略潘海為http://rciip.hrbeu.edu.cn1智能信息處理研究中心（RCIIP）學(xué)習(xí)要點(diǎn)?理解遞歸的概念。P?掌握設(shè)計(jì)有效算法的分治策略。?通過下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧。1)二分搜索技術(shù)；a2)大整數(shù)乘法；3)Strassen矩陣乘法；4)合并排序和快速排序；5)線性時(shí)間選擇；n6)最接近點(diǎn)對(duì)問題；2智能信息處理研究中心（RCIIP）算法總體思想??對(duì)這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠?qū)⒁蠼獾妮^大規(guī)模的問題分割成k個(gè)更小規(guī)模的子問P小，則再劃分為k個(gè)子問題，如

2、此遞歸的進(jìn)行下去，直題。到問題規(guī)模足夠小，很容易求出其解為止。naT(n)=nT(n/k)T(n/k)T(n/k)T(n/k)3智能信息處理研究中心（RCIIP）算法總體思想??對(duì)這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠?qū)⑶蟪龅男∫?guī)模的問題的解合并為一個(gè)更大規(guī)模的問P小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直題的解，自底向上逐步求出原來問題的解。到問題規(guī)模足夠小，很容易求出其解為止。T(n)=nan/kn/kn/knn/kT(n/k2)T(n/k2)4智能信息處理研究中心（RCIIP）算法總體思想?將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問P題的解

3、，自底向上逐步求出原來問題的解。T(n)=nan/kn/kn/knn/k5智能信息處理研究中心（RCIIP）算法總體思想?將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問P題的解，自底向上逐步求出原來問題的解。T(n)=nan/kn/kn/knn/k6智能信息處理研究中心（RCIIP）算法總體思想Divide?Divide=整個(gè)問題劃分P為多個(gè)子問題?Conquer=求解每個(gè)子問題(遞歸調(diào)用正在設(shè)Conquer計(jì)的算法)?Combine=合并子問題a的解,形成原始問題的解。分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，n

4、Combine分而治之。7智能信息處理研究中心（RCIIP）實(shí)例——二分搜索輸入：非降序排列的n個(gè)元素?cái)?shù)組a[1..n]和元素xP輸出：m,ifx=a[m]0,ifx不存在BinarySearch(l,r){aifl>rthenreturn0;elsem=(l+r)/2;if(x=a[m])returnm;nif(x

5、。?由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種a情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。n?分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。9智能信息處理研究中心（RCIIP）遞歸的概念例1階乘函數(shù)P階乘函數(shù)可遞歸地定義為：邊界條件?1n?0n!??a?n(n?1)!n?0遞歸方程n邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。10智能信息處理研究中

6、心（RCIIP）遞歸的概念例2Fibonacci數(shù)列P無窮數(shù)列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件?1n?0?aF(n)??1n?1??F(n?)1?F(n?)2n?1第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：遞歸方程intfibonacci(intn)n{if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}11智能信息處理研究中心（RCIIP）遞歸的概念例3整數(shù)劃分問題P將正整數(shù)n表示成一系列正整數(shù)之和：n=n+n+…+n，12k其中

7、n1≥n2≥…≥nk≥1，k≥1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。例如正整數(shù)6有如下不同的劃分：a6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；n2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。12智能信息處理研究中心（RCIIP）遞歸的概念例3整數(shù)劃分問題P前面的幾個(gè)例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n

8、,m)的如