算法设计第二章排序算法

实验报告实验目的：理解递归算法的基本思想和递归程序的执行过程，并熟悉编写递归算法。掌握递归算法的思想，对给定的问题能设计出分治算法予以解决。实验内容：编程实现讲过的例题：二分搜索、合并排序、快速排序。实验过程：1.二分搜索：1.1问题描述在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查找元素x和线性表L，输出x在L中的位置或者x不在L中的信息。1.2算法分析(1)首先将链表中第一个元素给参数low，最后一个元素给参量high；(2)在lowhigh的条件下：取d=(low+high)/2;若所查找元素第d个元素：则将d赋值给参量high；若所查找元素第d个元素：则将d+1赋值给参量high;继续在low与high的范围内查找；找到则输出。(3)当不满足lowhigh的条件时：输出没有查找到此元素。1.3程序框图假定要搜索x=9：1457891012152223273235145789108910↑2.合并排序2.1问题描述假定有一个数组A[1…m]p.q.r是它的三个索引，并且有1=p=qr=m,两个子数组A[p…q]A[q+1…r]各自按升序排列。我们要重新安排A中的元素的位置，使得子数组A[p…r]也按升序排列。2.2算法思想⑴.使用两个指针s.t.初始化时各自指向A[p]A[p+1]，再用一个空数组B[p…r]作暂存器。⑵.每一次比较元素A[s].A[t],将小的元素添加到辅助数组B[p…r]中，如果相同就把A[s]添加进去。同时更新指针，若添加是A[s]，则s++；若添加是A[t]，则t++；⑶.当条件s=q+1ort=q+1时过程结束，在前一种情况下把数组A[t…r]中剩余的元素添加到在B中.在后一种情况下把数组A[s…q]中剩余的元素添加到在B中.⑷.最后，把数组B[p…q]复制到A[p…r].2.3程序框图如图：给出有序数组两个：78910789101012153.快速排序3.1问题描述假定有一个数组A[1…m].其中的元素为无序排列；我们要重新安排A中的元素的位置，使得子数组A[p…r]也按升序排列。3.2算法思想(1)首先将链表中第一个元素给参数low，最后一个元素给参量high；(2)在lowhigh的条件下：将low与high之间的元素以low元素为轴，比low小的元素交换到low以前；比low大的元素交换到low以后。此时得到一个以low为轴的划分，然后分别对low前和其后的数列再进行划分，直到数列成为单个元素，此时完成排序；(3)程序用递归实现。3.3程序框图57164832↑↑ij51764832↑↑ij51467832↑↑ij51437862↑↑ij51432867↑↑ij21435867↑↑ij4.程序源代码：（说明：我是将本试验的的三个小试验放在同一个函数中实现：首先从文件“data.txt”中读取无序数列存入动态数组中，然后进行快速排序，再读入数据进行合并排序，然后对此有序数列进行二分查找）#includestdio.h101215#includemath.h#includestdlib.hint*L,*C;intNum;inttag=0;voidreadindata(){FILE*fpin;inta,i=0;if((fpin=fopen(data.txt,r))==NULL){printf(Cannotopen!);exit(0);}while(!feof(fpin)){fscanf(fpin,%d,&a);i++;}Num=i;rewind(fpin);L=(int*)malloc(sizeof(int)*(Num+1));for(i=1;i=Num;i++){fscanf(fpin,%d,&a);*(L+i)=a;}}intPartition(intlow,inthigh){intkey;*(L+0)=*(L+low);key=*(L+low);while(lowhigh){while(lowhigh&&(*(L+high)=key))high--;*(L+low)=*(L+high);while(lowhigh&&*(L+low)=key)low++;*(L+high)=*(L+low);}*(L+low)=*(L+0);returnlow;}voidQSort(intlow,inthigh){intpoint;if(lowhigh){point=Partition(low,high);QSort(low,point-1);QSort(point+1,high);}}voidQuickSort(){QSort(1,Num);}voidMerge(inti,intm,intn){intp;intk,t,j;t=i;C=(int*)malloc(sizeof(int)*(n-i+2));for(j=m+1,k=1;i=m&&j=n;k++){if((*(L+i))=(*(L+j)))*(C+k)=*(L+(i++));else*(C+k)=*(L+(j++));}while(i=m)*(C+(k++))=*(L+(i++));while(j=n)*(C+(k++))=*(L+(j++));for(p=t,k=1;p=n;k++,p++)*(L+p)=*(C+k);}voidMSort(ints,intt){intm;if(s==t)*(L+s)=*(L+s);else{m=(s+t)/2;MSort(s,m);MSort(m+1,t);Merge(s,m,t);}}voidMergeSort(){MSort(1,Num);}voidBsearch(intx,intlow,inthigh){intd,midkey;if(low=high)printf(Can'tfindthenumber!\n);else{d=(low+high)/2;midkey=*(L+d);if(x==midkey){printf(findthenumber,it'sthe%dthone,d);tag=1;}elseif(xmidkey)Bsearch(x,low,d);elseBsearch(x,d,high);}}voidsearch(){intx;charc;while(1){printf(Inputthenumberforsearching:);scanf(%d,&x);Bsearch(x,1,Num);if(tag==0)printf(Can'tfindthenumber!\n);printf(\nGoon?(input:'y'or'n'));c=getchar();c=getchar();if(c=='n'||c=='N')break;}}voidreadoutdata(int*L){inti;for(i=1;i=Num;i++)printf(%4d,*(L+i));printf(\n);}voidmain(){readindata();QuickSort();printf(快速排序的结果：\n);readoutdata(L);readindata();MergeSort();printf(合并排序的结果：\n);readoutdata(L);search();}实验总结：1.……2.……实验报告班号：10010407学号：042738姓名：赵丽丽实验目的：熟练掌握回溯法实验内容：回溯算法的几种形式实验过程：1.背包问题1.1问题描述对容量为c的背包进行装载。从n个物体中选取装入背包的物品，每件物品I的重量为wi，价值为vi。对于可行的背包装载，背包中的物品的总重量不能背包的总容量，最佳装载是指所装入的物品价值最高。1.2算法分析voidsearch(intm){if(m=n)//递归结束条件putout();//全部搜索完，得到一组解，相应的结果else{//不放入此物search(m+1);//搜索下一个a[m]=1;//放入此物search(m+1);//，搜索下一个a[m]=0;//恢复}}1.3程序框图①②②③③③③④④④④④④④④1.4程序源代码#includestdio.h#includemath.hintc,n,max;intw[20];intv[20];inta[20]={0};voidreaddata(){inti;printf(输入背包的容量：);scanf(%d,&c);printf(物品的件数为：);scanf(%d,&n);for(i=0;in;i++){printf(输入第%d背包的重量和价值是：,i+1);scanf(%d%d,&w[i],&v[i]);}}voidcheckmax(){inti;intweight=0;intvalue=0;for(i=0;in;i++){if(a[i]==1){weight+=w[i];//统计重量之和value+=v[i];//统计价值之和}}if(weight=c)//如过价值未超过容量，则为可行解if(valuemax)max=value;}voidsearch(intm){if(m=n)checkmax();//全部搜索完，得到一组解else{search(m+1);//不放入此物，搜索下一个a[m]=1;search(m+1);//放入此物，搜索下一个a[m]=0;}}voidmain(){readdata();//读入数据search(0);//从来开始搜索，printf(%d\n,max);//输出结果}2.装载问题2.1问题描述有两艘船，载重量分别是c1,c2。N个集装箱，重量是wi(I=1.2….),且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有的集装箱全部装入这两艘船中。2.2算法思想算法思想同背包问题，只是在putout()函数中，增加判断是否剩余集装箱能否装入第二艘船。voidsearch(intm){if(m=n)//递归结束条件putout();//全部搜索完，得到一组解，相应的结果else{//不放入此物search(m+1);//搜索下一个a[m]=1;//放入此物search(m+1);//，搜索下一个a[m]=0;//恢复}}2.4程序源代码#includestdio.h#includemath.hintc1,c2,n;intsum=0;inttag=0;inta[30]={0};intw[30];voidreaddata(){inti;printf(输入两艘船的载重c1,c2：);scanf(%d%d,&c1,&c2);printf(集装箱的个数为：);scanf(%d,&n);for(i=0;in;i++){printf(输入第%d集装箱的重量是：,i+1);scanf(%d,&w[i]);sum+=w[i];}}voidcheckmax(){inti;intweight=0;for(i=0;in;i++){if(a[i]==1){weight+=w[i];}}if(weight=c1&&(sum-weight)=c2){tag++;printf(\n所有集装箱可全部装入两艘船.\n其中装入第一艘船的集装箱重量为:);for(i=0;in;i++)if(a[i]==1)printf(%3d,w[i]);}}voidsearch(intm){if(m=n)checkmax();else{search(m+1);//此物不放入第一艘船，搜索下一个；a[m]=1;search(m+1);//此物放入第一艘船，搜索下一个；a[m]=0;//恢复}}voidmain(){readdata();search(0);if(!tag)printf(所有集装箱不可能全部装入两艘船.\n);}3.堡垒问题3.1问题描述在所给出的城堡图纸中放入堡垒，城堡中有些格子是墙，有些格子是空的，可以放置堡垒，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙的相隔，则