算法分析與設計實驗報告

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

1、實驗報告班級：學號：姓名：總成績：課程名稱：算法分析與設計實訓實驗項目：1、分治法實驗2、動態(tài)規(guī)劃法實驗3、貪心法實驗4、回溯法實驗5、分枝限界法實驗計算機學院工業(yè)中心202實驗室二〇一〇年6月21日20項目序號1項目名稱分治法實驗成績小標題找最大值和最小值1、方法思想分治法是把規(guī)模大的問題，分割成n個形式相同規(guī)模一定或不可再分的子問題，遞歸地解決每個子問題，再把子問題的結(jié)果匯總，合并得到原問題的解。分治法在每一層遞歸上由三個步驟組成：(1)劃分(divide)：將原問題分解為若干規(guī)模較小、相互獨立、與原問題形式相同的子

2、問題。(2)解決(conquer)：若子問題規(guī)模較小，則直接求解；否則遞歸求解各子問題。(3)合并(combine)：將各子問題的解合并為原問題的解。2、問題描述我們將分治策略用于此問題，每次將問題分成大致相等的兩部分，分別在這兩部分中找出最大值與最小值，再將這兩個子問題的解組合成原問題的解，就可得到該問題的分治算法。3、算法描述REC-MAXMIN(i，j，fmax，fmin)1ifi=j2thenfmax←fmin←A［i］3ifi=(j-1)4thenifA［i］>A［j］5thenfmax←A［i］

3、6fmin←A［j］elsefmax←A［j］8fmin←A［i］9elsemid←［(i+j)/2］10REC-MAXMIN(i，mid，gmax，gmin)11REC-MAXMIN(mid+1，j，hmax，hmin)12fmax←max{gmax，hmax}13fmin←min{gmin，hmin}4、程序清單#includevoidFZFa(inti,intj,int&max,int&min,inta[]){20if(i==j){max=a[i];min=a[j];}elseif

4、(i==(j-1)){if(a[i]>a[j]){max=a[i];min=a[j];}else{max=a[j];min=a[i];}}else{intmidd=(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、,4};intmax,min;FZFa(0,1,max,min,t);cout<<"最大值："<

6、解時，有些子問題被重復計算了許多次。如果能夠保存已解決的子問題的答案，而再需要時再找出已求的答案，就可以避免大量重復計算，從而得到多項式時間算法。為了達到這個目的，可以用一個表來記錄所有已解決的子問題的答案。不過孩子問題以后是否被用到，只要它被計算過，就將其結(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

7、［Y］3fori←1tom4dol［i,0］←05forj←1ton6dol［0,j］←07fori←1tom8doforj←1ton9doifxi=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(ch

8、arx[],chary[],inta[10][10],intn,intm){intc[10][10];inti,j;20for(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[