《算法分析与设计》 实验指导书

《《算法分析与设计》 实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法分析与设计》实验指导书《算法分析与设计》课程是计算机专业的一门必修课程。开设算法分析与设计实验，目的就是为了使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。《算法分析与设计》课程实验的目的：是为了使学生在课程学习的同时，通过实验环境中的实际操作，对部分算法的具体应用有一个初步的了解，使学生加深了解和更好地掌握《算法分析与设计》课程教学大纲要求的内容。《算法分析与设计》课程实验的注意事项：在《算法分析与设计》的课程实验过程中，要求学生做到：(1)预习实验

2、指导书有关部分，认真做好实验内容的准备，就实验可能出现的情况提前作出思考和分析。(2)认真书写实验报告。实验报告包括实验目的和要求，实验情况及其分析。(3)遵守机房纪律，服从辅导教师指挥，爱护实验设备。(4)实验课程不迟到。如有事不能出席，所缺实验一般不补。《算法分析与设计》课程实验的验收：实验的验收将分为两个部分。第一部分是上机操作，包括检查程序运行和即时提问。第二部分是提交电子的实验报告。实验一算法实现一一、实验目的与要求熟悉C/C++语言的集成开发环境；通过本实验加深对分治法、贪心算法的理解。二、实验内容:掌握分治法、贪心算法的概念和基本思想，并结

3、合具体的问题学习如何用相应策略进行求解的方法。三、实验题1.【伪造硬币问题】给你一个装有n个硬币的袋子。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个硬币；并放在仪器上比较两组的重量，若两组一样重，则刚才拿出来的硬币为伪造的；否则

5、，伪造的硬币在较轻的那一组。若n等于2,则结束，因为已经找出伪造硬币。否则，令n=(x-1)/2，执行步骤一。时间复杂度。因为以上算法应用的是二分法的思想，每次比较排除1/2的真硬币。所以其时间复杂度为O(n)。分成三堆思想/*总体思想：将所有的硬币分成三堆，通过比较三堆的质量找出与其他两组不同的一组，伪造的硬币一定在这一组中。写程序时还须注意硬币号所以一共有三种可能性：1.硬币刚好能分成三堆，即硬币的数目能被3整除。这样只需要比较哪堆硬币质量和其他的两组质量不一样，不一样的那组是有伪造硬币的那组。2.硬币的数目被3整除余1。再将这一种情况分成两种情况考

6、虑：a.三组硬币质量相等，则剩下的硬币是伪造的。b.三组硬币质量不等，则情况与1一致。3.硬币数目被3整除余2。也将这一种情况分成两种情况考虑：a.三组硬币质量相等，则伪造的硬币一定在剩下的两个硬币当中。从三组硬币中任意取出一个与剩下的两个硬币比较质量，则质量与其他两个不相等的硬币是伪造的。b.三组硬币质量不等，则情况与1一致。*/实验程序如下#include#includeusingnamespacestd;voidfindTheCoin(inta[],intn,intnum);//找硬币函数的声明intquan

7、tity(intq[],intn);//计算硬币质量函数的声明voidmain(){constintn=70;//定义硬币的总数是70枚intq[n];//定义硬币数组inti;for(i=0;i

8、q[i];returntotal;}voidfindTheCoin(intq[]