算法分析与设计——实验报告

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

1、课程名称：算法分析与设计学号：08220429姓名：王洪朋专业班级：（非师范）计算机科学与技术081学院：数理与信息工程学院指导老师：宋炯数理与信息工程学院实验一递归与分治策略一、实验目的1、熟练掌握递归与分治策略的思想并应用其解决实际问题。2、利用递归与分治策略的思想解决Gray码问题。二、实验要求Gray码是一个长度为2n的序列。序列中无相同元素，每个元素都是长度为n位的串，相邻元素恰好只有1位相同。用分治策略设计一个算法对任意的n构造相应的Gray码。三、算法实现#includeusingnamespacestd;voidprint(i

2、nta[],intlength);voidgray(intn,inta[],intlength);intmain(void){intn;cout<<"Pleaseinputn:";cin>>n;inta[n];for(inti=0;i=0;i--){cout<

3、=0){a[n]=1-a[n];print(a,length);}else{gray(n-1,a,length);a[n]=1-a[n];print(a,length);gray(n-1,a,length);}}实验运行结果：四、实验总结按照分治策略设计，利用递归方法构造Grey码。长度为n的Grey码字符串，前半部分只要在长度为n-1的Grey码前添0就可；后半部分令第二位为1，后几位为前半部分的逆顺序就可。实验二动态规划一、实验目的1、掌握动态规划的基本思想并应用其解决实际问题。2、利用动态规划的基本思想解决N堆石子合并问题。二、实验要求在一个圆形操场的四周

4、摆放N堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分，并分析算法的计算复杂性。三、算法实现#include#include#defineN500#defineoo2000000000#defineMIN(a,b)(a)<(b)?(a):(b)#defineMAX(a,b)(a)>(b)?(a):(b)usingnamespacestd;typedefstruct{intc,d;}Node;in

5、tn;intv[N];//每堆石头的个数intsave[N];//输出最优解的具体合并需要随时改变v的值，所以为了同时输出最小，最大的合并，在完成一个任务之后需要回溯Nodef[N][N];//f[i][j]存储最优解，同时存储合并线索intsum[N][N];//sum[i][j]表示从第i堆起，顺时针数j堆的石子总数//递归打印子序列f[i][j]的合并过程voidPrint(inti,intj){intk,x;if(j!=1){Print(i,f[i][j].d);x=(i+f[i][j].d-1)%n+1;Print(x,j-f[i][j].d);for

6、(k=1;k<=n;k++)if(v[k]>0){if(i==k

7、

8、x==k)cout<<"*"<

9、推含2堆，3堆...n堆石子的各子序列的合并方案for(i=1;i<=n;i++){t=sum[i][j];if(flag==0)f[i][j].c=oo;//求最小得分，那么需要初始化为ooelsef[i][j].c=0;//求最大得分，那么需要初始化为0for(k=1;k<=j-1;k++){x=(i+k-1)%n+1;if((flag==0&&f[i][k].c+f[x][j-k].c+t

10、

11、(flag!=0&&f[i][k].c+f[x][j-k].c+t>f[i][j].c)){f[i][j].c=f[i][k].c+f[x][j

12、-k].c+t;f[i]