《算法设计与分析》上机实验报告(3)
- 格式:doc
- 大小:606.90 KB
- 文档页数:17
算法设计与分析报告学生姓名学号专业班级指导教师完成时间目录一、课程内容 (3)二、算法分析 (3)1、分治法 (3)(1)分治法核心思想 (3)(2)MaxMin算法分析 (3)2、动态规划 (4)(1)动态规划核心思想 (4)(2)矩阵连乘算法分析 (5)3、贪心法 (5)(1)贪心法核心思想 (5)(2)背包问题算法分析 (6)(3)装载问题算法分析 (6)4、回溯法 (7)(1)回溯法核心思想 (7)(2)N皇后问题非递归算法分析 (7)(3)N皇后问题递归算法分析 (8)三、例子说明 (9)1、MaxMin问题 (9)2、矩阵连乘 (9)3、背包问题 (10)4、最优装载 (10)5、N皇后问题(非递归) (11)6、N皇后问题(递归) (11)四、心得体会 (11)五、算法对应的例子代码 (12)1、求最大值最小值 (12)2、矩阵连乘问题 (13)3、背包问题 (14)4、装载问题 (17)5、N皇后问题(非递归) (18)6、N皇后问题(递归) (20)一、课程内容1、分治法,求最大值最小值,maxmin算法;2、动态规划,矩阵连乘,求最少连乘次数;3、贪心法,1)背包问题,2)装载问题;4、回溯法,N皇后问题的循环结构算法和递归结构算法。
二、算法分析1、分治法(1)分治法核心思想当要求解一个输入规模为n,且n的取值相当大的问题时,直接求解往往是非常困难的。
如果问题可以将n个输入分成k个不同子集合,得到k个不同的可独立求解的子问题,其中1<k≤n,而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出。
那末,这类问题可以用分治法求解。
分治法的核心技术1)子问题的划分技术。
2)递归技术。
反复使用分治策略将这些子问题分成更小的同类型子问题,直至产生出不用进一步细分就可求解的子问题。
3)合并技术。
(2)MaxMin算法分析问题:在含有n个不同元素的集合中同时找出它的最大和最小元素。
算法设计与分析实验报告棋盘覆盖问题贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称:算法设计与分析班级:信计101班实验日期:2013-9-30 姓名: 张胜学号:1007010162 指导教师:程欣宇实验序号:一实验成绩: 一、实验名称分治算法实验 - 棋盘覆盖问题二、实验目的及要求1、熟悉递归算法编写;2、理解分治算法的特点;3、掌握分治算法的基本结构。
三、实验环境Visual C++四、实验内容根据教材上分析的棋盘覆盖问题的求解思路,进行验证性实验;要求完成棋盘覆盖问题的输入、分治求解、输出。
有余力的同学尝试消去递归求解。
五、算法描述及实验步骤分治算法原理:分治算法将大的分解成形状结构相同的子问题,并且不断递归地分解,直到子问题规模小到可以直接求解。
棋盘覆盖问题描述:在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格,想要求利用四种L型骨牌(每个骨牌可覆盖三个方格)不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。
实验步骤:1、定义用于输入和输出的数据结构;2、完成分治算法的编写;3、测试记录结构;4、有余力的同学尝试不改变输入输出结构,将递归消除,并说明能否不用栈,直接消除递归,为什么,六、调试过程及实验结果实验运行结果:七、总结通过本次实验,我更深的理解了递归和分治策略。
代码是书上的算法,加上主函数就行了,用的是C语言编写,很长时间没用了,感觉有点生疏。
实验结果有点问题,就是覆盖棋盘时,并不是按照1,2,3….的字符顺序,而是按照很乱的顺序输出字符,这个我不知道怎么解决,就没解决。
八、附录#include "stdio.h"#include "conio.h"int board[8][8] ={{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0 ,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}};int tile=0;void chessBoard(int tr, int tc, int dr, intdc, int size){int t=tile++,s=size/2;if (size==1) return;if (dr<tr+s&&dc<tc+s)chessBoard(tr,tc,dr,dc,s);else {board[tr+s-1][tc+s-1]=t;chessBoard(tr,tc,tr+s-1,tc+s-1,s);}if(dr <tr+s && dc >= tc+s)chessBoard(tr,tc+s,dr,dc,s);else {board[tr+s-1][tc+s]=t;chessBoard(tr,tc+s,tr+s-1,tc+s,s);} if(dr >= tr+s&&dc<tc+s)chessBoard(tr+s,tc,dr, dc,s);else {board[tr+s][tc+s-1]=t;chessBoard(tr+s,tc,tr+s,tc+s-1,s);} if(dr >= tr+s &&dc>=tc+s) chessBoard(tr+s,tc+s,dr,dc,s);else {board[tr+s][tc+s]=t;chessBoard(tr+s,tc+s,tr+s,tc+s,s);} }main(){int i ,j;chessBoard(0,0,5,5,8);for(i=0;i <8;i++){for( j=0;j <8;j++) {if(board[i][j]<10)printf("0");printf("%d",board[i][j]);printf(" ");}printf( "\n"); } getchar();}。
算法设计与分析第三章程序作业源程序代码1.最长公共子序列#include<stdio.h>#include<stdlib.h>#define N 1000int e[N][N],f[N][N];void LCSLength(int m,int n,char *x,char *y,int c[][N],int b[][N])//构造数组b[i][j]{int i,j;for (i=1; i<=m;i++)c[i][0]=0; //初始化, Y[j]为空时for (i=1;i<=n;i++)c[0][i]=0; //初始化,X[i]为空时for (i=1;i<=m;i++) //两重循环,自下而上,// 计算子问题{X(i), Y(j)}for (j=1;j<=n;j++){if(x[i]==y[j]){ //情况1c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}else if(c[i-1][j]>=c[i][j-1]){ //情况2c[i][j]=c[i-1][j];b[i][j]=2;}else //情况3{c[i][j]=c[i][j-1];b[i][j]=3;}}}void LCS(int i,int j,char *x,int b[][N]){if (i==0||j==0)return;if (b[i][j]==1){LCS(i-1,j-1,x,b);printf("%c",x[i]);/*第1种情况下,X(i)和Y(j)的最长公共子序列由X(i-1)和Y(j-1)的解LCS(i-1, j-1, x, b),加上位于最后的X[i]组成*/}else if(b[i][j]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b); //其它2种情况下,原问题解等于子问题解}main(){char A[N],B[N],C[N],D[N];int a=1,b=1,c=1,d=1;char ch;int i;FILE * fp;if((fp=fopen("最长公共子序列输入数据.txt","r"))==NULL)//打开文件失败printf("Can't open file ");else{//读取文件内容ch=fgetc(fp);ch=fgetc(fp);ch=fgetc(fp);ch=fgetc(fp);ch=fgetc(fp);while(ch!='B'&&ch!=EOF) {A[a]=ch;a++;ch=fgetc(fp);while(ch=='\n')ch=fgetc(fp);}a--;ch=fgetc(fp);ch=fgetc(fp);ch=fgetc(fp);ch=fgetc(fp);while(ch!='C'&&ch!=EOF) {B[b]=ch;b++;ch=fgetc(fp);while(ch=='\n')ch=fgetc(fp);}b--;ch=fgetc(fp);ch=fgetc(fp);ch=fgetc(fp);ch=fgetc(fp);while(ch!='D'&&ch!=EOF) {C[c]=ch;c++;ch=fgetc(fp);while(ch=='\n')ch=fgetc(fp);}c--;ch=fgetc(fp);ch=fgetc(fp);ch=fgetc(fp);ch=fgetc(fp);while(ch!=EOF){D[d]=ch;d++;ch=fgetc(fp);while(ch=='\n')ch=fgetc(fp);}d--;}fclose(fp);printf("文件读取完成\n");/* for(i=0;i<=a;i++)printf("%c",A[i]);printf("\n");for(i=0;i<=b;i++)printf("%c",B[i]);printf("\n");for(i=0;i<=c;i++)printf("%c",C[i]);printf("\n");for(i=0;i<=d;i++)printf("%c",D[i]);printf("\n"); */printf("\n\n\nA和B的最长公共子序列为:\n");LCSLength(a,b,A,B,e,f);LCS(a,b,A,f);printf("\n\n\nC和D的最长公共子序列为:\n");LCSLength(c,d,C,D,e,f);LCS(c,d,C,f);printf("\n\n\nA和D的最长公共子序列为:\n");LCSLength(a,d,A,D,e,f);LCS(a,d,A,f);system("pause");return 0;}2.最大子段和#include<stdio.h>#include<stdlib.h>#define N 400void MaxSum(int n,int *a){int sum=0,b=0;int i,x1=0,y1=0,x=0,y=0;for(i=1;i<=n;i++){if (b>0){b+=a[i];y1=i;}else{b=a[i];x1=i;}if(b>sum){sum=b;x=x1;y=y1;}}printf("\n该序列的最大子段和的位置为从第%d个到第%d个",x+1,y+1);printf("\n该序列的和最大子段为:\n");for(i=x;i<=y;i++)printf("%d ",a[i]);printf("\n它们的和为%d \n",sum);}main(){int A[N],B[N];int a=0,b=0;int i;FILE *fp1,*fp2;if((fp1=fopen("最大子段和输入数据-序列1.txt","r"))==NULL)//打开文件失败printf("Can't open file1 ");else //读取文件内容for(i=0;!feof(fp1);i++)fscanf(fp1,"%d\n",&A[i]);a=i-1;}if((fp2=fopen("最大子段和输入数据-序列2.txt","r"))==NULL)//打开文件失败printf("Can't open file2 ");else{for(i=0;!feof(fp2);i++)fscanf(fp2,"%d\n",&B[i]);b=i-1;}fclose(fp1);fclose(fp1);printf("文件读取成功!!!\n\n\n");printf("对于最大子段和输入数据-序列1 ");MaxSum(a,A);//计算最大子段和printf("\n\n对于最大子段和输入数据-序列2 ");MaxSum(b,B);// for(i=0;i<=b;i++)// printf("%d ",B[i]);system("pause");return 0;}3.凸多边形最优三角剖分#include<stdio.h>#include<stdlib.h>#include<math.h>#define N 30#define EARTH_RADIUS 6378.137struct Base{//基站结构体int ENODEBID;//基站标识float LONGITUDE;//基站经度float LATITUDE;//基站纬度int NUM;//基站k-dist距离};void readfile(struct Base * base,int n) //读取文件函数{FILE * fp;int i=0;if(n==21)fp=fopen("21个基站凸多边形数据.csv","rb");elsefp=fopen("29个基站凸多边形数据.csv","rb");if(fp==NULL)//打开文件失败printf("Can't open file ");else{while(EOF!=fscanf(fp,"%d,%f,%f,%d",&base[i].ENODEBID,&base[i].LO NGITUDE,&base[i].LATITUDE,&base[i].NUM)){//将数据读入结构体数组i++;//printf("%d\n",i);}// printf("文件读入成功!!!\n\n\n");fclose(fp);}float rad(float LatOrLon){return LatOrLon * 3.14/180.0;}float distance(struct Base * base,int a,int b)//求两个基站间的距离{float s;float radLat1,radLat2,radlng1,radlng2;radLat1 = rad(base[a].LATITUDE);radLat2 = rad(base[b].LATITUDE);radlng1 = rad(base[a].LONGITUDE);radlng2 = rad(base[b].LONGITUDE);//利用正弦余弦公式求距离if(radLat1==radLat2&&radlng1==radlng2)s=0;elses=acos(cos(radLat1)*cos(radLat2)*cos(radlng1-radlng2)+sin(radLat1)*s in(radLat2));s = s * EARTH_RADIUS;s=round(s*1000);}return s;}float weight(struct Base * base,int a,int b,int c){float s,s1,s2,s3;s1=distance(base,a,b);s2=distance(base,b,c);s3=distance(base,a,c);//s=distance(base,a,b)+distance(base,b,c)+distance(base,a,c);s=s1+s2+s3;return s;}float MinWeightTriangulation(struct Base * base,int n,float t[][N],int s[][N]){int i,j,r,k;float u=0;for(i=1;i<=n;i++)t[i][i]=0;for(r=2;r<=n;r++) //r为当前计算的链长(子问题规模)for(i=1;i<=n-r+1;i++)//n-r+1为最后一个r链的前边界{j=i+r-1;//计算前边界为r,链长为r的链的后边界t[i][j]=t[i+1][j]+weight(base,i-1,i,j);//将链ij划分为A(i) * ( A[i+1:j] )这里实际上就是k=is[i][j]=i;for (k=i+1;k<i+r-1;k++) //将链ij划分为( A[i:k] )* (A[k+1:j]){u=t[i][k]+t[k+1][j]+weight(base,i-1,k,j);if(u<t[i][j]){t[i][j]=u;s[i][j]=k;}}}return t[1][n];}void Traceback(int i,int j,int s[][N]){if(i==j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);printf("三角剖分顶点:V%d , V%d , V%d\n",i-1,j,s[i][j]); }main(){int i;float t[N][N];int s[N][N];struct Base base21[N];//结构体(N宏定义)struct Base base29[N];//结构体(N宏定义)readfile(base21,21);//将数据从文件中读到结构体中readfile(base29,29);//将数据从文件中读到结构体中printf("文件读入成功!!!\n\n\n");// for(i=0;i<=28;i++)//printf("%6d %.3f %.5f %d\n",base29[i].ENODEBID,base29[i].LONGITU DE,base29[i].LATITUDE,base29[i].NUM);printf("凸21多边形的最优三角剖分值为%f",MinWeightTriangulation(base21,20,t,s));printf("最优三角剖分结构为:\n");Traceback(1,20,s); //s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置printf("凸29多边形的最优三角剖分值为%f",MinWeightTriangulation(base29,28,t,s));printf("最优三角剖分结构为:\n");Traceback(1,28,s); //s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置system("pause");return 0;}4.01背包问题#include<stdio.h>#include<stdlib.h>#define N 100struct Goods{int weight;//物品重量int value;//物品价值};int knapsack(struct Goods *goods,int bag,int number,int p[][2],int head[]){int left=0,right=0,next=1,i,j,k,m,y;p[0][0]=0;p[0][1]=0;head[number+1]=0;head[number]=1;for(i=number;i>=1;i--){k=left;for(j=left;j<=right&&p[j][0]+goods[i-1].weight<=bag;j++){ y=p[j][0]+goods[i-1].weight;m=p[j][1]+goods[i-1].value;while(k<=right&&p[k][0]<y){p[next][0]=p[k][0];p[next][1]=p[k][1];next++;k++;}if(k<=right&&p[k][0]==y){if(m<p[k][1]){m=p[k][1];}k++;}if(m>p[next-1][1]){p[next][0]=y;p[next][1]=m;next++;}while(k<=right&&p[k][1]<=p[next-1][1]){k++;}}while(k<=right){p[next][0]=p[k][0];p[next][1]=p[k][1];next++;k++;}left=right+1;right=next-1;head[i-1]=next;}return next;}void traceback(struct Goods *goods,int number,int head[],int p[][2],int x[]){int j=p[head[0]-1][0],m=p[head[0]-1][1];int i,k,a;for(i=1;i<=number;i++){x[i]=0;a=1;// for(k=3450;k<=head[i]-1&&a==1;k++)for(k=head[i+1];k<=head[i]-1&&a==1;k++){if(p[k][0]+goods[i-1].weight==j&&p[k][1]+goods[i-1].value==m){x[i]=1;j=p[k][0];m=p[k][1];a=0;}}}}main(){int bag1,bag2;//背包容量int number1,number2;//物品数目int i,n;int p[20000][2];int h[N],x[N];struct Goods goods1[N],goods2[N];FILE *fp;char ch='0';if((fp=fopen("附件4.背包问题输入数据.txt","r"))==NULL)//打开文件失败printf("Can't open file ");else //读入背包和物品信息{fseek(fp,18,SEEK_CUR);fscanf(fp,"%d",&bag1);//背包1容量fseek(fp,18,SEEK_CUR);ch='0';for(i=0;ch!='\n';i++){fscanf(fp,"%d",&goods1[i].weight);//物品重量}number1=i;ch='0';fseek(fp,14,SEEK_CUR);for(i=0;ch!='\n'&&ch!=EOF;i++){fscanf(fp,"%d",&goods1[i].value);//物品价值ch=fgetc(fp);}if(number1!=i){printf("读取数据出错,程序将退出!\n");system("pause");}fseek(fp,22,SEEK_CUR);fscanf(fp,"%d",&bag2);//背包1容量fseek(fp,18,SEEK_CUR);ch='0';for(i=0;ch!='\n';i++){fscanf(fp,"%d",&goods2[i].weight);//物品重量}number2=i;ch='0';fseek(fp,14,SEEK_CUR);for(i=0;ch!='\n'&&ch!=EOF;i++){fscanf(fp,"%d",&goods2[i].value);//物品价值ch=fgetc(fp);}if(number2!=i){printf("读取数据出错,程序将退出!\n");system("pause");}}printf("文件读取成功!!!\n");/*打印文件的信息*/printf("\n\n第一组背包数据:\n");printf("背包容量:%d 物品数量:%d\n物品重量:\n",bag1,number1);for(i=0;i<number1;i++)printf("%d ",goods1[i].weight);printf("\n物品价值:\n");for(i=0;i<number1;i++)printf("%d ",goods1[i].value);printf("\n\n第二组背包数据:\n");printf("背包容量:%d 物品数量:%d\n物品重量:\n",bag2,number2);for(i=0;i<number2;i++)printf("%d ",goods2[i].weight);printf("\n物品价值:\n");for(i=0;i<number2;i++)printf("%d ",goods2[i].value);n=knapsack(goods1,bag1,number1,p,h);traceback(goods1,number1,h,p,x); //确定放入的物品//打印结果printf("\n\n第一组:\n背包重量为:%d 背包价值为:%d\n",p[n-1][0],p[n-1][1]);printf("放入的物品为:\n");for(i=1;i<number1;i++)if(x[i]==1)printf("物品%-2d 重量%-2d 价值%d\n",i,goods1[i-1].weight,goods1[i-1].value);//第二组数据n=knapsack(goods2,bag2,number2,p,h);traceback(goods2,number2,h,p,x);printf("\n\n第二组:\n背包重量为:%d 背包价值为:%d\n",p[n-1][0],p[n-1][1]);printf("放入的物品为:\n");for(i=1;i<number2;i++)if(x[i]==1)printf("物品%-2d 重量%-2d 价值%d\n",i,goods2[i-1].weight,goods2[i-1].value);system("pause");return 0;}运行结果1.最长公共子序列2.最大子段和3.凸多边形最优三角剖分4.01背包问题。
算法上机实验报告课程实验报告课程名称:算法设计与分析专业班级:信息安全1303学号:U201315182姓名:刘⽴鹏指导教师:王多强报告⽇期:2015-6-16计算机科学与技术学院⽬录⽬录 (2)实验⼀最近点对问题 (1)1.1实验内容与要求 (1)1.2算法设计 (1)1.3 实验结果与分析 (2)1.4编程技术与⽅法 (3)1.5 源程序及注释 (3)实验⼆⼤整数乘法 (8)2.1实验内容与要求 (8)2.2算法设计 (9)2.3 实验结果与分析 (12)2.4编程技术与⽅法 (12)2.5 源程序及注释 (12)实验三单源点 (14)3.1实验内容与要求 (14)3.2算法设计 (14)3.3 实验结果与分析 (14)3.4编程技术与⽅法 (16)3.5 源程序及注释 (16)实验四最优⼆分检索树 (19)4.1实验内容与要求 (19)4.2算法设计 (19)4.3实验结果与分析 (20)六、参考书⽬ (27)实验⼀最近点对问题1.1 实验内容与要求已知平⾯上分布着点集P 中的n 个点p 1,p 2,...p n ,点i 的坐标记为(x i ,y i ),1≤i≤n 。
两点之间的距离取其欧式距离,记为22)()(),(j i j i j i y y x x p p d -+-=问题:找出⼀对距离最近的点。
注:允许两个点位于同⼀个位置,此时两点之间的距离为0 要求:⽤分治法实现最近点对的问题。
1.2 算法设计(1)⾸先将所有的点按照x 坐标排序。
排序过程需要O(nlogn)的时间,不会从整体上增加时间复杂度的数量级。
(2)划分:由于点已经按x 坐标排序,所以空间上可以“想象” 画⼀条垂线,作为分割线,将平⾯上的点集分成左、右两半P L 和P R 。
如下图所⽰:d Ld CdR分割线P L P R记, d L:P L中的最近点对距离;d R:P R中的最近点对距离;d C:跨越分割线的最近点对距离。
华北电力大学实验报告||实验名称算法设计与分析实验课程名称算法设计与分析||专业班级:计科1203 学生姓名:学号:成绩:指导教师:牛为华实验日期:2014年10月实验一、矩阵连乘一、实验目的及要求1、了解并掌握动态规划算法解矩阵连乘问题的原理;2、通过上机实验,对矩阵连乘的知识进行巩固;3、用程序实现矩阵连乘。
二、实验原理1、两个矩阵相乘,第一个矩阵的列数=第二个矩阵的行数;2、三个矩阵相乘时:A1 * A2 * A3 =((A1 * A2 ) * A3 )A1 * A2 * A3 =(A1 * ( A2 * A3 ))不同的运算顺序,所需的乘法次数就不一样;在算分设计与 分析中,我们知道,乘法的次数越多,消耗的空间就越大,所需 的时间就越多。
3、当多个矩阵相乘时:我们假设M i ,j 就是第i 个矩阵到第j 个矩阵的矩阵连乘, 即M i ,j =M i M i+1 …… M j选中一个k 值,i<=k<=j ,使得:M i ,k-1 = M i M i+1…M k-1,M k ,j =M k M k+1…M j用数组C[i][j]表示第i 个矩阵到第j 个矩阵的矩阵连乘 最优解,有:111],[]1,1[{min ],1[+≤<++-=n k nk r r r n k C k C n C }],[]1,[{min ],[1+≤<++-=j k i j k i r r r j k C k i C j i C三、问题分析及算法设计思路1、计算最优值算法:建立两张表(,一张表存储矩阵相乘的最小运算量,主对角线上的值为0,依次求2个矩阵、3个矩阵…、直到n个矩阵相乘的最小运算量,其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得,最后一次求得的值即为n个矩阵相乘的最小运算量;另一张表存储最优断开位置。
2、输出矩阵结合方式算法:矩阵结合即是给矩阵加括号,打印出矩阵结合方式,由递归过程完成。
《算法分析与设计》实验指导与报告书实验目录实验1 求最大公约数 (1)实验2 斐波那契数列 (3)实验3 最近对问题 (6)实验4 堆排序 (7)实验5 霍纳法则和二进制幂 (8)实验6 字符串匹配问题 (9)实验7 Warshall算法和Floyd算法 (10)实验8 最优二叉查找树 (11)实验9 Huffman编码* (12)实验10 求解非线性方程* (13)实验11 投资问题* (14)注:(1)实验4和实验5为变治法应用,二选一;(2)实验7和实验8为动态规划法应用,二选一;(3)带*号的实验为选做实验,根据课时及学生实验完成情况机动安排。
实验1 求最大公约数{c = a;a = b;b = c;}while(a % b != 0){c = a % b;a = b;b = c;}printf("%d", b);return 0;}连续整数检测算法最大公约数算法:#include <stdio.h>int main(){int a,b,t;printf("Please input two integers: ");scanf("%d %d",&a,&b);if(a<b)t=a;elset=b;while(t>=1){if((a%t==0)&&(b%t==0))break;t--;}printf("%d",t);return 0;}相减循环:#include<stdio.h>int main(){int m,n;printf("Please input two integers: ");scanf("%d%d",&m,&n);while(m!=n)if(m>n) m=m-n;else n=n-m;printf("%d",m);return 0;}教师评分实验2 斐波那契数列实验目的(1)求斐波那契数列;(2)区分递归和递推思想。
算法分析与设计实验报告实验一分治策略排序一、实验目的1)以排序问题为例,掌握分治法的基本设计策略;2)熟练掌握合并排序算法的实现;3)熟练掌握快速排序算法的实现;4) 理解常见的算法经验分析方法。
二、算法思路1. 合并排序算法思想:分而治之(divide - conquer);每个递归过程涉及三个步骤第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作第三, 合并: 合并两个排好序的子序列,生成排序结果.最坏时间复杂度最好时间复杂度空间复杂度2.快速排序算法思想:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序。
一躺快速排序的算法是:1)、设置两个变量I、J,排序开始的时候I:=1,J:=N;2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];3)、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;5)、重复第3、4步,直到I=J;三、实验内容:1. 准备实验数据要求:编写一个函数data-generate,生成2000个在区间[1,10000]上的随机整数,并将这些数输出到外部文件data.txt中。
这些数作为本算法实验的输入数据。
2. 实现合并排序算法要求:实现mergesort算法。
输入:待排数据文件data.txt;输出:有序数据文件resultsMS.txt(注:建议将此排好序的数据作为实验二的算法输入);程序运行时间TimeMS。
算法分析与设计课程实验报告班级: 131213学号: 13121XXX姓名: XXX指导老师:邓凡目录算法分析与设计课程实验报告 (1)实验一排序 (1)1. 课本练习2.3-7 (1)2. 实现优先队列 (2)3.快速排序 (2)4. 第k大元素 (3)实验二动态规划 (4)1. 矩阵链乘 (4)2. 最长公共子序列 (5)3. 最长公共子串 (7)4. 最大和 (9)5. 最短路径 (10)实验三贪心策略 (11)1. 背包问题 (11)2. 任务调度 (14)3. 单源点最短路径 (15)4. 任意两点间最短路径 (16)实验四回溯法 (18)1. 0-1背包问题 (18)2. 8-Queen问题 (21)实验一排序1.课本练习2.3-7(1)问题描述描述一个运行时间为 (nlgn)的算法,给定n个整数的集合S和另一个整数x,该算法能确定S中是否存在两个其和刚好是x的元素。
(2)问题分析该问题首先要进行排序,然后用二分查找法判断S中是否存在两个其和刚好是x的元素,因为时间复杂度为(nlgn),所以可以采用归并排序。
(3)算法分析归并排序的思想是将n个元素分成各含n/2个元素的子序列,然后对两个子序列递归地进行排序,最后合并两个已排序的子序列得到排序结果。
二分查找的思想是对于集合中的每一个数字,用二分法找到x-S[i]的位置,若存在且不为其本身,则输出S中存在有两个和等于x的元素;否则,不存在。
(4)实验结果2.实现优先队列(1)问题描述实现优先队列,维护一组元素构成的集合S。
(2)问题分析优先队列是基于堆排序的。
首先将集合S中的元素进行堆排序。
当进行操作时,要不断维护集合S的有序性,即要不断地调整堆。
(3)算法分析本程序中主要的函数有INSERT():需要调用INCREASE_KEY()来维护堆,其时间复杂度为O(lgn),函数MAXIMUM()仅需要返回S[1],时间复杂度为 (1),函数EXTRACT_MAX()需要调用堆排序中的MAX_HEAPIFY,时间复杂度为O(lgn),函数INCREASE_KEY()更新结点到根结点的路径长度为O(lgn),时间复杂度为O(lgn)。
实验报告班级:学号:姓名:总成绩:课程名称:算法分析与设计实训实验项目:1、分治法实验2、动态规划法实验3、贪心法实验4、回溯法实验5、分枝限界法实验计算机学院工业中心202 实验室二〇一〇年 6 月 21 日项目序号 1 项目名称分治法实验成绩小标题找最大值和最小值1、方法思想分治法是把规模大的问题,分割成n个形式相同规模一定或不可再分的子问题,递归地解决每个子问题,再把子问题的结果汇总,合并得到原问题的解。
分治法在每一层递归上由三个步骤组成:(1) 划分(divide):将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。
(2) 解决(conquer):若子问题规模较小,则直接求解;否则递归求解各子问题。
(3) 合并(combine):将各子问题的解合并为原问题的解。
2、问题描述我们将分治策略用于此问题,每次将问题分成大致相等的两部分,分别在这两部分中找出最大值与最小值,再将这两个子问题的解组合成原问题的解,就可得到该问题的分治算法。
3、算法描述REC-MAXMIN(i,j,fmax,fmin)1 if i=j2 then fmax ← fmin ← A[i]3 if i=(j-1)4 then if A[i]>A[j]5 then fmax← A[i]6 fmin←A[j]else fmax ←A[j]8 fmin←A[i]9 else mid ←[(i+j)/2]10 REC-MAXMIN(i,mid,gmax,gmin)11 REC-MAXMIN(mid+1,j,hmax,hmin)12 fmax← max{gmax,hmax}13 fmin←min{gmin,hmin}4、程序清单#include<iostream.h>void FZFa(int i,int j,int &max,int &min,int a[]){if(i= =j){max=a[i];min=a[j];}else if(i= =(j-1)){if(a[i]>a[j]){max=a[i];min=a[j];}else{max=a[j];min=a[i];}}else{int midd=(i+j)/2;int max1=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<min2)min=min1;elsemin=min2;}}int main(){int t[]={2,4};int max,min;FZFa(0,1,max,min,t);cout<<"最大值:"<<max<<endl;cout<<"最小值:"<<min<<endl;return 0;}5、实验结果(可用文字描述和贴图等方式表现实验结果)项目序号 2 项目名称动态规划法实验成绩小标题最长公共子序列1、方法思想动态规划算法与分治法类似,其基本思想也是将待求解问题分成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
福州大学数学与计算机科学学院 《算法设计与分析》上机实验报告(3) 专业和班级 姓名 成绩 学号
实验名称 哈夫曼编码
实验目的和求 1. 理解算法设计的基本步骤和各步的主要内容,基本要求 2. 加深对贪心选择算法基本思想的理解 3.培养学生用计算机解决实际问题的能力
实验任务 1.掌握哈夫曼编码问题的基本算法及其应用 2. 利用贪心选择算法找出具体问题的最优解 3. 分析实验结果,总结算法的时间和空间复杂度
实验步骤 1. 哈夫曼编码问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。一个包含100,000个字符的文件,各字符出现频率不同,如下表所示。
有多种方式表示文件中的信息,若用0,1码表示字符的方法,即每个字符用唯一的一个0,1串表示。若采用定长编码表示,则需要3位表示一个字符,整个文件编码需要300,000位;若采用变长编码表示,给频率高的字符较短的编码;频率低的字符较长的编码,达到整体编码减少的目的,则整个文件编码需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224,000位,由此可见,变长码比定长码方案好,总码长减小约25%。 前缀码:对每一个字符规定一个0,1串作为其代码,并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单;例如001011101可以唯一的分解为0,0,101,1101,因而其译码为aabe。 哈夫曼提出了构造最优前缀码的贪心算法,由此产生的编码方案称为哈夫曼算法。 2. 算法的设计思想 哈夫曼编码依据贪心算法来构造最优前缀码,构造思想步骤如下:
(1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
(2)算法以|C|个叶结点开始,执行|C|-1次的“合并”运算后产生最终所要求的树T。
(3)假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后,产生一棵新的树,其频率为合并的2棵树的频率之和,并将新树插入优先队列Q。经过n-1次的合并后,优先队列中只剩下一棵树,即所要求的树T。
构造过程如图所示:
3. 算法正确性证明 要证明哈夫曼算法的正确性,只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。 (1)贪心选择性质 二叉树T表示字符集C的一个最优前缀码,证明可以对T作适当修改后得到一棵新的二叉树T”,在T”中x和y是最深叶子且为兄弟,同时T”表示的前缀码也是C的最优前缀码。设b和c是二叉树T的最深叶子,且为兄弟。设f(b)<=f(c),f(x)<=f(y)。由于x和y是C中具有最小频率的两个字符,有f(x)<=f(b),f(y)<=f(c)。首先,在树T中交换叶子b和x的位置得到T',然后再树T'中交换叶子c和y的位置,得到树T''。如图所示:
由此可知,树T和T'的前缀码的平均码长之差为: 因此,T''表示的前缀码也是最优前缀码,且x,y具有相同的码长,同时,仅最优一位编码不同。 (2)最优子结构性质
二叉树T表示字符集C的一个最优前缀码,x和y是树T中的两个叶子且为兄弟,z是它们的父亲。若将z当作是具有频率f(z)=f(x)+f(y)的字符,则树T’=T-{x,y}表示字符集C’=C-{x, y} ∪ { z}的一个最优前缀码。因此,有:
如果T’不是C’的最优前缀码,假定T”是C’的最优前缀码,那么有
,显然T”’是比T更优的前缀码,跟前提矛盾!故T'所表示的C'的前缀码是最优的。
由贪心选择性质和最优子结构性质可以推出哈夫曼算法是正确的,即HuffmanTree产生的一棵最优前缀编码树。
4. 哈夫曼编码算法的程序代码 (1)huffman.cpp,程序主文件 1. //huffman 贪心算法 哈夫曼算法 2. #include "stdafx.h" 3. #include "BinaryTree.h" 4. #include "MinHeap.h" 5. #include 6. using namespace std; 7. 8. const int N = 6; 9. 10. template class Huffman; 11. 12. template 13. BinaryTree HuffmanTree(Type f[],int n); 14. 15. template 16. class Huffman 17. { 18. friend BinaryTree HuffmanTree(Type[],int); 19. public: 20. operator Type() const 21. { 22. return weight; 23. } 24. //private: 25. BinaryTree tree; 26. Type weight; 27. }; 28. 29. int main() 30. { 31. char c[] = {'0','a','b','c','d','e','f'}; 32. int f[] = {0,45,13,12,16,9,5};//下标从1开始 33. BinaryTree t = HuffmanTree(f,N); 34. 35. cout<<"各字符出现的对应频率分别为:"<36. for(int i=1; i<=N; i++) 37. { 38. cout<39. } 40. cout<41. 42. cout<<"生成二叉树的前序遍历结果为:"<43. t.Pre_Order(); 44. cout<45. 46. cout<<"生成二叉树的中序遍历结果为:"<47. t.In_Order(); 48. cout<49. 50. t.DestroyTree(); 51. return 0; 52. } 53. 54. template 55. BinaryTree HuffmanTree(Type f[],int n)
56. { 57. //生成单节点树 58. Huffman *w = new Huffman[n+1]; 59. BinaryTree z,zero; 60. 61. for(int i=1; i<=n; i++) 62. { 63. z.MakeTree(i,zero,zero); 64. w[i].weight = f[i]; 65. w[i].tree = z; 66. } 67. 68. //建优先队列 69. MinHeap> Q(n); 70. for(int i=1; i<=n; i++) Q.Insert(w[i]);
71. 72. //反复合并最小频率树 73. Huffman x,y; 74. for(int i=1; i75. { 76. x = Q.RemoveMin(); 77. y = Q.RemoveMin(); 78. z.MakeTree(0,x.tree,y.tree); 79. x.weight += y.weight; 80. x.tree = z; 81. Q.Insert(x); 82. } 83. 84. x = Q.RemoveMin(); 85. 86. delete[] w; 87. 88. return x.tree; 89. }
(2)BinaryTree.h 二叉树实现 1. #include 2. using namespace std; 3. 4. template 5. struct BTNode 6. { 7. T data; 8. BTNode *lChild,*rChild; 9. 10. BTNode() 11. { 12. lChild=rChild=NULL; 13. } 14. 15. BTNode(const T &val,BTNode *Childl=NULL,BTNode *Childr=NULL) 16. { 17. data=val; 18. lChild=Childl; 19. rChild=Childr; 20. } 21. 22. BTNode* CopyTree() 23. { 24. BTNode *nl,*nr,*nn; 25. 26. if(&data==NULL) 27. return NULL; 28. 29. nl=lChild->CopyTree(); 30. nr=rChild->CopyTree(); 31. 32. nn=new BTNode(data,nl,nr); 33. return nn; 34. } 35. }; 36. 37. 38. template 39. class BinaryTree 40. { 41. public: 42. BTNode *root; 43. BinaryTree(); 44. ~BinaryTree(); 45. 46. void Pre_Order(); 47. void In_Order(); 48. void Post_Order(); 49. 50. int TreeHeight()const;