算法分析与设计实验报告 完整版

算法分析与设计 课程实验实验报告专业:计算机科学与技术班级：姓名：学号：完成时间：2009 年6月15 日实验一 算法实现一一、实验目的与要求熟悉C/C+语言的集成开发环境； 通过本实验加深对分治法、贪心算法的理解。二、实验内容:掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。三、实验题1. 【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬 币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想 写出解决问题的算法，并计算其时间复杂度。2. 【找零钱问题】一个小孩买了价值为33 美分的糖，并将1 美元的钱交给售货员。售 货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、 5美分、及1 美分的硬币。给出一种找零钱的贪心算法。四、实验步骤理解算法思想和问题要求；编程实现题目要求； 上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序1. 伪造硬币问题源程序：/C语言实现#include #inClude#inClude#define N 100#define N1 12/只能判断是否相等的天平void solve(int Coin,int Count,int first,int last) if (Count=2) prin tf(无法判断n);return;if (first=last) /只有一个硬币时候printf(假币的序号为%d,假币的重量为dn, first, coinfirst);else辻(last-first=l) /如果只剩下两个硬币(此时count不为)if (first 0) /不是最开始的硬币if (coinfirs t = coin0) /如果第 firs t和第个相等，说明 first 位置不是伪币solve(coin,count,first+1,last);else/否则，说明firs t位置是伪币solve(coin,count,first,last-1);else if(lastcount-1) /不是最后的硬币if (coinfirs t=coincoun tT)/如果第 firs t和最后一个相等,说明las t位置不是伪币solve(coin,count,first+1,last);else/否则，说明firs t位置是伪币solve(coin,count,first,last-1);elseif (firstlast)int temp=(last-first+l)/3; /将硬币分为三组int sum1=0, sum2=0;for(int i=0;itemp;i+)sum1+=coinfirst+i; sum2+=coinlast-i;if (sum1=sum2) /两边的总重相等,在中间，递归 solve(coin,count,first+temp,last-temp);else /在两边,不在中间if (sum1=coinfirst+temp*temp) /左边的和中间的相等,在右边， 递归solve(coin,count,last-temp+1,last);else solve(coin,count,first,first+temp-1); /右边的和中间的相等, 在左边，递归void main() int i;int coinN; /定义数组coin用来存放硬币重量for(i=0;iN;i+) /初始化数组coini=0; /所用硬币初始值为coinN1=1;/第N1个设置为，即伪币int cnt = N;prinf (硬币个数:%dn,cnt); solve(coin,cnt,0,cnt-1);2 找零钱问题(1) 零钱个数无限制的时候:源程序：/c语言实现#include main()int T=25,10,5,1;int a5;int money,i,j;prin tf(输入钱数:n);scanf(%d,&money); for(i=0;i4;i+)ai=money/Ti; money=money%Ti;prin tf(找钱结果:n硬币：t);for(i=0;i=3;i+)printf(%dt|t,Ti);prin tf (n 个数：t);for(i=0;i=3;i+)printf(%dt|t,ai);printf(n);return(0);(2)当零钱个数有个数限制的时候：源程序：/C语言实现#include main()int T=25,10,5,1; /硬币的面值int a5; /用来记录找钱的个数int Count=1,2,10,1000; /各个面值硬币的个数int money,i;prin tf(输入钱数:n);sCanf(%d,&money);for(i=0;iTi*Counti) /当剩余钱数大于当前硬币总值 ai=Counti;/当前硬币个数取现有的最大值money=money-Ti*Counti;elseai=money/Ti;money=money%Ti;prin tf(找钱结果:n硬币：t);for(i=0;i=3;i+)printf(%dt|t,Ti);prin tf (nn 个数：t);for(i=0;i:J.芽 爭I士口it-: 刀常数 斷67捣圜个10ancontinue3找零钱问题（2、硬币个数有限制，其中硬币个数限制分别为1,2,10和 1000。） 运行结果：输入钱数:123找钱结果:硬币:25 |10 |5|1个数:1|2|42截图：忙数： 1：2I4I2Ptess an y ItesF to cont inue七、实验分析1、 在伪造硬币问题中， 由于提供的用来比较硬币重量的仪器只能知道两组硬币的重 量是否相同，而不能判断那一边是较重的或者较轻的，所以当硬币个数是2 的时候 就不能判断伪币的位置。时间复杂度为 O（nlogn）2、找零钱问题中，可以把问题分为两种问题：（1）提供了不限数目的面值为25 美分、10 美分、5 美分、及 1 美分的硬币， 在计算的时候不用考虑硬币数目的限制，从硬币的最大面值开始计算，找到最优解。（2）提供了数目有限的面值为25 美分、10 美分、5 美分、及 1 美分的硬币， 由于硬币的数目有限制，则在解决的时候要考虑是否已经达到硬币数目的最大限 制。实验二 算法实现二一、实验目的与要求熟悉C/C+语言的集成开发环境； 通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验内容:掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握0-1背包问题的三种算法，并分析其优缺点。三、实验题1. 0-1背包问题的贪心算法2. 0-1背包问题的动态规划算法3. 0-1背包问题的回溯算法四、实验步骤理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序；验证分析实验结果； 整理出实验报告。五、实验程序1，0-1背包问题的贪心算法#include#include#include#define N 5/物体个数int m1010;int vN;/vi为价值int wN;/wi为重量int xN;int x2N;int x1N;float sN; /单位价值void Sort(float* s) /排序子程序int i,j,k; float temp;int t;/记录交换时的临时值 for(i=1;i=N;i+) x1i=i;for(i=1;i=N;i+) for(j=i+1;j=N;j+)if(sisj) /按照单位价值排序 t=x1j;x1j=x1i;x1i=t; /记录交换之前的位置 temp=si; si=sj; sj=temp;t=wi; wi=wj;wj=t; t=vi; vi=vj;vj=t;void Knapsack(int c,int n)int i;Sort(s); for(i=1;i=n;i+) /xi=0;xx1i=0;for(i=1;ic) break ;/ xi=1; xx1i=1; c-=wi; if(xi=n) xxi=c/wi;main()int i;int c;/容量int n=N;/*输入各个数据*/ prin tf(请输入%d个物体的价值：,n); for(i=1;i=n;i+)scanf(%d,&vi);prin tf(请输入%d个物体的重量：,n); for(i=1;i=n;i+) scanf(%d,&wi);printf(请输入容量：); for(i=1;i=n;i+) si=(float)vi/(float)wi;scanf(%d,&c); printf (n物体的单位价值：n); for(i=1;i=n;i+) printf(t%f,si); /*输出结果*/printf (n重量：)； for(i=1;i=n;i+) printf(t%d,wi); printf (n价值：);for(i=1;i=n;i+) printf(t%d,vi);Knapsack(c,n); printf (n结果：)； for(i=1;i=n;i+) printf(t%d,xi);prin tf(nt(其中表示放进背包)n); return(0);2， 0-1背包问题的动态规划算法#include #include#define N 5/物体个数 int m1010;int vN;/vi为价值int wN;/wi为重量int xN;int min(int n1,int n2)if(n1n2)return n2; else return n1;int max(int n1,int n2)if(n2n1)return n2;else return n1;void Knapsack(int c,int n)int i,j;int jMax二min(wn-l,c);/当前最大容量 for(j=0;j二jMax;j+) /初始化m mnj=0;for(j=wn;j=c;j+)/ mnj=vn;for(i=n-1;i1;i-) jMax=min(wi-1,c);for(j=0;j=jMax;j+) mij=mi+1j;for(j=wi;j=c;j+) mij=max(mi+1j,mi+1j-wi+vi);m1c=m2c; if(c=w1)m1c=max(m1c,m2c-w1+v1);void Traceback(int c,int n)int i; for(i=1;in;i+)if(mic=mi+1c) x1=0;elsexi=1; c-=wi;xn=(mnc) ? 1:0;main()int i;int c;/容量int n=N;/*输入各个数据*/prin tf(请输入%d个物体的价值：,n); for(i=1;i=N;i+)scanf(%d,&vi);prin tf(请输入%d个物体的重量：,n); for(i=1;i=N;i+)scanf(%d,&wi); printf(请输入容量：); scanf(%d,&c); Knapsack(c,n);Traceback(c,n);/*输出结果*/printf (n重量：)； for(i=1;i=N;i+)printf(t%d,wi);printf (n价值：); for(i=1;i=N;i+)printf(t%d,vi);printf (n结果：)； for(i=1;i=N;i+)printf(t%d,xi);prin tf(nt(其中表示放进背包)n); return(0);3，0-1背包问题的回溯算法源程序：/c+实现 #include using namespace std;class Knapfriendint Knapsack(int p,int w,int c,int n ); public:void print()for(int m=1;m=n;m+) coutbestxm ;coutendl;private:int Bound(int i); void Backtrack(int i);int c;/背包容量 int n; /物品数 int *w;/物品重量数组 int *p;/物品价值数组 int cw;/当前重量 int cp;/当前价值 int bes tp;/当前最优值 int *bes tx;/当前最优解 int *x;/当前解;int Knap:Bound(int i)/计算上界int clef t二c-cw;/剩余容量int b=cp;/以物品单位重量价值递减序装入物品 while(i=n&wi=cleft) cleft-=wi;b+=pi; i+;/装满背包 if(in)if(bestpcp)prin tf(最优解为n); for(int j=1;j=n;j+) bestxj=xj;bestp=cp;return;if(cw+wi=c) /搜索左子树xi=1; cw+=wi; cp+=pi; Backtrack(i+1);cw-=wi;cp-=pi; if(Bound(i+l)bes tp)/搜索右子树xi=0; Backtrack(i+1);class Objectfriendint Knapsack(int p,int w,int c,int n); public:int operator=(Object a)const return (d=a.d);private: int ID; float d;int Knapsack(int p,int w,int c,int n) /为 Knap:Back tr ack初始化int W=0;int P=0;int i=1;Object *Q=new Objectn; for(i=1;i=n;i+)Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi;W+=wi; if(W=c)ret urn P;/装入所有物品 /依物品单位重量价值排序 float f;for( i=0;in;i+) for(int j=i;jn;j+) if(Qi.dQj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K;K.p = new intn+1;K.w = new intn+1;K.x = new intn+1;K.bestx =new intn+1;K.x0=0;K.bestx0=0;for( i=1;i=n;i+)K.pi=pQi-1.ID;K.wi=wQi-1.ID;K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0; /回溯搜索 K.Backtrack(1);K.print(); delete Q; delete K.w; delete K.p; return K.bestp; void main() int *p; int *w; int c=0; int n=0; int i=0;/*输入各个数据*/ printf(请输入物品的个数：)； scanf(%d,&n);p=newintn+1; w=newintn+1;p0=0; w0=0;printf(n请输入物品的价值：)； for(i=1;i=n;i+) scanf(%d,&pi);printf(n请输入个物品的重量：)； for(i=1;i=n;i+)scanf(%d,&wi)；printf(n请输入背包容量：)； scanf(%d,&c)；/*输出结果*/coutKnapsack(p,w,c,n)any kes1 to cantinue 2、动态规划法运行结果：请输入5 个物体的价值：3 4 6 7 4请输入5 个物体的重量：3 4 5 6 1重量： 34561价值： 34674结果： 00011（其中1 表示放进背包）请输入容量：8一A西 8 孫弋*: 昇昇容 无1A1A 请请请的的慎里屢量：34561其中1表示放进背包）Press：key to cont In Lie3 、回溯法运行结果： 请输入物品的个数：5 请输入物品的价值：3 4 6 7 4 请输入个物品的重量：3 4 5 6 1 请输入背包容量：8 最优解为11001晴输入物品的个数：5晴输入物品的价值：3 4 6 7 4猜输入个物品的重量；3 4 5 6 1BtAf包容量：& 厳优解为110 0 1七、实验分析1,在贪心算法中首先用Sort ()要对物品的重量，价值和单位价值按照单 位价值由大到小排序，然后用Knapsack ()计算最优值，算法的计算时间上界为 O(nlogn)。2,在动态规划法中，用二维数组m来存储m (i, j)的相应值，按照 Knapsack计算后，m1c给出所要求的0T背包问题的最优值。相应的最优值可以由 Traceback 计算：如果 m1c = m2c，则 xl=0,否则 xl=l,当 xl=0 时由 m2c 继续构造最优解。当x1=1时，由m2c-wl继续构造最优解。依次类推，可以构造相 应的最优解(xl,x2,xn)。3，在回溯法的实现中，由Bound计算当前节点处的上界。类Knap的数据 成员记录空间树中的结点信息，以减少参数传递及递归调用所需的栈空间。在解 空间树的当前扩展结点处，仅当要进入右子树时才计算上界Bound，以判断是否 可以将右子树剪去。进入左子树时不需要计算上界，因为其上界与其父结点的上 界相同。