算法分析与设计实验报告

《算法分析与设计实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告班级：学号：姓名：总成绩：课程名称：算法分析与设计实训实验项目：1、分治法实验2、动态规划法实验3、贪心法实验4、回溯法实验5、分枝限界法实验计算机学院工业中心202实验室二〇一〇年6月21日20项目序号1项目名称分治法实验成绩小标题找最大值和最小值1、方法思想分治法是把规模大的问题，分割成n个形式相同规模一定或不可再分的子问题，递归地解决每个子问题，再把子问题的结果汇总，合并得到原问题的解。分治法在每一层递归上由三个步骤组成：(1)划分(divide)：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子

2、问题。(2)解决(conquer)：若子问题规模较小，则直接求解；否则递归求解各子问题。(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、解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而再需要时再找出已求的答案，就可以避免大量重复计算，从而得到多项式时间算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不过孩子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思想。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[