《算法分析与设计》课程实验
实验报告
专业：计算机科学与技术班级：姓名：学号：
f《算法分析与设计》实验报告
完成时间：2009年6月15日
1
f《算法分析与设计》实验报告
实验一算法实现一
一、实验目的与要求
熟悉CC语言的集成开发环境；通过本实验加深对分治法、贪心算法的理解。
二、实验内容
掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。
三、实验题
1【伪造硬币问题】给你一个装有
个硬币的袋子。
个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算其时间复杂度。2【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。
四、实验步骤
理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。
五、实验程序1伪造硬币问题
2
f《算法分析与设计》实验报告
源程序：
c语言实现
i
cludestdioh
i
cludestdlibh
i
cludemathh
defi
eN100
defi
eN112
只能判断是否相等的天平
voidsolvei
tcoi
i
tcou
ti
tfirsti
tlast
ifcou
t2
pri
tf