算法设计与分析实验三(贪心与分治)

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

1、南华大学计算机科学与技术学院实验报告南华大学计算机科学与技术学院实验报告（200~200学年度第学期）课程名称算法分析与设计实验名称贪心法与分治法姓名刘文东学号20104030327专业计算机技术班级10级03班地点8-209教师余颖老师南华大学计算机科学与技术学院实验报告实验三分治与贪心一、实验目的与要求熟悉C/C++语言的集成开发环境；通过本实验加深对分治法、贪心算法的理解。二、实验内容:掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。三、实验题1.【循环赛日程安排问题】计算机学院准备举办一次男生羽毛球单打比赛，现

2、在总共有16名选手报名，首轮比赛准备采取循环赛的形式进行角逐，要求必须在15天内比完，且每个选手每天只能安排一场比赛，请你帮助学生会安排首轮循环赛的比赛日程表。2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序（1）循环赛日程安排实验代码#includeu

3、singnamespacestd;inta[16][16];voidcopysc(intx1,inty1,intx2,inty2,intn);voidscap(intx,inty,intn);voidscjs(intx,inty,intn);intmain()南华大学计算机科学与技术学院实验报告{inti,j;a[0][0]=1;//初始化两个人的赛程安排a[0][1]=2;a[1][0]=2;a[1][1]=1;scap(0,0,16);for(i=0;i<16;i++)//输出结果{for(j=0;j<16;j++)cout<

4、out<

5、;i++)for(j=0;jusingnamespacestd;intmain(){inta=100,b=33,c=a-b;南华大学计算机科学与技术学院实验报告intmoney[4]={25,10,5,1};//把可用的钱按

6、从大到小存入数组intnum[4]={0};//用于记录每种钱要用多少次for(inti=0;i<4;i++){num[i]=c/money[i];//每次去计算当前最大可用的最大的钱要用多少c=c%money[i];//还应找的钱}for(inti=0;i<4;i++)//输出结果{if(num[i]!=0)cout<

7、的相同或相似的子问题，再把子问题分成更小的子问题，直到最后问题可以简单的直接求解，原问题的解即子问题的解的合并。实验中的16名选手赛程安排，可以先二分。用scap函数进行分治，当人数比较大时，n=n/2,然后递归调用自己，实现人数减少的分治。当人数比较少时，n=2，可以直接初始化。合并子问题用到scjs函数与copysc函数，先用scjs函数利用人数少时已经安排的赛程计算并行的赛程for(i=0;i

8、分copysc(0,0,n,n,n);//左上部分复