算法分析与设计实验报告.docx
- 文档编号:11609228
- 上传时间:2023-06-01
- 格式:DOCX
- 页数:20
- 大小:224.42KB
算法分析与设计实验报告.docx
《算法分析与设计实验报告.docx》由会员分享,可在线阅读,更多相关《算法分析与设计实验报告.docx(20页珍藏版)》请在冰点文库上搜索。
算法分析与设计实验报告
算法设计与分析基础实验报告
所在学院:
信息科学与工程学院
专业班级:
学生姓名:
学生学号
指导教师:
一>实验目的
加深对分治法、回溯法、动态规划这三种重要的算法思想的理解
分别掌握一个算法实例
二>实验内容
运用分治法,回溯法,动态规划思想分别编写一个程序,从文件中读取输入数据,并将结果写入文件。
三>算法说明
分治法:
就是将一个问题分成几个小问题(最好为两个),最好拥有同样的规模,然后再对这些小问题求解(一般用递归),最后合并这些小问题的解,就得到原始问题的解了。
我选择用快速排序来实现分治法;
动态规划:
基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。
若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。
如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。
我们可以用一个表来记录所有已解的子问题的答案。
不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。
这就是动态规划法的基本思路。
具体的动态规划算法多种多样,但它们具有相同的填表格式。
我选择用0-1背包问题来实现这个算法。
回溯法基本思想:
在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。
当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。
四>实验代码和运行结果
N皇后问题
#include
#include
#definemaxn16
voidsearch(int);
voidreaddata();//读入数据
voidoutputresult();//打印结果
intcanplace(int,int);//判断该位置能否放置皇后
voidplace(int,int);//在该位置能否放置皇后
voidtakeout(int,int);//把该位置放置皇后去掉
inta[maxn];//a[i]存放第i个皇后的位置
FILE*fp;
intn,num=0;//n用于存放从文件中读取的皇后的数量,num用于表示可能的方案
char*filename;
charstr[]={"thenumberofprojectis:
"};
intcontinuey=1;
intmain()
{
readdata();
if(continuey){
search(0);//递归搜索
printf("共有%d种方案,已经输出到文件N-huanghou-io文件.txt中,请查看!
\n",num);
}
}
voidreaddata(){
filename="N-皇后问题-io-文件.txt";
if((fp=fopen(filename,"r"))==NULL){
printf("不能打开文件%s!
\n",filename);
exit(0);
}
fscanf(fp,"%d",&n);
fclose(fp);
if(n>maxn){
printf("输入的皇后过多,请重新配置输入的文件,减少皇后的个数!
");
continuey=0;
exit(0);
}
printf("从文件读入的数据为:
%d\n",n);
}
voidsearch(intm)
{
inti;
if(m>=n){//当已经找出一组解时
num++;
outputresult();//输出当前结果
//getwchar();
}
else
{
for(i=0;i { if(canplace(m,i))//判断第m个格子是否能放堡垒 { place(m,i);//在(m,i)格子上放置一个皇后 search(m+1);//递归搜索下一行 takeout(m,i);//当该行中所有的列都不符合时,退回上一级,把(m,i)格子上的皇后去掉 } } } } intcanplace(introw,intcol) { if(row==0) return (1); inti; for(i=0;i if(abs(i-row)==abs(a[i]-col)||a[i]==col) return(0); return (1); } voidplace(introw,intcol) { a[row]=col; } voidtakeout(introw,intcol) { a[row]=-1; } voidoutputresult() { intyes=1,no=0; inti,j; if((fp=fopen(filename,"a"))==NULL){ printf("不能打开文件%s! \n",filename); exit(0); } fprintf(fp,"\n"); fputs(str,fp); //fwrite(str,strlen(str),1,fp); fprintf(fp,"%d",num); fputs("\n",fp); fprintf(fp,"\n"); for(i=0;i { for(j=0;j if(a[i]==j) fprintf(fp,"%d\t",yes); else fprintf(fp,"%d\t",no); } fprintf(fp,"\n"); } } 0-1背包问题 #include #definemaxnum10//定义物品最多个数为10 voidreaddata(); voidinitial(); voidsearch(int); intcheckmax(); voidqsort(); voidselect(); voidprintresult(); intcap,num;//c: 背包容量;n: 物品数 intwa[maxnum],va[maxnum];//w[i]、v[i]: 第i件物品的重量和价值 inta[maxnum],s[maxnum+1],maxval; /*a数组存放当前解各物品选取情况; maxval: 记录最大价值a[i]=0表示不选第i件物品, a[i]=1表示选第i件物品*/ intpmv[maxnum];//第i个物品的单位重量的回报 intupborder;//子集的上界 intweight,values;//已选物品的重量w,价值v intflagleft=1,flagright=1;//左右子女节点是否满足约束条件标志,0不满足1,满足 intcontinuey=1;//是否继续深入标志 intm=0;//替换变量 intj=0;//为第j个暂存节点 intps[maxnum][maxnum];//中间被抛弃的可行节点的w,v,ub,m信息,ps[j][0]=w,ps[j][1]=v, //ps[j][2]=ub,ps[j][3]=m intleft,right; FILE*fp; char*filename; intmain() { readdata();//读入数据 initial();//初始化剩余物品的最佳单价 while(continuey){ search(m);//搜索 m++; } printresult(); } voidreaddata() { inth; filename="0-1背包问题.txt"; if((fp=fopen(filename,"ra"))==NULL){ printf("不能打开文件%s! \n",filename); exit(0); } fscanf(fp,"%d%d",&num,&cap); if(num>maxnum){ printf("输入的物品过多,请重新配置输入的文件! "); exit(0); } printf("从文件读入的物品个数为: %d,背包的容量为: %d\n",num,cap); getchar(); for(h=0;h fscanf(fp,"%d%d",&wa[h],&va[h]); } fclose(fp); } voidinitial(){ inti; for(i=0;i { pmv[i]=va[i]/wa[i]; } pmv[num]=0; qsort();//对物品按单位重量价值由大到小排序,并把对应物品的序号存在数 //组s[]中,s[i]为单位重量价值排在第i的物品序号 weight=0; values=0; upborder=pmv[s[0]]*cap; } voidqsort(){ intargs[maxnum]; inti,k,y,max,sa; for(y=0;y args[y]=pmv[y]; } for(k=0;k max=0; for(i=0;i if(args[i]>max){ max=args[i]; sa=i; } } s[k]=sa; args[sa]=0; } s[k]=num; } voidselect(){ if(weight+wa[s[m]] flagleft=1; left=values+va[s[m]]+(cap-weight-wa[s[m]])*pmv[s[m+1]]; } else{ flagleft=0; left=0; } flagright=1; right=values+(cap-weight)*pmv[s[m+1]]; } voidsearch(intm) { intt; if(m>=num){ t=checkmax(); if(t==0){//与暂存的可行节点信息比较,判断是否已经是最优解,如果//是,则暂停 continuey=0;//checkmax(); } else{//否则返回暂存数组中的序号,处理后从最优的暂存可行节点重新开//始搜索 weight=ps[t][0];//交换暂存可行节点信息,j为最有暂存点的序号 values=ps[t][1]; upborder=ps[t][2]; m=ps[t][3]; m++; ps[t][2]=0;//销毁原来的暂存点,因为它将会产生一个新的暂存点 } } else { select(); if(flagleft==1&&flagright==1){ upborder=left; ps[j++][0]=weight;//暂存右边可行节点信息 ps[j++][1]=values; ps[j++][2]=right; ps[j++][3]=m; weight+=wa[s[m]]; values+=va[s[m]]; a[s[m]]=1; printf("weight=%d\n",weight); printf("values=%d\n",values); printf("upborder=%d\n",upborder); } else{ upborder=right; a[s[m]]=0; printf("weight=%d\n",weight); printf("values=%d\n",values); printf("upborder=%d\n",upborder); } } } intcheckmax() { intr=0; inti; for(i=0;i { if(ps[i][2] { r=i+1; } } if(ps[r][2]>upborder){//如果存在暂存点的ub值比现在的最优解大 ps[j++][0]=weight;//暂存最优解信息 ps[j++][1]=values; ps[j++][2]=upborder; ps[j++][3]=m; return(r); } else{ maxval=values; return(0);//如果不存在,返回0 } } voidprintresult() { charstrmv[]={"\n最佳选择的价值为: "},strt[]={"物品的序号为: "},strs[]={"是否选择: "}; charstrw[]={"物品的重量为: "},strv[]={"物品的价值为: "}; intl; if((fp=fopen(filename,"a"))==NULL){ printf("不能打开文件%s! \n",filename); exit(0); } fputs("\n",fp); for(l=0;l fputs(strt,fp);//输出物品的序号 fprintf(fp,"%d\t",s[l]); fputs(strw,fp);//输出物品的重量 fprintf(fp,"%d\t",wa[s[l]]); fputs(strv,fp);//输出物品的价值 fprintf(fp,"%d\t",va[s[l]]); fputs(strs,fp);//是否选择物品 fprintf(fp,"%d\t",a[s[l]]); fputs("\n",fp); } fputs(strmv,fp); fprintf(fp,"%d\t",maxval); printf("maxvalue=%d\n",maxval); } 快速排序 #include #include #defineSIZE100 voidquick_sort(intdata[],intx,inty); intpation(intdata[],intx,inty); voidread(); voidwrite(); intn; inta=10; intdata[SIZE]; intmain() { read(); quick_sort(data,0,n-1); write(); printf("数据导入成功,请在(输出文档)中查看排序结果! "); //printf("\n"); return0; } voidquick_sort(intdata[],intx,inty) { if(x>=y)return; intq=pation(data,x,y); quick_sort(data,x,q-1); quick_sort(data,q+1,y); } intpation(intdata[],intx,inty) { intn=data[x],i=x+1,j=y,temp; while (1) { while(data[i] while(data[j]>n)--j; if(i>=j)break; temp=data[i];data[i]=data[j];data[j]=temp; } data[x]=data[j]; data[j]=n; returnj; } voidread() { FILE*fp; fp=fopen("数据.txt","r"); if(! fp){printf("不能打开文件");exit (1);} fscanf(fp,"要排%d个数\n",&n); for(intj=0;j fscanf(fp,"%d",&data[j]); fclose(fp); } voidwrite(){ FILE*fp; fp=fopen("输出.txt","a"); if(! fp){printf("不能打开文件");exit (1);} fprintf(fp,"%d个数字排序结果为",a); fputs("\n",fp); for(inti=0;i { fprintf(fp,"%d",data[i]); } } 五>实验总结 通过实验一方面增长了我们对这三种算法的更进一步的理解,让我们感到算法的奥妙,也让我们接触很多有趣的问题。 在实验的过程中遇到了很多问题,比如那个从文件读数据时,原来没怎么做过,所以也没什么经验,只好问同学,上网查找,和问老师,最后基本上做出来了。 实验中让我们了解了算法中的细节问题,原来一直停留在宏观上对算法的大体描述,现在要实现每个细节,还是挺耗费时间的。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 设计 实验 报告