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

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

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

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

3、通过木实验加深对分治法、贪心算法的理解。二、实验内容：掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何川相应策略进行求解的方法。三、实验题1.【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台对用来比较两组硕币垂量的仪器，利川这台仪器，可以知道两组硬币的垂量是否相同。试川分治法的思想写出解决问题的算法,并计算其时间复杂度。2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数

4、目最少的硬币找给小孩。假设捉供了数目有限的而值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。a）实验步骤理解算法思想和问题要求；编程实现题冃要求；上机输入和调试白己所编的程序；验证分析实验结果；整理出实验报告。四、实验程序五、实验结果六、实验分析1木实验运用分治算法。可将硬币分成N堆来进行实验若分成两堆算法思想如下步骤一、令x等于n.步骤二、若x为偶数，则将袋子中的硬币一分为二，即各x/2个放仪器上比较两组硬币的重量，那组较轻伪造的硬币就在该组。若n等于2,则结束，因为已经找出伪造

5、硬币。否则，令n=n/2,执行步骤一。否则，取出一个硬币后，再把剩下的x・1个硬币进行分组，每组(x-1)/2个硬币；并放在仪器上比较两组的重量，若两组一-样重，则刚才拿出来的硬币为伪造的；否则，伪造的硬币在较轻的那一组。若n等于2,则结束，因为已经找出伪造硬币。否则，令n=(x-1)/2,执行步骤一。吋间复杂度。因为以上算法应用的是二分法的思想,每次比较排除1/2的真硬币。所以其时间复杂度为0(n)。分成三堆思想广总体思想：将所有的皎币分成三堆，通过比较三堆的质量找出与其他两组不同的一组，伪造的硬币一定在

6、这一组小。写程序时述须注意硬币号所以一共有三种可能性：1•侦币刚好能分成三堆，即破币的数冃能被3整除。这样只需要比较哪堆便币质量和其他的两组质量不一样，不一样的那组是有伪造硬币的那组。2硕币的数目被3整除余1。再将这一种情况分成两种情况考虑：3•三组硬币质量和等，则剩下的硬币是伪造的。b.三组硬币质量不等，则情况与1一致。3•硕币数目被3整除余2o也将这一种情况分成两种情况考虑：a.三组硬币质量相等，则伪造的硬币一定在剩下的两个硬币当屮。从三组硬币屮任意取岀一个与剩下的两个硬币比较质量，则质量与其他两个不相

7、等的硬币是伪造的。b.三组硬币质量不等，则情况与1一致。*/实验二算法实现二一、实验目的与要求熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和凹溯算法的理解。二、实验内容:学握贪心算法、动态规划和回溯算法的概念和基木思想，分析并学握”0-1“背包问题的三种算法，并分析其优缺点。三、实验题1.“0-1”背包问题的贪心算法2.“0・1”背包问题的动态规划算法3.“0-1”背包问题的回溯算法四、实验步』理解算法思想和问题要求;编程实现题冃要求；上机输入和调试白己所编的程辰验证分析实验结果；整

8、理出实验报告。五、实验程序六、实验结果七、实验分析