算法分析与设计实验报告

1、算法分析与设计实验报告 班级：学号：姓名：实验一 算法实现一一、 实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对分治法、贪心算法的理解。二、 实验内容:掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。三、 实验题1. 【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算其时间复杂度。（1） 源程序： #include#include#incl

2、udeint findTheCoin(int q,int a,int b); int quantity(int q,int a,int b); void main()time_t ts;srand(unsigned) time(&ts);const int Max=70; int n,k;while(true)cout 请输入硬币的个数 n;int qMax; int i;for( i=1;i=n;i+)qi=2; k=rand()%n;if(k=0)k=n;qk=1;cout随机产生的硬币排列顺序endl;for(i=1;i=n;i+)coutqi ;if(i%5=0)coutendl;co

3、utendl;int p=findTheCoin(q,1,n);cout伪造硬币的位置：pendl;cout=endl;int quantity(int q,int a,int b) int total=0;int i;for( i=a;i=b;i+)total+=qi;return total;int findTheCoin(int q,int a,int b) if(a=b)return a;int n=b-a+1;int c=n%3;int m=a+n/3-1;int d;switch(c)case 0: if (quantity(q,a,m)=quantity(q,m+1,m+n/3)

4、d=findTheCoin(q,m+n/3+1,m+2*(n/3);return d;else if (quantity(q,a,m)=quantity(q,m+n/3+1,m+2*(n/3)d=findTheCoin(q,m+1,m+n/3);return d;else d=findTheCoin(q,a,m);return d;/break;case 1:if( (quantity(q,a,m)=quantity(q,m+1,m+n/3) & (quantity(q,m+n/3+1,m+2*(n/3)=quantity(q,m+1,m+n/3) )return m+2*(n/3)+1;el

5、se if (quantity(q,a,m)=quantity(q,m+1,m+n/3)d=findTheCoin(q,m+n/3+1,m+2*(n/3);return d;else if (quantity(q,a,m)=quantity(q,m+n/3+1,m+2*(n/3)d=findTheCoin(q,m+1,m+n/3);return d;else d=findTheCoin(q,a,m);return d;/break;case 2: if(qm+2*(n/3)+1=qm+2*(n/3)+2)if (quantity(q,a,m)=quantity(q,m+1,m+n/3)d=fi

6、ndTheCoin(q,m+n/3+1,m+2*(n/3);return d;else if (quantity(q,a,m)=quantity(q,m+n/3+1,m+2*(n/3)d=findTheCoin(q,m+1,m+n/3);return d;elsed=findTheCoin(q,a,m);return d;else if(qm+2*(n/3)+2=q1)return m+2*(n/3)+1;/cout伪造硬币的号码是3*m+1endl;else return m+2*(n/3)+2;/cout伪造硬币的号码是3*m+2endl;/return true;（2）运行结果2.【找零

7、钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。（1）源程序：#include#includeint makeChange(int money,int coin25,int coin10,int coin5,int coin1)int i=0,j=0;while(money)if(money=25) i=money/25;if(i=coin25)money=money-25*i;j+=i;cout需要25美分i个!endl;elsemoney=m

8、oney-25*coin25;j+=coin25;cout需要25美分coin25个!=10)i=money/10;if(i=coin10)money=money-10*i;j+=i;cout需要10美分i个!endl;elsemoney=money-10*coin10;j+=coin10;cout需要10美分coin10个!=5) i=money/5;if(i=coin5)money=money-5*i;j+=i;cout需要5美分i个!endl;elsemoney=money-5*coin5;j+=coin5;cout需要5美分coin5个!=1)i=money/1;if(i=coin1)

9、money=money-1*i;j+=i;cout需要1美分i个!endl;elsecout!endl;cout! 零钱不够，无法找零! !endl;cout! 请退出后重新操作! !endl;cout!endl;return 0;cout共需要j个硬币!endl;return 1;void main()int money,smoney,ymoney;int coin25,coin10,coin5,coin1;cout欢迎使用，按0可退出!endl;cout请输入各面值硬币的个数:endl;coutcoin25;coutcoin10;coutcoin5;coutcoin1;while(true

10、)coutymoney;if(ymoney=0)break;coutsmoney;money=smoney-ymoney;cout您要找money美分!endl;if(money=0)continue;makeChange(money,coin25,coin10,coin5,coin1);cout=endl;（2）运行结果四、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验感想找零钱问题生活中也很常见，问题也很简单，所以变成没有费很大力气。伪造硬币问题因为涉及到函数的递归调用，所以在编程时在递归调用函数时结果的返回出了

11、许多错误，先检查了自己的算法，弄清思路是没有问题的，可能在写程序时犯了一些逻辑错误，后来经过一组测试数据，自己在纸上模拟程序单步执行，终于找到了自己犯得错误，问题迎刃而解。实验二 算法实现二一、 实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、 实验内容:掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握0-1背包问题的三种算法，并分析其优缺点。三、 实验题1. 0-1背包问题的贪心算法（1）源程序#include #define max 100 void sort (int n,float amax,float bmax) in

12、t j,h,k; float t1,t2,t3,cmax; for(k=1;k=n;k+) ck=ak/bk; for(h=1;hn;h+) for(j=1;j=n-h;j+) if(cjcj+1) t1=aj;aj=aj+1;aj+1=t1; t2=bj;bj=bj+1;bj+1=t2; t3=cj;cj=cj+1;cj+1=t3; void knapsack(int n,float limitw,float vmax,float wmax,int xmax) float c1;int i; sort(n,v,w);cout货物按价值密度排序后为：endl;cout价值：;for(i=1;i

13、=n;i+)coutvi ;coutendl重量：;for(i=1;i=n;i+)coutwi ;c1=limitw; for(i=1;ic1)continue; xi=1; c1=c1-wi; void main() int n,i,xmax; float vmax,wmax,totalv=0,totalw=0,limitw; while(true)cout请输入货物数量:n; cout背包最大载重:limitw; for(i=1;i=n;i+) xi=0; cout请依次输入物品的价值：endl; for(i=1;ivi; cout请依次输入物品的重量：endl; for(i=1;iwi;

14、 knapsack (n,limitw,v,w,x); coutendl装载结果为:;for(i=1;i=n;i+) coutxi ; if(xi=1) totalw=totalw+wi;totalv=totalv+vi; coutendl;cout背包的总重量为：totalwendl; cout背包的总价值为：totalvendl; cout=endl;（2）运行结果2. 0-1背包问题的动态规划算法（1）源程序#includeint c10100;int knapsack(int wmax,int n)int i,j,w10,p10;cout请输入每个物品的重量：endl;for(i=1;

15、iwi;cout请输入每个物品的价值：endl;for(i=1;ipi;for(i=0;i10;i+)for(j=0;j100;j+)cij=0;for(i=1;i=n;i+)for(j=1;j=wmax;j+)if(wici-1j)cij=pi+ci-1j-wi;elsecij=ci-1j;elsecij=ci-1j;return(cnwmax);int main()int wmax,n,i,j;cout请输入背包的载重：wmax;cout请输入货物数量：n;cout装载的最大价值为：knapsack(wmax,n)endl;return 0;（2）运行结果3. 0-1背包问题的回溯算法（1

16、）源程序#includeusing namespace std; class Knap friend 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;/当前

17、最优值 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) for(int j=1;j=n;j+) bestxj=xj; bestp=cp; return; if(cw+wibestp)/搜索右子树 xi=0; Backtrack(i+1); class Object friend int Kna

18、psack(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; fo

19、r( 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(); de

20、lete 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; /char k; while(true) cout请输入背包容量：c; cout请输入物品的个数：n; p=new intn+1; w=new intn+1; p0=0; w0=0; cout请输入物品的价值：endl;for(i=1;ipi; cout请输入物品的重量：endl; for(i=1;iwi;cout最优解为：endl;/cout最优值为(bestp)：endl;coutKnapsack(p,w,c,n)endl; cout=endl;/couts 重新开始endl; /coutq 退出k; （2）运行结果四、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、 实验感想 贪心算法只考虑眼前的利益而不考虑长远利益，得到的可能不是最优解，所以编程时一步一步顺着走下来就好了，相对简单。在编写0-1背包回溯和动态算法的程序时，最重的是先捋清思路，比如在纸上画一棵树，根据算法走一遍，搞清楚每一步是怎么走的，参数怎么变化等，最好在纸上一步一步记录清楚，编程时避免很多错误。