算法分析與設(shè)計實驗報告

《算法分析與設(shè)計實驗報告》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、項目序號1項目名稱分治法實驗成績小標(biāo)題找最大值和最小值1、方法思想分治法是把規(guī)模大的問題，分割成n個形式相同規(guī)模一定或不可再分的子問題，遞歸地解決每個子問題，再把子問題的結(jié)果匯總，合并得到原問題的解。分治法在每一層遞歸上由三個步驟組成：(1)劃分(divide)：將原問題分解為若干規(guī)模較小、相互獨立、與原問題形式相同的子問題。(2)解決(conquer)：若子問題規(guī)模較小，則直接求解；否則遞歸求解各子問題。(3)合并(combine)：將各子問題的解合并為原問題的解。2、問題描述我們將分治策略用于此問題

2、，每次將問題分成大致相等的兩部分，分別在這兩部分中找出最大值與最小值，再將這兩個子問題的解組合成原問題的解，就可得到該問題的分治算法。3、算法描述REC-MAXMIN(i，j，fmax，fmin)1ifi=j2thenfmax←fmin←A［i］3ifi=(j-1)4thenifA［i］>A［j］5thenfmax←A［i］6fmin←A［j］elsefmax←A［j］8fmin←A［i］9elsemid←［(i+j)/2］10REC-MAXMIN(i，mid，gmax，gmin)11

3、REC-MAXMIN(mid+1，j，hmax，hmin)12fmax←max{gmax，hmax}13fmin←min{gmin，hmin}4、程序清單#includevoidFZFa(inti,intj,int&max,int&min,inta[]){11if(i==j){max=a[i];min=a[j];}elseif(i==(j-1)){if(a[i]>a[j]){max=a[i];min=a[j];}else{max=a[j];min=a[i];}}else{intm

4、idd=(i+j)/2;intmax1=0,min1=0,max2=0,min2=0;FZFa(i,midd,max1,min1,a);FZFa(midd+1,j,max2,min2,a);if(max1>max2)max=max1;elsemax=max2;if(min1

5、"<

6、到多項式時間算法。為了達(dá)到這個目的，可以用一個表來記錄所有已解決的子問題的答案。不過孩子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃的基本思想。2、問題描述最長公共子序列為題：給定兩個序列X={x1,x2,x3……xm}和Y={y1,y2,y3……yn},找出X和Y的最長公共子序列。3、算法描述LCSLENGTH(X,Y)1m←length［X］2n←length［Y］3fori←1tom4dol［i,0］←05forj←1ton6dol［0,j］←07fori←

7、1tom8doforj←1ton119doifxi=yj10thenl［i,j］←l［i-1,j-1］+1b［i,j］←112elseifl［i-1,j］←l［i,j-1］13thenl［i,j］←l［i-1,j］14b［i,j］←215elsel［i,j］←l［i,j-1］16b［i,j］←317returnlandb4、程序清單#includeintlcsleng(charx[],chary[],inta[10][10],intn,intm){intc[10]

8、[10];inti,j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i];for(i=1;i<=n;i++)for(j=1;j<=m;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;a[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];a[i][j]=2;}els