实验三 分治与贪心.docx
《实验三 分治与贪心.docx》由会员分享，可在线阅读，更多相关《实验三 分治与贪心.docx（13页珍藏版）》请在冰点文库上搜索。
实验三分治与贪心
南华大学
计算机科学与技术学院
实验报告
（2012~2013学年度第2学期）
课程名称
算法设计与分析
实验名称
分治与贪心
姓名
古古天
学号
xx
姓名
xx
学号
xx
姓名
xx
学号
xx
班级
软卓01班
教师
余xx
实验三分治与贪心
一、实验目的与要求
熟悉C/C++语言的集成开发环境；
通过本实验加深对分治法、贪心算法的理解。
二、实验内容:
掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。
三、实验题
1.【删数】给定一个n位正整数A，去掉其中任意k（k<=n）个数字后，剩下的数字按原次序排列组成一个新的正整数，对于给定的n位正整数A和正整数k，找出剩下数字组成的新数最小的删数方案。
例如，给定的n位正整数为A为276841，k为4，则删数后最小的新数为21。
2.【循环赛日程安排问题】计算机学院准备举办一次男生羽毛球单打比赛，现在总共有16名选手报名，首轮比赛准备采取循环赛的形式进行角逐，要求必须在15天内比完，且每个选手每天只能安排一场比赛，请你帮助学生会安排首轮循环赛的比赛日程表。
3.（*选做）【钓鱼】豆豆有h（1<=h<=16）个小时的空闲时间，他打算去钓鱼。
豆豆钓鱼的地方共有n（2<=n<=25）个湖，所有的湖沿着一条单向路顺序排列（豆豆每在一个湖钓完鱼后，他只能走到下一个湖继续钓），豆豆必须从1号湖开始钓起，但是他可以在任何一个湖结束他此次钓鱼的行程。
ti（0例如，t3=4意味着，从第3个湖到第4个湖需要花费20分钟。
为了帮助他拟定钓鱼之旅，豆豆收集了一些有关湖泊的信息：
在每个湖中每5分钟钓的鱼数（此题中以5分钟作为单位时间）随时间的增长而线性递减。
每个湖中头5分钟可以钓到的鱼数fi（fi>=0）以及每个湖中相邻5分钟钓鱼数的减少量di（di>=0），输入中均会给出。
求一种方案，使得豆豆在有限的h小时中可以钓到尽可能多的鱼。
输入：
第一行为一个整数n，表示有n个湖，第二行为一个整数h，表示有h个小时，第三行有n个整数表示每个湖中头5分钟可以钓到的鱼数fi，接下来一行n个整数表示每个湖中相邻5分钟钓鱼数的减少量di，最后一行为n-1个整数描述顺序的相邻湖之间的路程所要花费的时间ti。
输出：
输出在各个湖分别呆多长时间（已分钟计且应为5的倍数），以及钓鱼的总数量。
四、实验步骤
理解算法思想和问题要求；
编程实现题目要求；
上机输入和调试自己所编的程序；
验证分析实验结果；
整理出实验报告。
五、实验程序
实验题1程序：
#include
#include
usingnamespacestd;
intmain（）
{
strings;
intn;
while（cin>>s）
{
cin>>n;
if（n>s.length（））//异常处理
cout<<"ERROR"<elseif（n==s.length（））//异常处理
cout<<0<else
{
while（n--）
{
for（inti=0;ii++;
s.erase（i,1）;//删除从位置i开始的1个字符
}
while（s.length（）>1&&s[0]=='0'）//删数结束,处理第一位为零的情况
s.erase（0,1）;
cout<}
}
return0;
}
实验题2程序：
#include
#include
usingnamespacestd;
constintN=1000;
inta[1000][1000];
voidgetresult（inta[][N],intk）
{
intn=1,m=1,i;
for（i=1;i<=k;i++）
n*=2;
for（i=0;ia[i][0]=i+1;
for（ints=0;s{
n/=2;
for（intt=0;t{
for（intj=m;j<2*m;j++）
for（inti=m;i<2*m;i++）//十字形交叉赋值
{
a[i-m+2*t*m][j]=a[i+2*t*m][j-m];
a[i+2*t*m][j]=a[i-m+2*t*m][j-m];
}
}
m*=2;
}
}
intmain（）
{
cout<<"输入比赛队伍数：
";
intn,k,i;
while（cin>>n&&n）
{
k=0;
for（i=n;i>=1;i=i/2）
k++;
getresult（a,k）;
for（i=0;i{
for（intj=0;jcout<（2）<cout<}
cout<<"输入比赛队伍数（输入0结束）：
";
}
return0;
}
实验题3程序：
#include
usingnamespacestd;
structget_fish
{
intfish_num;//5分钟可以钓到的鱼数
intdis;//5分钟钓鱼数的减少量
intcount;//记录每个湖的钓鱼时间
}fish[26],fish1[26];
intget_max（get_fisha[],intn）
{
intmax=1;
for（inti=2;i<=n;i++）
{
if（a[max].fish_nummax=i;
}
//cout<<"m="<returnmax;
}
intcost[26];//第i个湖到第i+1个湖的时间
intmain（）
{
intn;//n个湖
inth;//h个小时
inttemp=0;
while（cin>>n&&n）
{
temp++;
cin>>h;
inttime=h*12;//小时换算为若干个5分钟
inti,sum_fish=0;
for（i=1;i<=n;i++）
cin>>fish[i].fish_num;
for（i=1;i<=n;i++）
cin>>fish[i].dis;
for（i=1;icin>>cost[i];
for（intm=1;m<=n;m++）//钓完前m个湖
{
inttemp_time=time;
for（i=1;i<=n;i++）
{
fish1[i].fish_num=fish[i].fish_num;
fish1[i].dis=fish[i].dis;
fish1[i].count=0;
}
//cout<<"m="<inttemp_fish=0;
intfish_lake=0;//在哪个湖钓鱼
for（i=1;itemp_time=temp_time-cost[i];
//cout<<"time0="<for（i=temp_time;i>0;i--）//时间逐步减少,直至时间耗尽
{
//cout<<"time="<fish_lake=get_max（fish1,m）;//得到当前最大钓鱼数
temp_fish=temp_fish+fish1[fish_lake].fish_num;
//cout<<"temp_fish="<fish1[fish_lake].fish_num=fish1[fish_lake].fish_num-fish1[fish_lake].dis;//减少下个5分钟钓的鱼数
fish1[fish_lake].count++;//记录钓鱼次数
if（fish1[fish_lake].fish_num<0）//钓鱼数不能为负数
fish1[fish_lake].fish_num=0;
}
if（temp_fish>sum_fish）
{
for（i=1;i<=n;i++）
fish[i].count=fish1[i].count;
sum_fish=temp_fish;
}
//cout<<"temp_fish="<}
if（temp!
=1）
cout<for（i=1;i<=n;i++）
{
if（i==1）
cout<else
cout<<","<}
cout<cout<<"Numberoffishexpected:
"<}
return0;
}
六、实验结果
实验题1结果：
实验题2结果：
（说明：
上图给出的是n个选手的比赛日程表，其中第一列表示1-n个选手，第2列到第n列表示各个选手在第1天到第n-1天的所遇到的选手。
）
实验题3结果：
七、实验分析
1．实验题1逐步删除最大数，若干次循环后，就可以得到目的数。
是简单贪心的应用。
2．实验题2是采用的分治方法，考虑好后，即可解决。
3．实验题3需要思索一番，找到贪心的条件，即以逐步增加钓鱼的湖数为贪心条件，这样就可以假设在任何时间，他可以移动到任何想去的湖，而移动的过程无需时间。
只需在每个5分钟的开始“瞬间移动”到当前5分钟中能钓到最多的鱼的湖中，且只钓5分钟的鱼。
这样逐步积累，等到时间耗尽时，就得到一次分治条件下的最大钓鱼数。
最后，分治完成，得到最大钓鱼数。
升级会员 