资源描述:
《算法分析与设计实验报告》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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=j2thenfmax←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(min15、,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、算法描述LCSLENGTH(X,Y)1m←length[X]2n←length
7、[Y]3fori←1tom4dol[i,0]←05forj←1ton6dol[0,j]←07fori←1tom8doforj←1ton9doifxi=yj10thenl[i,j]←l[i-1,j-1]+1b[i,j]←112elseifl[i-1,j]←l[i,j-1]13thenl[i,j]←l[i-1,j]14b[i,j]←215elsel[i,j]←l[i,j-1]16b[i,j]←317returnlandb4、程序清单#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[