算法分析与设计实验报告 完整版.doc

《算法分析与设计》 课程实验 实验报告 专业：计算机科学与技术 班级： 姓名： 学号： 完成时间：2009年6月15日  实验一 算法实现一 实验目的与要求 熟悉C/C++语言的集成开发环境； 通过本实验加深对分治法、贪心算法的理解。 实验内容: 掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。 实验题 1. 【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算其时间复杂度。 2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。 实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。 实验程序 伪造硬币问题 源程序： //c语言实现 #include stdio.h #includestdlib.h #includemath.h #define N 100 #define N1 12 //只能判断是否相等的天平 void solve(int coin[],int count,int first,int last) { if (count==2) { printf(无法判断\n); return; } if (first==last) {//只有一个硬币时候 printf(假币的序号为%d, 假币的重量为%d\n, first, coin[first]); } else if(last-first==1){ //如果只剩下两个硬币（此时count不为） if (first 0) { //不是最开始的硬币 if (coin[first] == coin[0]) //如果第first和第个相等，说明first位置不是伪币 solve(coin,count,first+1,last); else //否则，说明first位置是伪币 solve(coin,count,first,last-1); } else if(lastcount-1){ //不是最后的硬币 if (coin[first]==coin[count-1]) //如果第first和最后一个相等，说明last位置不是伪币 solve(coin,count,first+1,last); else //否则，说明first位置是伪币 solve(coin,count,first,last-1); } } else if (firstlast){ int temp=(last-first+1)/3; //将硬币分为三组 int sum1=0, sum2=0; for(int i=0;itemp;i++){ sum1+=coin[first+i]; sum2+=coin[last-i]; } if (sum1==sum2){ //两边的总重相等,在中间，递归 solve(coin,count,first+temp,last-temp); } else {//在两边,不在中间 if (sum1==coin[first+temp]*temp){ //左边的和中间的相等,在右边，递归 solve(coin,count,last-temp+1,last); } else { solve(coin,count,first,first+temp-1); //右边的和中间的相等,在左边，递归 } } } } void main() { int i; int coin[N]; //定义数组coin用来存放硬币重量 for(i=0;i