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

《算法分析与设计》实验指导书 《算法分析与设计》实验指导书 《算法分析与设计》课程是计算机专业的一门必修课程。开设算法分析与设 计实验 目的就是为了使学生消化理论知识 加深对讲授内容的理解 尤其是一 些算法的实现及其应用 培养学生独立编程和调试程序的能力 使学生对算法的 分析与设计有更深刻的认识。 《算法分析与设计》课程实验的目的：是为了使学生在课程学习的同时，通 过实验环境中的实际操作 对部分算法的具体应用有一个初步的了解 使学生加 深了解和更好地掌握《算法分析与设计》课程教学大纲要求的内容。 《算法分析与设计》课程实验的注意事项：在《算法分析与设计》的课程实 验过程中，要求学生做到： (1) 预习实验指导书有关部分 认真做好实验内容的准备 就实验可能出 现的情况提前作出思考和分析。 (2) 认真书写实验报告。实验报告包括实验目的和要求 实验情况及其分 析。 (3) 遵守机房纪律，服从辅导教师指挥，爱护实验设备。 (4) 实验课程不迟到。如有事不能出席，所缺实验一般不补。 《算法分析与设计》课程实验的验收：实验的验收将分为两个部分。第一部 分是上机操作 包括检查程序运行和即时提问。第二部分是提交电子的实验报告。 第 1 页 《算法分析与设计》实验指导书 实验一 算法实现一 一、 实验目的与要求 熟悉 C/C++语言的集成开发环境； 通过本实验加深对分治法、贪心算法的理解。 二、 实验内容: 掌握分治法、贪心算法的概念和基本思想 并结合具体的问题学习如何用相应策略进行 求解的方法。 三、 实验题 1. 【伪造硬币问题】给你一个装有 n 个硬币的袋子。n 个硬币中有一个是伪造的。你的 任务是找出这个伪造的硬币。为了帮助你完成这一任务 将提供一台可用来比较两组硬 币重量的仪器 利用这台仪器 可以知道两组硬币的重量是否相同。试用分治法的思想 写出解决问题的算法，并计算其时间复杂度。 2. 【找零钱问题】一个小孩买了价值为 33 美分的糖 并将 1 美元的钱交给售货员。售 货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为 25 美分、10 美分、 5 美分、及 1 美分的硬币。给出一种找零钱的贪心算法。 a) 实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。 四、 实验程序 五、 实验结果 六、 实验分析 第 2 页 《算法分析与设计》实验指导书 1 本实验运用分治算法。可将硬币分成 N 堆来进行实验 若分成两堆算法思想如下 步骤一、令 x 等于 n. 步骤二、若 x 为偶数 则将袋子中的硬币一分为二 即各x/2 个放仪器上比较两组硬币的重量,那 组较轻伪造的硬币就在该组。若 n 等于 2,则结束，因为已经找出伪造硬币。否 则 令 n=n/2，执行步骤一。 否则 取出一个硬币后 再把剩下的 x-1 个硬币进行分组，每组(x-1)/2 个硬币；并 放在仪器上比较两组的重量，若两组一样重 则刚才拿出来的硬币为伪造的；否 则 伪造的硬币在较轻的那一组。若 n 等于 2,则结束 因为已经找出伪造硬币。 否则 令 n=(x-1)/2，执行步骤一。 时间复杂度。因为以上算法应用的是二分法的思想 每次比较排除 1/2 的真硬币。 所以其时间复杂度为 O(n)。 分成三堆思想 /*总体思想：将所有的硬币分成三堆，通过比较三堆的质量找出与其他两组不同 的一组，伪造的硬币一定在这一组中。写程序时还须注意硬币号