实验3__分治与贪心

《实验3__分治与贪心》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验三分治与贪心一、实验目的熟悉C/C++语言的集成开发环境；通过本实验加深对分治法、贪心算法的理解。二、实验内容掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。三、实验要求1.【循环赛日程安排问题】计算机学院准备举办一次男生羽毛球单打比赛，现在总共有16名选手报名，首轮比赛准备采取循环赛的形式进行角逐，要求必须在15天内比完，且每个选手每天只能安排一场比赛，请你帮助学生会安排首轮循环赛的比赛日程表。2.【找零钱问题】一个小孩买了价值为33美分的糠，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提

2、供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给岀一种找零钱的贪心算法。四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序1・#include#includevoidTable(intk){inta[20][20];intq,n=1;for(inti=1;iv=k;i++)n*=2;q=n；for(inti=1;i<=n;i++)a[1][i]=i;intm=1;for(ints=1;sv=k;s++){n/=2;for(

3、intt=1;t<=n;t++)for(inti=m+1;i<=2*m;i++)for(intj=m+1;j<=2*m;j++){a[i]0+(t-1)*m*2]=a[i-m]0+(t-1)*m*2-m];a[i]0+(t-1)*m*2-m]=a[i-m]0+(t-1)*m*2];}m*=2;}for(inti=1;i<=q;i++){for(intj=1;j<=q;j++)printf("%dH,a[i][j])；printfOn");}}voidmain(){intk=4;Table(k);systemC'pause");}2.#include

4、tream>usingstd::cout;usingstd::endl;intmain(){ints=100-33;inta=25;intb=10;intc=5;intd=1;intcout1=0;intcout2=0;intcout3=0;intcout4=0;for(s;s>=a;cout1++)s=s-a;for(s;s>=b;cout2++)s=s-b;for(s;s>=c;cout3++)s=s-c;for(s;s>=d;cout4++)s=s-d;if(s==O)coutvv”找M«cout1«M个25美分的硬币”vvendl«""«cout2

5、«H个［0美分的硬币”vvendl«""«cout3«"个5美分的硬币"vvendl«""«cout4«"个1美分的硬币”vvendl;}systemC'pause");return0;}六.实验结果C:UserspcDocummts…L口回I找2个25美分的硬币l-f-10美分的硬币1<--5O的碑币2^1美分的硬币请按任・・・HF七、实验分析分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题,以便各个击破，分而治之。分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为

6、k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。分治法在每一层递归上都有三个步骤：1.将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；2.若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题合并：将各个子问题的解合并为原问题的解。贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能

7、产生整体最优解或者是整体最优解的近似解。贪心算法的基本思路：1•建立数学模型来描述问题。2.把求解的问题分成若干个子问题。1.对每一子问题求解，得到子问题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。