算法设计与分析实验三

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

2、安排一场比赛，请你帮助学生会安排首轮循环赛的比赛日程表。2. 【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序（1）循环赛日程安排实验代码#include viostream> using namespace std; int a1616; void copysc (int x1,int y1,int x2

3、,int y2,int n); void scap(int x,int y,int n); void scjs(int x,int y,int n); int main()int i,j;a00=1；初始化两个人的赛程安排a01=2;a10=2;a11=1；scap(0,0,16);for(i=0;ivl6;i+) 输出结果for(j=0;j<16;j+) coutvvaijvv""coutvvendl;/每 行结尾处换行return 0;void scap(int x,int y,int n)if(n=2)/如果只有两个人直接返回结果 return; else/否则

4、二分n=n/2;scap(0,0,n);/递归调用自己scjs(0,n,n);/由已安排的部分算出并行的没安排的 copysc (0,0,n,n,n);/左上部分复制到右下部分 copysc(0,n,n,0,n);右上部分复制到左下部分void copysc(int x1,int y1,int x2,int y2,int n)实现复制int i,j;for(i=0;i<n;i+) for(j=0;j<n;j+) ax2+iy2+j=ax1+iy1+j;void scjs (int x,int y,int/计算并行的赛事用于复制int i,j;for(i=0;i<n;i+)fo

5、r(j=0;j<n;j+) aij+n=aij+n;/ 数字规律 (2)找零钱问题实验代码#include<iostream>using namespace std;int main ()int a=100,b=33,c=a-b;int money4=25,10,5,1;/把可用的钱按从大到小存入数组int num4=0;用于记录每种钱要用多少次for(int i=0;i<4;i+)numi=c/moneyi;每次去计算当前最大可用的最大的钱要用多少 c=c%moneyi;还应找的钱for(int i=0;i<4;i+)/ 输出结果if(numi!=0)coutv

6、vmoneyivv"美分应找"vvnumivv"个"vvendl;return 0;六、实验结果1循环赛日程安排问题实验结果3 4 54 3 62 71 812911 121314151618 9 12 111413161511 12 9 101516131412 1191615141313 14 15 16910111214 13 16 1510912111513 141112:91016 15 14 13121110 915 16 1 23 456? 877 88 75 &3 44 31 21112?15 161314341278512111

7、0916613141516911125G7S1231413161510 91211SE872141516131411 12910?8563411615141312 1110 9765432慣按任意键继续4 344 3 2 112 13 1411 14 13 16 15 27S?85610 11L10 9 122找零钱问题实验结果七、 实验分析分治法 就是把一个复杂的问题分成两个或更多的相同或相似的 子问题，再把子问题分成更小的子问题，直到最后问题可以简单的直 接求解，原问题的解即子问题的解的合并。实验中的16名选手赛程安排，可以先二分。用scap函数进行分治，当人数比

8、较大时，n=n/2, 然后递归调用自己，实现人数减少的分治。当人数比较少时，n=2,可以直接初始化。合并子问题用到scjs函数与copysc函数，先用scjs 函数利用人数少时已经安排的赛程计算并行的赛程for(i=0;ivn;i+)for(j=0；j<n;j+)aij+n=aij+n;即用左上部分计算出右上部分最后用copy函数把已经安排的赛程合并到没安排的部分copysc (0,0, n,n,n);/左上部分复制到右下部分copysc(0, n,n ,0, n);/右上部分复制到左下部分实现对整个赛事的安排。贪心法 在对问题求解时，总是做出当前看来最好的选择，他所做 出的仅是某种意义上的局部最优解。贪心法要有最优量度标准，最优解可以通过一系列局部最优的选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解，然后再去解做出这个选择后产生 的相应的子问题。每做一次选择就将所求问题简化为一个规模更小的 子问题，最终可得到问题的一个整体最优解。由此原理，要使找的硬 币数目最小，就得尽量找最大的硬币。所以把硬币按从