算法设计与分析大作业报告

《算法设计与分析大作业报告》班级：学号：姓名：分治法大作业报告问题陈述：编程实现归并排序算法和快速排序算法，输出排序结果。输入10组相同的数据，验证排序结果和完成排序的比较次数。分治法基本思想：分治法的基本思想是将问题分解成若干个子问题，然后求解子问题。子问题较原问题要容易些，先得出子问题的解，由此得出原问题的解，这就是所谓“分而治之”的思想。算法描述：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。本实验就是通过归并排序和快速排序来体现分治的思想。1.归并排序的思想：将A（1），……，A（N）分成两个集合，对每个集合单独分类，然后将已分类的两个序列归并成一个含N个元素分好类的元素2.快速排序的思想：选取A的某个元素做为划分元素，然后将其他元素重新排列，使在划分元素以前出现的元素都小于或等于它，在划分元素之后出现的划分元素都大于等于它。程序代码：#includestdio.h#includetime.h#includestdlib.hvoidMergeSort(int*data,intx,inty,int*temp){intp,q,m,i=x;if(y-x1){m=x+(y-x)/2;p=x;q=m;MergeSort(data,x,m,temp);MergeSort(data,m,y,temp);while(pm||qy){if(q=y||(pm&&data[p]data[q])){temp[i++]=data[p++];}else{temp[i++]=data[q++];}}for(i=x;iy;i++)data[i]=temp[i];}}voidHoareSort(int*data,intx,inty){intp=x,q=y-1,temp;while(pq){while(qp&&data[q]=data[p])q--;if(qp){temp=data[p],data[p]=data[q],data[q]=temp;p++;}while(qp&&data[p]=data[q])p++;if(pq){temp=data[p],data[p]=data[q],data[q]=temp;q--;}if(p==q){HoareSort(data,x,p);HoareSort(data,p+1,y);}}}intmain(){intdata[10],i;inttemp[10];srand(time(NULL));for(i=0;i10;i++){data[i]=rand()%100;}printf(未排序排序的数据为：\n);for(i=0;i10;i++){printf(%d,data[i]);}printf(\n);printf(归并排序的顺序为：\n);MergeSort(data,0,10,temp);for(i=0;i10;i++){printf(%d,data[i]);}printf(\n);printf(快速排序的顺序为：\n);HoareSort(data,0,10);for(i=0;i10;i++){printf(%d,data[i]);}printf(\n);return0;}运行结果：结论分析：归并排序和快速排序都是递归排序，但是归并排序是稳定的排序方法，快速排序是不稳定的排序方法。（1）此问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（2）利用该问题分解出的子问题的解可以合并为该问题的解；（3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。动态规划大作业报告问题陈述：定义0-1背包问题为：}yvmax{n1iii。限制条件为：cywn1iii，且ni{0,1},1yi。iv和iw分别表示第i个物品的价值和重量，c为背包容量。动态规划基本思想：动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。算法描述：刻画0-1背包问题的最优解的结构。可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果一个问题的最优解包含了物品n，即xn=1，那么其余x1，x2，...，x(n-1)一定构成子问题1，2，...，n-1在容量W-wn时的最优解。如果这个最优解不包含物品n，即xn=0，那么其余x1，x2，...，x(n-1)一定构成子问题1，2，...，n-1在容量W时的最优解。递归定义最优解的值，根据上述分析的最优解的结构递归地定义问题最优解。设c[i,w]表示背包容量为w时，i个物品导致的最优解的总价值，得到下式。显然要求c[n,w]。程序代码：#includeiostreamusingnamespacestd;voidPath(intn,intW,intc[][100],int*v,int*wei){memset(*c,0,(W+1)*sizeof(int));for(inti=1;i=n;i++){c[i][0]=0;for(intw=1;w=W;w++){if(wei[i-1]w){c[i][w]=c[i-1][w];}else{inttemp=c[i-1][w-wei[i-1]]+v[i-1];if(c[i-1][w]temp){c[i][w]=c[i-1][w];}elsec[i][w]=temp;}}}}voidfind(intc[][100],int*x,int*wei,intn,intW){intw=W;for(inti=n;i=2;i--){if(c[i][w]==c[i-1][w]){x[i-1]=0;}else{x[i-1]=1;w=w-wei[i-1];}}if(c[1][w]==0)x[0]=0;elsex[0]=1;}intmain(){intn=5;intW=100;intw[]={10,48,35,23,25,30};intv[]={40,10,20,30,50};intc[6][100]={0};Path(n,W,c,v,w);cout最优的总价值为：;coutc[6][100]endl;intx[5];find(c,x,w,n,W);cout用0表示不装入，1表示装入，情况如下：endl;for(inti=1;in+1;i++){cout第i件物品的装入状态为：;coutx[i]endl;}return0;}运行结果：结论分析：上述代码的时间复杂度为O(nw)。能表示出装入或者不装入但计算出装入后的总价值有点问题，程序还不够完善有待改进。动态规划问题的的实质就是寻求一个最优解的过程，实质就是为问题寻求一个最优算法，这个最优算法解出来的值是运用所有算法中最接近实际值的解。一般对一个问题，不会运用多种算法，而只会选取其中的一种来求解（但实际问题中常常需要不同算法的结合，不过一般是处理不同方面的算法）不同的算法对待不同的问题总是有利有弊。贪心法大作业报告问题陈述：给定n种物品和一个背包.物品i的重量是Wi,其价值为Vi,背包的容量为C。在选择物品i装入背包时，可以选择物品i的一部分，1=i=n。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。贪心法基本思想：贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质：1.整体的最优解可以通过局部的最优解来求出；2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。算法描述：对于背包问题,若它的一个最优解包含物品j,则从该最优解中拿出所含的物品j的那部分重量w,剩余的将是n-1个原重物品1,2,…,j-1,j+1,…,n及重为Wj-W的物品j中可装入容量为c-w的背包且具有最大价值的物品。程序代码：#includeiostream.hstructgoodinfo{floatp;floatw;floatX;intflag;};voidInsertionsort(goodinfogoods[],intn){intj,i;for(j=2;j=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].pgoods[i].p){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}}voidbag(goodinfogoods[],floatM,intn){floatcu;inti,j;for(i=1;i=n;i++)goods[i].X=0;cu=M;for(i=1;in;i++){if(goods[i].wcu)break;goods[i].X=1;cu=cu-goods[i].w;}if(i=n)goods[i].X=cu/goods[i].w;for(j=2;j=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].flaggoods[i].flag){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}cout最优解为:endl;for(i=1;i=n;i++){cout第i件物品要放:;coutgoods[i].Xendl;}}voidmain(){cout运用贪心法解背包问题endl;intj;intn;floatM;goodinfo*goods;while(j){cout请输入物品的总数量：;cinn;goods=newstructgoodinfo[n+1];cout请输入背包的最大容量：;cinM;coutendl;inti;for(i=1;i=n;i++){goods[i].flag=i;cout请输入第i件物品的重量:;cingoods[i].w;cout请输入第i件物品的效益:;cingoods[i].p;goods[i].p=goods[i].p/goods[i].w;coutendl;}Insertionsort(goods,n);bag(goods,M,n);cout请问您还要继续运行此程序吗？请用Y或者N回答。endl;cinj;if(j=='N')break;}}运行结果：结论分析：程序较完整，算法复杂度为O（N*N）。但有一点点小小的不足并没有算出物品装入后的重量，也没有展示最优解的价值为多少。回溯法大作业报告问题陈述：在n×n格的棋盘上放置彼此不受攻击的n个皇后按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。要求在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。回溯法基本思想：从一条路往前走，能进则进，不能进则退回来，换一条路再试。当我们