




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、編寫遞歸程序有幾個(gè)重要的原則可以遵循:.要解決的問(wèn)題可拆分為幾個(gè)與原問(wèn)題類似 的子問(wèn)題(子問(wèn)題仍可拆分)。.每個(gè)子問(wèn)題必須比原來(lái)問(wèn)題的規(guī)模更小(即使小一號(hào)也行,當(dāng)然如果能夠迅速減小規(guī)模更好)。.遇到足夠小的子問(wèn)題時(shí)就直接解決之,防止問(wèn)題無(wú)限細(xì)分下去,也就是防止無(wú)限遞歸(遞歸終止條件很重要)。先看一個(gè)最簡(jiǎn)單的遞歸程序,下面程序求整數(shù)的階乘:( ) ? : *();所謂遞歸程序,就是程序在執(zhí)行中又調(diào)用其自身,如上面函數(shù)在其函數(shù)體內(nèi)調(diào)用了函數(shù)。函數(shù)在每次被調(diào)用時(shí)都會(huì)生成一個(gè)包含自身局部變量的副本,即算是函數(shù)調(diào)用自身時(shí)也是如此。遞歸程序主體主要由兩部分構(gòu)成:一是遞歸執(zhí)行部分,包含遞歸執(zhí)行所需的條件;一
2、是遞歸終止部分,含遞歸終止條件。上面求階乘的程序中把這兩部分寫在一行代碼里面,把其分別抽出來(lái)便是:( )( ) ;遞歸終止體*();遞歸執(zhí)行體下面以幾個(gè)經(jīng)典算法問(wèn)題的遞歸程序求解為例來(lái)分析編寫遞歸程序中可以遵循的簡(jiǎn)單規(guī)則。. 求正整數(shù)所有可能的和式的組合,如給定正整數(shù),所有和加起來(lái)等于的和式如下:其中一個(gè)和式中的因子只能為自然數(shù),因子允許重復(fù)出現(xiàn)。這個(gè)問(wèn)題是一個(gè)組合問(wèn)題的變形,用遞歸程序?qū)崿F(xiàn)如下(分析見(jiàn)注釋):;存儲(chǔ)和式因子組合的緩沖求當(dāng)前和式中因子之和。1 / 14( );( ; ; );打印當(dāng)前滿足條件的和式。( ), ;(; ; )注意這里的循環(huán)條件,可以有效防止出現(xiàn)重復(fù)的組合 ;( (
3、)首先要確定遞歸中止條件();( )和式中的因子不應(yīng)該超過(guò)和的大小;();減小問(wèn)題規(guī)模,繼續(xù)遞歸;()2 / 14;(:);();();. 給定正整數(shù),以及共 個(gè)正整數(shù)的一個(gè)排列, 假如是 ,. ,求所有和此排列 “不相交 ”的排列。所謂不相交,是指新的排列和已有排列在同一位置上的數(shù)都不相同。如假設(shè),則其排列:和是相交的,因?yàn)榈诙€(gè)位置上都是;而排列和則不相交。問(wèn)題分析: 此問(wèn)題是普通排列問(wèn)題的變形, 只要在排列問(wèn)題的遞歸程序中加上位置的限制即可,程序?qū)崿F(xiàn)如下,具體分析見(jiàn)注釋。; ;預(yù)定義好位置的排列判斷當(dāng)前選擇的數(shù)是否已經(jīng)被使用。( , * )( ; ; )();求不相交排列。當(dāng)前排列的位置
4、或者說(shuō)當(dāng)前排列元素個(gè)數(shù)。存儲(chǔ)當(dāng)前排列的數(shù)組。存儲(chǔ)不相交排列的數(shù)目。( , * , )( )遞歸終止條件( ; ; ) ; ;3 / 14( ; ; )循環(huán)挑選當(dāng)前位置可以放置的數(shù)()判斷當(dāng)前選定的數(shù)是夠已經(jīng)用過(guò); ;( )回溯的限制條件,同一位置的數(shù)不能和預(yù)定義的排列中相應(yīng)位置的數(shù)相同;();繼續(xù)遞歸 ;回溯,重新初始化當(dāng)前位置() ;(); ;遞歸程序求解問(wèn)題雖然優(yōu)美簡(jiǎn)潔,但是和相應(yīng)的非遞歸程序比較,隨著問(wèn)題規(guī)模的增大,程序的效率會(huì)逐漸下降,這也是遞歸程序的一大缺陷盡管排列組合是生活中經(jīng)常遇到的問(wèn)題,可在程序設(shè)計(jì)時(shí),不深入思考或者經(jīng)驗(yàn)不足都讓人無(wú)從下手。由于排列組合問(wèn)題總是先取組合再排列,并
5、且單純的排列問(wèn)題相對(duì)簡(jiǎn)單,所以本文僅對(duì)組合問(wèn)題的實(shí)現(xiàn)進(jìn)行詳細(xì)討論。以在個(gè)數(shù)中選取 ( 。用來(lái)存儲(chǔ)當(dāng)前組合中的元素( 這里存儲(chǔ)的是元素下標(biāo)) ,常量表示滿足條件的一個(gè)組合中元素的個(gè)數(shù),這兩個(gè)參數(shù)僅用來(lái)輸出結(jié)果。( , , ,)( ; ; )注意這里的循環(huán)范圍;( )();,輸出一個(gè)組合( ; ; ) ; ;因?yàn)檫f歸程序均可以通過(guò)引入棧,用回溯轉(zhuǎn)化為相應(yīng)的非遞歸程序,所以組合問(wèn)題又可以用回溯的方法來(lái)解決。為了便于理解,我們可以把組合問(wèn)題化歸為圖的路徑遍歷問(wèn)題,在個(gè)數(shù)中選取個(gè)數(shù)的所有組合,相當(dāng)于在一個(gè)這樣的圖中(下面以從中任選個(gè)數(shù)為例說(shuō)明)求從 位置出發(fā)到達(dá) ( ? : ;5 / 14*;( ; ;
6、 ) ;注意這里 用來(lái)作為循環(huán)判斷標(biāo)識(shí);標(biāo)志找到一個(gè)有效組合( )()輸出符合要求的組合(; ; ) ; ;在當(dāng)前位置選擇新的數(shù)字( )當(dāng)前位置已無(wú)數(shù)字可選,回溯 ;( )更新當(dāng)前位置的下一位置的數(shù)字 ;( ); ;下面是測(cè)試以上函數(shù)的程序:();6 / 14;( ) ;回溯方法 () ;遞歸方法;();由上述分析可知, 解決組合問(wèn)題的通用算法不外乎遞歸和回溯兩種。在針對(duì)具體問(wèn)題的時(shí)候,因?yàn)檫f歸程序在遞歸層數(shù)上的限制, 對(duì)于大型組合問(wèn)題而言, 遞歸不是一個(gè)好的選擇, 這種情況下只能采取回溯的方法來(lái)解決。個(gè)數(shù)的全排列問(wèn)題相對(duì)簡(jiǎn)單,可以通過(guò)交換位置按序枚舉來(lái)實(shí)現(xiàn)。提供了求某個(gè)序列下一個(gè)排列的算法,
7、其算法原理如下:. 從當(dāng)前序列最尾端開始往前尋找兩個(gè)相鄰元素,令前面一個(gè)元素為*,后一個(gè)元素為*,且滿足 * ;. 再次從當(dāng)前序列末端開始向前掃描,找出第一個(gè)大于*的元素,令為*(可能等于),將,元素對(duì)調(diào);. 將之后(含)的所有元素顛倒次序,這樣所得的排列即為當(dāng)前序列的下一個(gè)排列。其實(shí)現(xiàn)代碼如下:( , )( ) ;空範(fàn)圍;( ) ;只有一個(gè)元素;指向尾端;(;);以上,鎖定一組(兩個(gè))相鄰元素(* *)如果前一個(gè)元素小於後一個(gè)元素7 / 14;令 指向尾端(!(* *);由尾端往前找,直到遇上比*大的元素(, );交換 ,(, );將之後的元素全部逆向重排;( )進(jìn)行至最前面了(, );全部
8、逆向重排;下面程序演示了利用來(lái)求取某個(gè)序列全排列的方法:() ; ()();()()(, ); ;()()()()(, ); ;注意: 上面程序中初始序列是按數(shù)值的從小到大的順序排列的,如果初始序列無(wú)序的話,上面程序只能求出從當(dāng)前序列開始的后續(xù)部分排列,也就是說(shuō)求出的排列是按排列從小到大的順序進(jìn)行的。最優(yōu)化原理年美國(guó)數(shù)學(xué)家等人,根據(jù)一類多階段問(wèn)題的特點(diǎn),把多階段決策問(wèn)題變換為一系列互相聯(lián)系的單階段問(wèn)題,然后逐個(gè)加以解決。一些靜態(tài)模型,只要人為地引進(jìn) “時(shí)間 ”因素,分成時(shí)段, 就可以轉(zhuǎn)化成多階段的動(dòng)態(tài)模型, 用動(dòng)態(tài)規(guī)劃方法去處理。 與此同時(shí), 他提出了8 / 14解決這類問(wèn)題的“最優(yōu)化原理 ”
9、():“一個(gè)過(guò)程的最優(yōu)決策具有這樣的性質(zhì):即無(wú)論其初始狀態(tài)和初始決策如何,其今后諸策略對(duì)以第一個(gè)決策所形成的狀態(tài)作為初始狀態(tài)的過(guò)程而言,必須構(gòu)成最優(yōu)策略”。簡(jiǎn)言之,一個(gè)最優(yōu)策略的子策略,對(duì)于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。這個(gè) “最優(yōu)化原理 ”如果用數(shù)學(xué)化一點(diǎn)的語(yǔ)言來(lái)描述的話, 就是:假設(shè)為了解決某一優(yōu)化問(wèn)題,需要依次作出個(gè)決策, ,如若這個(gè)決策序列是最優(yōu)的,對(duì)于任何一個(gè)整數(shù), ,不論前面?zhèn)€決策是怎樣的,以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài),即以后的決策, ,也是最優(yōu)的。最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)。任何一個(gè)問(wèn)題,如果失去了這個(gè)最優(yōu)化原理的支持,就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算。能采用動(dòng)態(tài)
10、規(guī)劃求解的問(wèn)題都需要滿足一定的條件:()問(wèn)題中的狀態(tài)必須滿足最優(yōu)化原理;()問(wèn)題中的狀態(tài)必須滿足無(wú)后效性。所謂的無(wú)后效性是指:“下一時(shí)刻的狀態(tài)只與當(dāng)前狀態(tài)有關(guān),而和當(dāng)前狀態(tài)之前的狀態(tài)無(wú)關(guān),當(dāng)前的狀態(tài)是對(duì)以往決策的總結(jié)”。問(wèn)題求解模式動(dòng)態(tài)規(guī)劃所處理的問(wèn)題是一個(gè)多階段決策問(wèn)題,一般由初始狀態(tài)開始,通過(guò)對(duì)中間階段決策的選擇, 達(dá)到結(jié)束狀態(tài)。 這些決策形成了一個(gè)決策序列, 同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線 ( 通常是求最優(yōu)的活動(dòng)路線 ) 。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式,一般要經(jīng)歷以下幾個(gè)步驟。初始狀態(tài) 決策 決策 決策 結(jié)束狀態(tài)圖 動(dòng)態(tài)規(guī)劃決策過(guò)程示意圖()劃分階段:按照問(wèn)題的時(shí)間或空
11、間特征,把問(wèn)題分為若干個(gè)階段。在劃分階段時(shí),注意劃分后的階段一定要是有序的或者是可排序的,否則問(wèn)題就無(wú)法求解。()確定狀態(tài)和狀態(tài)變量:將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。當(dāng)然,狀態(tài)的選擇要滿足無(wú)后效性。()確定決策并寫出狀態(tài)轉(zhuǎn)移方程:因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系,狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。 所以如果確定了決策, 狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過(guò)來(lái)做,根據(jù)相鄰兩段各狀態(tài)之間的關(guān)系來(lái)確定決策。()尋找邊界條件:給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式,需要一個(gè)遞推的終止條件或邊界條件。算法實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì),也就是上
12、面?zhèn)€步驟的確定,一旦設(shè)計(jì)完成,實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。使用動(dòng)態(tài)規(guī)劃求解問(wèn)題,最重要的就是確定動(dòng)態(tài)規(guī)劃三要素:?jiǎn)栴}的階段 , 每個(gè)階段的 狀態(tài) 以及從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系 。遞推關(guān)系必須是從次小的問(wèn)題開始到較大的問(wèn)題之間的轉(zhuǎn)化,從這個(gè)角度來(lái)說(shuō), 動(dòng)態(tài)規(guī)劃往往可以用遞歸程序來(lái)實(shí)現(xiàn), 不過(guò)因?yàn)檫f推可以充分利用前面保存的子問(wèn)題的解來(lái)減少重復(fù)計(jì)算,所以對(duì)于大規(guī)模問(wèn)題來(lái)說(shuō),有遞歸不可比擬的優(yōu)勢(shì),這也是動(dòng)態(tài)規(guī)劃算法的核心之處。確定了動(dòng)態(tài)規(guī)劃的這三要素, 整個(gè)求解過(guò)程就可以用一個(gè)最優(yōu)決策表 來(lái)描述,最優(yōu)決策表是一個(gè)二維表,9 / 14其中行表示決策的階段, 列表示問(wèn)題狀態(tài), 表格需要填寫的數(shù)
13、據(jù)一般對(duì)應(yīng)此問(wèn)題的在某個(gè)階段某個(gè)狀態(tài)下的最優(yōu)值(如最短路徑,最長(zhǎng)公共子序列,最大價(jià)值等),填表的過(guò)程就是根據(jù)遞推關(guān)系,從行列開始,以行或者列優(yōu)先的順序,依次填寫表格,最后根據(jù)整個(gè)表格的數(shù)據(jù)通過(guò)簡(jiǎn)單的取舍或者運(yùn)算求得問(wèn)題的最優(yōu)解。 下面分別以求解最大化投資回報(bào)問(wèn)題和最長(zhǎng)公共子序列問(wèn)題為例闡述用動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的一般思路。.最大化投資回報(bào)問(wèn)題:某人有一定的資金用來(lái)購(gòu)買不同面額的債卷,不同面額債卷的年收益是不同的, 求給定資金, 年限以及債卷面額、 收益的情況下怎樣購(gòu)買才能使此人獲得最大投資回報(bào)。程序輸入約定:第一行第一列表示資金(的倍數(shù))總量,第二列表示投資年限;第二行表示債卷面額總數(shù);從第三
14、行開始每行表示一種債卷,占用兩列,前一列表示債卷面額,后一列表示其年收益,如下輸入實(shí)例,程序?qū)崿F(xiàn)如下,注釋幾乎說(shuō)明了一切,所以不再另外分析。此數(shù)組是算法的關(guān)鍵存儲(chǔ)結(jié)構(gòu),用來(lái)存儲(chǔ)不同階段各種債卷組合下對(duì)應(yīng)可獲取的最大利息。;此函數(shù)用于計(jì)算當(dāng)前債卷在不同購(gòu)買額下的最優(yōu)利息情況,注意此時(shí)的利息情況是基于上一次債卷的情況下計(jì)算得到的,也就是說(shuō)當(dāng)前利息最優(yōu)是基于上一次利息最優(yōu)的基礎(chǔ)上計(jì)算出來(lái)的,這也正好體現(xiàn)了動(dòng)態(tài)規(guī)劃中 “最優(yōu)化原則 ”:不管前面的策略如何,此后的決策必須是基于當(dāng)前狀態(tài)(由上一次決策產(chǎn)生)的最優(yōu)決策。*動(dòng)態(tài)規(guī)劃的求解過(guò)程一般都可以用一個(gè)最優(yōu)決策表來(lái)描述,對(duì)于本程序,以示例輸入為例,對(duì)于第
15、一年,其最優(yōu)決策表如下:(*)()()()()表示首先選利息為的債卷在對(duì)應(yīng)資金下的最優(yōu)利息。()表示可用來(lái)購(gòu)買債卷的資金。()表示在已有狀態(tài)下再選擇利息為的債卷在對(duì)應(yīng)資金下的最優(yōu)利息。注意上面表格,在求購(gòu)買利息為的債卷獲得的最優(yōu)收益的時(shí)候,參考了以前的最優(yōu)狀態(tài),以行列的為例,(*)可以在以前購(gòu)買了張的債卷的基礎(chǔ)上再?gòu)埖?,也可以在以前?gòu)買了張的基礎(chǔ)上再買張,經(jīng)比較取其收益大的,這就是典型的動(dòng)態(tài)規(guī)劃中的當(dāng)前最優(yōu)狀態(tài)計(jì)算。本程序中把上面的最優(yōu)決策二維表用一個(gè)一維數(shù)組表示,值得借鑒。*10 / 14( ) ; ( );( )累計(jì)同時(shí)購(gòu)買多種債卷時(shí)的利息 ;() ; ;();();()();();();()();();計(jì)算指定年限內(nèi)最優(yōu)組合的本金利息
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 股權(quán)抵押融資信托合作框架協(xié)議
- 房屋買賣三方售后服務(wù)與糾紛解決合同
- 新能源汽車研發(fā)股東投資管理合同
- 股權(quán)代理及股權(quán)變更代理合同
- 沖擊鉆施工安全防護(hù)措施責(zé)任合同
- 離婚財(cái)產(chǎn)分割協(xié)議書范本含知識(shí)產(chǎn)權(quán)分割
- 餐飲場(chǎng)所托管租賃合同模板(含員工培訓(xùn)及管理)
- 物聯(lián)網(wǎng)倉(cāng)儲(chǔ)租賃與智能化物業(yè)運(yùn)營(yíng)管理合同模板
- 火鍋店特許經(jīng)營(yíng)合同范本
- 柴油批發(fā)市場(chǎng)建設(shè)與運(yùn)營(yíng)合同
- 浙江省湖州市2023-2024學(xué)年高一下學(xué)期6月期末考試 地理 含解析
- 食品安全法從業(yè)人員管理制度
- 工廠班組安全培訓(xùn)課件
- 2010浙G22 先張法預(yù)應(yīng)力混凝土管樁
- 以客戶為中心的銀行服務(wù)體驗(yàn)優(yōu)化
- 《慢性乙型肝炎防治指南(2022年版)-》解讀
- 劃線及交通設(shè)施工程施工方案
- 2025年中考物理終極押題猜想(廣東省卷專用)(解析版)
- 學(xué)校食堂自營(yíng)管理實(shí)施方案
- 2024年10月自考00882學(xué)前教育心理學(xué)試題及答案含評(píng)分參考
- 廣東省廣州市2024年中考道德與法治試卷(含答案)
評(píng)論
0/150
提交評(píng)論