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

算法分析与设计实验报告算法分析与设计 课程实验实验报告专业：计算机科学与技术 班级： 姓名： 学号： 完成时间：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) printf(无法判断n); return; if (first=last) /只有一个硬币时候printf(假币的序号为%d, 假币的重量为%dn, first, coinfirst); else if(last-first=1) /如果只剩下两个硬币（此时count不为）if (first 0) /不是最开始的硬币if (coinfirst = coin0) /如果第first和第个相等，说明first位置不是伪币solve(coin,count,first+1,last);else /否则，说明first位置是伪币solve(coin,count,first,last-1); else if(lastcount-1) /不是最后的硬币if (coinfirst=coincount-1) /如果第first和最后一个相等，说明last位置不是伪币solve(coin,count,first+1,last); else /否则，说明first位置是伪币solve(coin,count,first,last-1); else if (firstlast) int temp=(last-first+1)/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; printf(硬币个数：%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;printf(输入钱数:n);scanf(%d,&money);for(i=0;i4;i+)ai=money/Ti;money=money%Ti;printf(找钱结果:n硬币:t);for(i=0;i=3;i+)printf(%dt|t,Ti);printf(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;printf(输入钱数:n);scanf(%d,&money);for(i=0;iTi*counti) /当剩余钱数大于当前硬币总值ai=counti; /当前硬币个数取现有的最大值money=money-Ti*counti;elseai=money/Ti;money=money%Ti;printf(找钱结果:n硬币:t);for(i=0;i=3;i+)printf(%dt|t,Ti);printf(nn个数:t);for(i=0;i=3;i+)printf(%dt|t,ai);printf(n);return(0);六、 实验结果1伪造硬币问题运行结果：硬币个数：100假币的序号为12, 假币的重量为1截图：2找零钱问题（1、硬币个数无限制）运行结果：输入钱数:67找钱结果:硬币: 25 | 10 | 5 | 1 |个数: 2 | 1 | 1 | 2 |截图：3找零钱问题（2、硬币个数有限制，其中硬币个数限制分别为1,2,10和1000。）运行结果：输入钱数:123找钱结果:硬币: 25 | 10 | 5 | 1 |个数: 1 | 2 | 4 | 2 |截图：七、 实验分析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;/*输入各个数据*/printf(请输入%d个物体的价值：,n); for(i=1;i=n;i+) scanf(%d,&vi);printf(请输入%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);printf(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-1,c);/当前最大容量for(j=0;j=jMax;j+) /初始化mmnj=0;for(j=wn;j1;i-)jMax=min(wi-1,c);for(j=0;j=jMax;j+)mij=mi+1j;for(j=wi;j=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;/*输入各个数据*/printf(请输入%d个物体的价值：,n);for(i=1;i=N;i+)scanf(%d,&vi);printf(请输入%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);printf(nt(其中表示放进背包)n);return(0);3，0-1背包问题的回溯算法源程序：/c+实现#includeusing namespace std;class Knapfriend int 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 bestp;/当前最优值int *bestx;/当前最优解int *x;/当前解; int Knap:Bound(int i) /计算上界int cleft=c-cw;/剩余容量int b=cp;/以物品单位重量价值递减序装入物品while(i=n&wi=cleft) cleft-=wi; b+=pi; i+;/装满背包if(in)if(bestpcp) printf(最优解为n); for(int j=1;j=n;j+) bestxj=xj; bestp=cp;return; if(cw+wibestp)/搜索右子树 xi=0; Backtrack(i+1); class Object friend int Knapsack(int p,int w,int c,int n);public:int operator=a.d);private:int ID;float d;int Knapsack(int p,int w,int c,int n) /为Knap:Backtrack初始化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)return 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=new intn+1;w=new intn+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)endl; /调用子函数并输出六、 实验结果 1、贪心算法运行结果请输入5个物体的价值：4 6 9 3 1请输入5个物体的重量：4 7 3 2 5请输入容量：