《《算法分析与设计》 实验指导书.doc》由会员分享，可在线阅读，更多相关《《算法分析与设计》 实验指导书.doc（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析与设计 实验指导书算法分析与设计课程是计算机专业的一门必修课程。开设算法分析与设计实验，目的就是为了使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。算法分析与设计课程实验的目的：是为了使学生在课程学习的同时，通过实验环境中的实际操作，对部分算法的具体应用有一个初步的了解，使学生加深了解和更好地掌握算法分析与设计课程教学大纲要求的内容。算法分析与设计课程实验的注意事项：在算法分析与设计的课程实验过程中，要求学生做到：(1) 预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出现的情况
2、提前作出思考和分析。(2) 认真书写实验报告。实验报告包括实验目的和要求，实验情况及其分析。(3) 遵守机房纪律，服从辅导教师指挥，爱护实验设备。(4) 实验课程不迟到。如有事不能出席，所缺实验一般不补。算法分析与设计课程实验的验收：实验的验收将分为两个部分。第一部分是上机操作，包括检查程序运行和即时提问。第二部分是提交电子的实验报告。实验一 算法实现一一、 实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对分治法、贪心算法的理解。二、 实验内容:掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。三、 实验题1. 【伪造硬币问题】给你一个装有n
3、个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算其时间复杂度。2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。a) 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。四、 实验程序五、 实验结果六、 实
4、验分析1本实验运用分治算法。可将硬币分成N堆来进行实验若分成两堆算法思想如下步骤一、令x等于n.步骤二、若x为偶数， 则将袋子中的硬币一分为二，即各x/2个放仪器上比较两组硬币的重量,那组较轻伪造的硬币就在该组。若n等于2,则结束，因为已经找出伪造硬币。否则，令n=n/2，执行步骤一。否则， 取出一个硬币后，再把剩下的x-1个硬币进行分组，每组(x-1)/2个硬币；并放在仪器上比较两组的重量，若两组一样重，则刚才拿出来的硬币为伪造的；否则，伪造的硬币在较轻的那一组。若n等于2,则结束，因为已经找出伪造硬币。否则，令n=(x-1)/2，执行步骤一。时间复杂度。因为以上算法应用的是二分法的思想，每
5、次比较排除1/2的真硬币。所以其时间复杂度为O(n)。分成三堆思想/*总体思想：将所有的硬币分成三堆，通过比较三堆的质量找出与其他两组不同的一组，伪造的硬币一定在这一组中。写程序时还须注意硬币号所以一共有三种可能性： 1.硬币刚好能分成三堆，即硬币的数目能被3整除。这样只需要比较哪堆硬币质量和其他的两组质量不一样，不一样的那组是有伪造硬币的那组。 2.硬币的数目被3整除余1。再将这一种情况分成两种情况考虑： a.三组硬币质量相等，则剩下的硬币是伪造的。 b.三组硬币质量不等，则情况与1一致。 3.硬币数目被3整除余2。也将这一种情况分成两种情况考虑： a.三组硬币质量相等，则伪造的硬币一定在剩
6、下的两个硬币当中。从三组硬币中任意取出一个与剩下的两个硬币比较质量，则质量与其他两个不相等的硬币是伪造的。 b.三组硬币质量不等，则情况与1一致。*/实验程序如下#include #include using namespace std;void findTheCoin(int a, int n ,int num); /找硬币函数的声明int quantity(int q,int n ); / 计算硬币质量函数的声明void main() const int n=70; /定义硬币的总数是70枚 int qn; /定义硬币数组 int i; for( i=0;in;i+) qi=1; /给硬币
7、的重量赋值，正常的硬币的重量是1 q4=0; /定义第4枚硬币是伪造的，质量是0 findTheCoin(q, n,0); /调用找硬币的函数 int quantity(int q, int n) /计算硬币的质量，把一组中所有的硬币的质量都加起来 int total=0; int i; for( i=0;in;i+) total+=qi; return total;void findTheCoin(int q,int n,int num) /找硬币 int c=n%3; /分成三组的余数 int m=n/3; int i; int *q1,*q2,*q3; q1=(int*)malloc(m
8、*sizeof(int); q2=(int*)malloc(m*sizeof(int); q3=(int*)malloc(m*sizeof(int); for(i=0;im;i+) q1i=qi; q2i=qm+i; q3i=q2*m+i; /把硬币分成三组,每组M个,第一组开始标号为I ,第二组M+I,第三组2M+I; switch(c) case 0: /余数为0的情况 if (quantity(q1,m)=quantity(q2,m) findTheCoin(q3,m,num+2*m); else if (quantity(q1,m)=quantity(q3,m) findTheCoin
9、(q2,m,num+m); else findTheCoin(q1,m,num); break; case 1: /余数为1的情况 if( (quantity(q1,m)=quantity(q2,m) & (quantity(q3,m)=quantity(q2,m) ) cout伪造硬币的号码是num+nendl; else if (quantity(q1,m)=quantity(q2,m) findTheCoin(q3,m,num+2*m); else if (quantity(q1,m)=quantity(q3,m) findTheCoin(q2,m,num+m); else findTh
10、eCoin(q1,m,num); break; case 2: /余数为2的情况 if(qn-1=qn-2)/若余出的两个硬币重量相等 if (quantity(q1,m)=quantity(q2,m) findTheCoin(q3,m,num+2*m); else if (quantity(q1,m)=quantity(q3,m) findTheCoin(q2,m,num+m); else findTheCoin(q1,m,num); else if(qn-1=q1)/若第N-1个与第一个相等,则第二个是伪硬币 cout伪造硬币的号码是n-2+numendl; else cout伪造硬币的号
11、码是n-1+numendl; 2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。对于给定的数额，用面值25、10、5、2、1的硬币找零，要求所用硬币总数最少。C+实现，算法如下：#include #include using namespace std;int main() int a,b25,b10,b5,b2,b1; cout 请输入要找的零钱:a; b25=(a/25); b10=(a%25)/10; b5=(a%25)%10/5;
12、 b2=(a%25)%10%5/2; b1=(a%25)%10%5%2; cout需要以下几枚零钱:endl;if(b25!=0)cout25分的b25枚endl;if(b10!=0)cout10分的b10枚endl;if(b5!=0)cout5分的b5枚endl;if(b2!=0)cout2fendeb2meiendl;if(b1!=0) cout 1分的b1枚 endl;return(0);实验二 算法实现二一、 实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、 实验内容:掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握0-1背包问题的三种算法，并分析其优缺点。三、 实验题1. 0-1背包问题的贪心算法2. 0-1背包问题的动态规划算法3. 0-1背包问题的回溯算法四、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、 实验程序六、 实验结果七、 实验分析