經(jīng)典算法設(shè)計(jì)方法大雜燴

1、.經(jīng)典算法設(shè)計(jì)方法大雜燴經(jīng)典算法設(shè)計(jì)方法大雜燴2010-03-31 21：56一、什么是算法算法是一系列解決問(wèn)題的清晰指令，也就是說(shuō)，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。算法常常含有重復(fù)的步驟和一些比較或邏輯判斷。如果一個(gè)算法有缺陷，或不適合于某個(gè)問(wèn)題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問(wèn)題。不同的算法可能用不同的時(shí)間、空間或效率來(lái)完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來(lái)衡量。算法的時(shí)間復(fù)雜度是指算法需要消耗的時(shí)間資源。一般來(lái)說(shuō)，計(jì)算機(jī)算法是問(wèn)題規(guī)模n的函數(shù)f(n)，算法執(zhí)行的時(shí)間的增長(zhǎng)率與f(n)的增長(zhǎng)率正相關(guān)，稱作漸進(jìn)時(shí)間復(fù)雜度(Asymptotic Time

2、Complexity)。時(shí)間復(fù)雜度用"O(數(shù)量級(jí))"來(lái)表示，稱為"階"。常見的時(shí)間復(fù)雜度有：O(1)常數(shù)階；O(log2n)對(duì)數(shù)階；O(n)線性階；O(n2)平方階。算法的空間復(fù)雜度是指算法需要消耗的空間資源。其計(jì)算和表示方法與時(shí)間復(fù)雜度類似，一般都用復(fù)雜度的漸近性來(lái)表示。同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析要簡(jiǎn)單得多。二、算法設(shè)計(jì)的方法1.遞推法遞推法是利用問(wèn)題本身所具有的一種遞推關(guān)系求問(wèn)題解的一種方法。設(shè)要求問(wèn)題規(guī)模為N的解，當(dāng)N=1時(shí)，解或?yàn)橐阎?，或能非常方便地得到解。能采用遞推法構(gòu)造算法的問(wèn)題有重要的遞推性質(zhì)，即當(dāng)?shù)玫絾?wèn)題規(guī)模為i-1的解后，由問(wèn)題

3、的遞推性質(zhì)，能從已求得的規(guī)模為1，2，i-1的一系列解，構(gòu)造出問(wèn)題規(guī)模為I的解。這樣，程序可從i=0或i=1出發(fā)，重復(fù)地，由已知至i-1規(guī)模的解，通過(guò)遞推，獲得規(guī)模為i的解，直至得到規(guī)模為N的解?！締?wèn)題】階乘計(jì)算問(wèn)題描述：編寫程序，對(duì)給定的n(n 100)，計(jì)算并輸出k的階乘k！(k=1，2，n)的全部有效數(shù)字。由于要求的整數(shù)可能大大超出一般整數(shù)的位數(shù)，程序用一維數(shù)組存儲(chǔ)長(zhǎng)整數(shù)，存儲(chǔ)長(zhǎng)整數(shù)數(shù)組的每個(gè)元素只存儲(chǔ)長(zhǎng)整數(shù)的一位數(shù)字。如有m位成整數(shù)N用數(shù)組a存儲(chǔ)：N=am×10m-1+am-1×10m-2+a2×101+a1×100并用a0存儲(chǔ)長(zhǎng)整數(shù)N的位數(shù)m，

4、即a0=m。按上述約定，數(shù)組的每個(gè)元素存儲(chǔ)k的階乘k！的一位數(shù)字，并從低位到高位依次存于數(shù)組的第二個(gè)元素、第三個(gè)元素。例如，5！=120，在數(shù)組中的存儲(chǔ)形式為：3 02 1首元素3表示長(zhǎng)整數(shù)是一個(gè)3位數(shù)，接著是低位到高位依次是0、2、1，表示成整數(shù)120。計(jì)算階乘k！可采用對(duì)已求得的階乘(k-1)！連續(xù)累加k-1次后求得。例如，已知4！=24，計(jì)算5！，可對(duì)原來(lái)的24累加4次24后得到120。細(xì)節(jié)見以下程序。#include stdio.h#include malloc.h#define MAXN 1000 void pnext(int a,int k)int*b,m=a0,i,j,r,car

5、ry；b=(int*)malloc(sizeof(int)*(m+1)；for(i=1；i=m；i+)bi=ai；for(j=1；j=k；j+)for(carry=0,i=1；i=m；i+)r=(i a0?ai+bi：ai)+carry；ai=r%10；carry=r/10；if(carry)a+m=carry；free(b)；a0=m；void write(int*a,int k)int i；printf("%4d！=",k)；for(i=a0；i 0；i-)printf("%d",ai)；printf("nn")；void mai

6、n()int aMAXN,n,k；printf("Enter the number n：")；scanf("%d",&n)；a0=1；a1=1；write(a,1)；for(k=2；k=n；k+)pnext(a,k)；write(a,k)；getchar()；2.遞歸遞歸是設(shè)計(jì)和描述算法的一種有力的工具，由于它在復(fù)雜算法的描述中被經(jīng)常采用，為此在進(jìn)一步介紹其他算法設(shè)計(jì)方法之前先討論它。能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為N的問(wèn)題，設(shè)法將它分解成規(guī)模較小的問(wèn)題，然后從這些小問(wèn)題的解方便地構(gòu)造出大問(wèn)題的解，并且這些規(guī)模較小的問(wèn)題也能采用

7、同樣的分解和綜合方法，分解成規(guī)模更小的問(wèn)題，并從這些更小問(wèn)題的解構(gòu)造出規(guī)模較大問(wèn)題的解。特別地，當(dāng)規(guī)模N=1時(shí)，能直接得解?！締?wèn)題】編寫計(jì)算斐波那契(Fibonacci)數(shù)列的第n項(xiàng)函數(shù)fib(n)。斐波那契數(shù)列為：0、1、1、2、3、，即：fib(0)=0；fib(1)=1；fib(n)=fib(n-1)+fib(n-2)(當(dāng)n 1時(shí))。寫成遞歸函數(shù)有：int fib(int n)if(n=0)return 0；if(n=1)return 1；if(n 1)return fib(n-1)+fib(n-2)；遞歸算法的執(zhí)行過(guò)程分遞推和回歸兩個(gè)階段。在遞推階段，把較復(fù)雜的問(wèn)題(規(guī)模為n)的求解推

8、到比原問(wèn)題簡(jiǎn)單一些的問(wèn)題(規(guī)模小于n)的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說(shuō)，為計(jì)算fib(n)，必須先計(jì)算fib(n-1)和fib(n-2)，而計(jì)算fib(n-1)和fib(n-2)，又必須先計(jì)算fib(n-3)和fib(n-4)。依次類推，直至計(jì)算fib(1)和fib(0)，分別能立即得到結(jié)果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數(shù)fib中，當(dāng)n為1和0的情況。在回歸階段，當(dāng)獲得最簡(jiǎn)單情況的解后，逐級(jí)返回，依次得到稍復(fù)雜問(wèn)題的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的結(jié)果，在得到了fib(n-1)和

9、fib(n-2)的結(jié)果后，返回得到fib(n)的結(jié)果。在編寫遞歸函數(shù)時(shí)要注意，函數(shù)中的局部變量和參數(shù)知識(shí)局限于當(dāng)前調(diào)用層，當(dāng)遞推進(jìn)入"簡(jiǎn)單問(wèn)題"層時(shí)，原來(lái)層次上的參數(shù)和局部變量便被隱蔽起來(lái)。在一系列"簡(jiǎn)單問(wèn)題"層，它們各有自己的參數(shù)和局部變量。由于遞歸引起一系列的函數(shù)調(diào)用，并且可能會(huì)有一系列的重復(fù)計(jì)算，遞歸算法的執(zhí)行效率相對(duì)較低。當(dāng)某個(gè)遞歸算法能較方便地轉(zhuǎn)換成遞推算法時(shí)，通常按遞推算法編寫程序。例如上例計(jì)算斐波那契數(shù)列的第n項(xiàng)的函數(shù)fib(n)應(yīng)采用遞推算法，即從斐波那契數(shù)列的前兩項(xiàng)出發(fā)，逐次由前兩項(xiàng)計(jì)算出下一項(xiàng)，直至計(jì)算出要求的第n項(xiàng)?！締?wèn)題】組合問(wèn)題

10、問(wèn)題描述：找出從自然數(shù)1、2、n中任取r個(gè)數(shù)的所有組合。例如n=5，r=3的所有組合為：(1)5、4、3(2)5、4、2(3)5、4、1(4)5、3、2(5)5、3、1(6)5、2、1(7)4、3、2(8)4、3、1(9)4、2、1(10)3、2、1分析所列的10個(gè)組合，可以采用這樣的遞歸思想來(lái)考慮求組合函數(shù)的算法。設(shè)函數(shù)為void comb(int m,int k)為找出從自然數(shù)1、2、m中任取k個(gè)數(shù)的所有組合。當(dāng)組合的第一個(gè)數(shù)字選定時(shí)，其后的數(shù)字是從余下的m-1個(gè)數(shù)中取k-1數(shù)的組合。這就將求m個(gè)數(shù)中取k個(gè)數(shù)的組合問(wèn)題轉(zhuǎn)化成求m-1個(gè)數(shù)中取k-1個(gè)數(shù)的組合問(wèn)題。設(shè)函數(shù)引入工作數(shù)組a存放求出

11、的組合的數(shù)字，約定函數(shù)將確定的k個(gè)數(shù)字組合的第一個(gè)數(shù)字放在ak中，當(dāng)一個(gè)組合求出后，才將a中的一個(gè)組合輸出。第一個(gè)數(shù)可以是m、m-1、k，函數(shù)將確定組合的第一個(gè)數(shù)字放入數(shù)組后，有兩種可能的選擇，因還未去頂組合的其余元素，繼續(xù)遞歸去確定；或因已確定了組合的全部元素，輸出這個(gè)組合。細(xì)節(jié)見以下程序中的函數(shù)comb?！境绦颉?include stdio.h#define MAXN 100 int aMAXN；void comb(int m,int k)int i,j；for(i=m；i=k；i-)ak=i；if(k 1)comb(i-1,k-1)；elsefor(j=a0；j 0；j-)printf(

12、"%4d",aj)；printf("n")；void main()a0=3；comb(5,3)；3.回溯法回溯法也稱為試探法，該方法首先暫時(shí)放棄關(guān)于問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí)，就選擇下一個(gè)候選解；倘若當(dāng)前候選解除了還不滿足問(wèn)題規(guī)模要求外，滿足所有其他要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問(wèn)題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問(wèn)題的一個(gè)解。在回溯法中，放棄當(dāng)前候選解，尋找下一個(gè)候選解的過(guò)程稱為回溯。擴(kuò)大當(dāng)前候選解的規(guī)模，以繼續(xù)試探的過(guò)程稱為向前試探。【問(wèn)題】組合問(wèn)

13、題問(wèn)題描述：找出從自然數(shù)1，2，n中任取r個(gè)數(shù)的所有組合。采用回溯法找問(wèn)題的解，將找到的組合以從小到大順序存于a0，a1，ar-1中，組合的元素滿足以下性質(zhì)：(1)ai+1ai，后一個(gè)數(shù)字比前一個(gè)大；(2)ai-i=n-r+1。按回溯法的思想，找解過(guò)程可以敘述如下：首先放棄組合數(shù)個(gè)數(shù)為r的條件，候選組合從只有一個(gè)數(shù)字1開始。因該候選解滿足除問(wèn)題規(guī)模之外的全部條件，擴(kuò)大其規(guī)模，并使其滿足上述條件(1)，候選組合改為1，2。繼續(xù)這一過(guò)程，得到候選組合1，2，3。該候選解滿足包括問(wèn)題規(guī)模在內(nèi)的全部條件，因而是一個(gè)解。在該解的基礎(chǔ)上，選下一個(gè)候選解，因a2上的3調(diào)整為4，以及以后調(diào)整為5都滿足問(wèn)題的全

14、部要求，得到解1，2，4和1，2，5。由于對(duì)5不能再作調(diào)整，就要從a2回溯到a1，這時(shí)，a1=2，可以調(diào)整為3，并向前試探，得到解1，3，4。重復(fù)上述向前試探和向后回溯，直至要從a0再回溯時(shí)，說(shuō)明已經(jīng)找完問(wèn)題的全部解。按上述思想寫成程序如下：【程序】#define MAXN 100 int aMAXN；void comb(int m,int r)int i,j；i=0；ai=1；doif(ai-i=m-r+1if(i=r-1)for(j=0；j r；j+)printf("%4d",aj)；printf("n")；ai+；continue；elseif(i

15、=0)return；a-i+；while(1)main()comb(5,3)；4.貪婪法貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。例如平時(shí)購(gòu)物找錢時(shí)，為使找回的零錢的硬幣數(shù)最少，不考慮找零錢的所有各種發(fā)表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當(dāng)不足大面值幣種的金額時(shí)才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優(yōu)，是因?yàn)殂y行對(duì)其發(fā)行的硬幣種類和硬幣

16、面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪婪算法，應(yīng)找1個(gè)11單位面值的硬幣和4個(gè)1單位面值的硬幣，共找回5個(gè)硬幣。但最優(yōu)的解應(yīng)是3個(gè)5單位面值的硬幣?！締?wèn)題】裝箱問(wèn)題問(wèn)題描述：裝箱問(wèn)題可簡(jiǎn)述如下：設(shè)有編號(hào)為0、1、n-1的n種物品，體積分別為v0、v1、vn-1。將這n種物品裝到容量都為V的若干箱子里。約定這n種物品的體積均不超過(guò)V，即對(duì)于0i<n，有0<viV。不同的裝箱方案所需要的箱子數(shù)目可能不同。裝箱問(wèn)題要求使裝盡這n種物品的箱子數(shù)要少。若考察將n種物品的集合分劃成n個(gè)或小于n個(gè)物品的所有子集，最優(yōu)解就可以找到。但所有可能劃

17、分的總數(shù)太大。對(duì)適當(dāng)大的n，找出所有可能的劃分要花費(fèi)的時(shí)間是無(wú)法承受的。為此，對(duì)裝箱問(wèn)題采用非常簡(jiǎn)單的近似算法，即貪婪法。該算法依次將物品放到它第一個(gè)能放進(jìn)去的箱子中，該算法雖不能保證找到最優(yōu)解，但還是能找到非常好的解。不失一般性，設(shè)n件物品的體積是按從大到小排好序的，即有v0v1vn-1。如不滿足上述要求，只要先對(duì)這n件物品按它們的體積從大到小排序，然后按排序結(jié)果對(duì)物品重新編號(hào)即可。裝箱算法簡(jiǎn)單描述如下：輸入箱子的容積；輸入物品種數(shù)n；按體積從大到小順序，輸入各物品的體積；預(yù)置已用箱子鏈為空；預(yù)置已用箱子計(jì)數(shù)器box_count為0；for(i=0；i n；i+)從已用的第一只箱子開始順序?qū)?/p>

18、找能放入物品i的箱子j；if(已用箱子都不能再放物品i)另用一個(gè)箱子，并將物品i放入該箱子；box_count+；else將物品i放入箱子j；上述算法能求出需要的箱子數(shù)box_count，并能求出各箱子所裝物品。下面的例子說(shuō)明該算法不一定能找到最優(yōu)解，設(shè)有6種物品，它們的體積分別為：60、45、35、20、20和20單位體積，箱子的容積為100個(gè)單位體積。按上述算法計(jì)算，需三只箱子，各箱子所裝物品分別為：第一只箱子裝物品1、3；第二只箱子裝物品2、4、5；第三只箱子裝物品6。而最優(yōu)解為兩只箱子，分別裝物品1、4、5和2、3、6。若每只箱子所裝物品用鏈表來(lái)表示，鏈表首結(jié)點(diǎn)指針存于一個(gè)結(jié)構(gòu)中，結(jié)構(gòu)

19、記錄尚剩余的空間量和該箱子所裝物品鏈表的首指針。另將全部箱子的信息也構(gòu)成鏈表。以下是按以上算法編寫的程序?！境绦颉?include stdio.h#include stdlib.h typedef struct eleint vno；struct ele*link；ELE；typedef struct hnodeint remainder；ELE*head；Struct hnode*next；HNODE；void main()int n,i,box_count,box_volume,*a；HNODE*box_h,*box_t,*j；ELE*p,*q；Printf("輸入箱子容積n&q

20、uot;)；Scanf("%d",&box_volume)；Printf("輸入物品種數(shù)n")；Scanf("%d",&n)；A=(int*)malloc(sizeof(int)*n)；Printf("請(qǐng)按體積從大到小順序輸入各物品的體積：")；For(i=0；i n；i+)scanf("%d",a+i)；Box_h=box_t=NULL；Box_count=0；For(i=0；i n；i+)p=(ELE*)malloc(sizeof(ELE)；p-vno=i；for(j=box

21、_h；j！=NULL；j=j-next)if(j-remainder=ai)break；if(j=NULL)j=(HNODE*)malloc(sizeof(HNODE)；j-remainder=box_volume-ai；j-head=NULL；if(box_h=NULL)box_h=box_t=j；else box_t=boix_t-next=j；j-next=NULL；box_count+；else j-remainder-=ai；for(q=j-next；q！=NULL&&q-link！=NULL；q=q-link)；if(q=NULL)p-link=j-head；j-h

22、ead=p；elsep-link=NULL；q-link=p；printf("共使用了%d只箱子"，box_count)；printf("各箱子裝物品情況如下：")；for(j=box_h,i=1；j！=NULL；j=j-next,i+)printf("第%2d只箱子，還剩余容積%4d，所裝物品有；n",I,j-remainder)；for(p=j-head；p！=NULL；p=p-link)printf("%4d",p-vno+1)；printf("n")；5.分治法任何一個(gè)可以用計(jì)算機(jī)求解的

23、問(wèn)題所需的計(jì)算時(shí)間都與其規(guī)模N有關(guān)。問(wèn)題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。例如，對(duì)于n個(gè)元素的排序問(wèn)題，當(dāng)n=1時(shí)，不需任何計(jì)算；n=2時(shí)，只要作一次比較即可排好序；n=3時(shí)只要作3次比較即可，。而當(dāng)n較大時(shí)，問(wèn)題就不那么容易處理了。要想直接解決一個(gè)規(guī)模較大的問(wèn)題，有時(shí)是相當(dāng)困難的。分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。如果原問(wèn)題可分割成k個(gè)子問(wèn)題(1 kn)，且這些子問(wèn)題都可解，并可利用這些子問(wèn)題的解求出原問(wèn)題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了

24、方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：(1)該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；(2)該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；(3)利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；(4)該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子子問(wèn)題。上述的第一條特征是絕大多數(shù)問(wèn)題都可以滿足的，因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一

25、般是隨著問(wèn)題規(guī)模的增加而增加；第二條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用；第三條特征是關(guān)鍵，能否利用分治法完全取決于問(wèn)題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮貪心法或動(dòng)態(tài)規(guī)劃法。第四條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好。分治法在每一層遞歸上都有三個(gè)步驟：(1)分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；(2)解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題；(

26、3)合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。6.動(dòng)態(tài)規(guī)劃法經(jīng)常會(huì)遇到復(fù)雜問(wèn)題不能簡(jiǎn)單地分解成幾個(gè)子問(wèn)題，而會(huì)分解出一系列的子問(wèn)題。簡(jiǎn)單地采用把大問(wèn)題分解成子問(wèn)題，并綜合子問(wèn)題的解導(dǎo)出大問(wèn)題的解的方法，問(wèn)題求解耗時(shí)會(huì)按問(wèn)題規(guī)模呈冪級(jí)數(shù)增加。為了節(jié)約重復(fù)求相同子問(wèn)題的時(shí)間，引入一個(gè)數(shù)組，不管它們是否對(duì)最終解有用，把所有子問(wèn)題的解存于該數(shù)組中，這就是動(dòng)態(tài)規(guī)劃法所采用的基本方法。以下先用實(shí)例說(shuō)明動(dòng)態(tài)規(guī)劃方法的使用。【問(wèn)題】求兩字符序列的最長(zhǎng)公共字符子序列問(wèn)題描述：字符序列的子序列是指從給定字符序列中隨意地(不一定連續(xù))去掉若干個(gè)字符(可能一個(gè)也不去掉)后所形成的字符序列。令給定的字符序列X="

27、;x0，x1，xm-1"，序列Y="y0，y1，yk-1"是X的子序列，存在X的一個(gè)嚴(yán)格遞增下標(biāo)序列i0，i1，ik-1，使得對(duì)所有的j=0，1，k-1，有xij=yj。例如，X="ABCBDAB"，Y="BCDB"是X的一個(gè)子序列?？紤]最長(zhǎng)公共子序列問(wèn)題如何分解成子問(wèn)題，設(shè)A="a0，a1，am-1"，B="b0，b1，bm-1"，并Z="z0，z1，zk-1"為它們的最長(zhǎng)公共子序列。不難證明有以下性質(zhì)：(1)如果am-1=bn-1，則zk-1=am-1=bn-1

28、，且"z0，z1，zk-2"是"a0，a1，am-2"和"b0，b1，bn-2"的一個(gè)最長(zhǎng)公共子序列；(2)如果am-1！=bn-1，則若zk-1！=am-1，蘊(yùn)涵"z0，z1，zk-1"是"a0，a1，am-2"和"b0，b1，bn-1"的一個(gè)最長(zhǎng)公共子序列；(3)如果am-1！=bn-1，則若zk-1！=bn-1，蘊(yùn)涵"z0，z1，zk-1"是"a0，a1，am-1"和"b0，b1，bn-2"的一個(gè)最長(zhǎng)公共子序列

29、。這樣，在找A和B的公共子序列時(shí)，如有am-1=bn-1，則進(jìn)一步解決一個(gè)子問(wèn)題，找"a0，a1，am-2"和"b0，b1，bm-2"的一個(gè)最長(zhǎng)公共子序列；如果am-1！=bn-1，則要解決兩個(gè)子問(wèn)題，找出"a0，a1，am-2"和"b0，b1，bn-1"的一個(gè)最長(zhǎng)公共子序列和找出"a0，a1，am-1"和"b0，b1，bn-2"的一個(gè)最長(zhǎng)公共子序列，再取兩者中較長(zhǎng)者作為A和B的最長(zhǎng)公共子序列。代碼如下：#include stdio.h#include string.h#de

30、fine N100 char aN,bN,strN；int lcs_len(char*a,char*b,int cN)int m=strlen(a),n=strlen(b),i,j；for(i=0；i=m；i+)ci0=0；for(i=0；i=n；i+)c0i=0；for(i=1；i=m；i+)for(j=1；j=m；j+)if(ai-1=bj-1)cij=ci-1j-1+1；else if(ci-1j=cij-1)cij=ci-1j；else cij=cij-1；return cmn；char*buile_lcs(char s,char*a,char*b)int k,i=strlen(a),

31、j=strlen(b)；k=lcs_len(a,b,c)；sk='message'；while(k 0)if(cij=ci-1j)i-；else if(cij=cij-1)j-；elses-k=ai-1；i-；j-；return s；void main()printf("Enter two string(%d)！n",N)；scanf("%s%s",a,b)；printf("LCS=%sn",build_lcs(str,a,b)；7.迭代法迭代法是用于求方程或方程組近似根的一種常用的算法設(shè)計(jì)方法。設(shè)方程為f(x)=0，

32、用某種數(shù)學(xué)方法導(dǎo)出等價(jià)的形式x=g(x)，然后按以下步驟執(zhí)行：(1)選一個(gè)方程的近似根，賦給變量x0；(2)將x0的值保存于變量x1，然后計(jì)算g(x1)，并將結(jié)果存于變量x0；(3)當(dāng)x0與x1的差的絕對(duì)值還小于指定的精度要求時(shí)，重復(fù)步驟(2)的計(jì)算。若方程有根，并且用上述方法計(jì)算出來(lái)的近似根序列收斂，則按上述方法求得的x0就認(rèn)為是方程的根。上述算法用C程序的形式表示為：程序如下：【算法】迭代法求方程組的根for(i=0；i n；i+)xi=初始近似根；dofor(i=0；i n；i+)yi=xi；for(i=0；i n；i+)xi=gi(X)；for(delta=0.0,i=0；i n；i+

33、)if(fabs(yi-xi)delta)delta=fabs(yi-xi)；while(delta Epsilon)；for(i=0；i n；i+)printf("變量x%d的近似根是%f"，I，xi)；printf("n")；具體使用迭代法求根時(shí)應(yīng)注意以下兩種可能發(fā)生的情況：(1)如果方程無(wú)解，算法求出的近似根序列就不會(huì)收斂，迭代過(guò)程會(huì)變成死循環(huán)，因此在使用迭代算法前應(yīng)先考察方程是否有解，并在程序中對(duì)迭代的次數(shù)給予限制；(2)方程雖然有解，但迭代公式選擇不當(dāng)，或迭代的初始近似根選擇不合理，也會(huì)導(dǎo)致迭代失敗。8.窮舉搜索法窮舉搜索法是對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問(wèn)題的解?！締?wèn)題】將A、B、C、D、E、F這六個(gè)變量排成如圖所示的三