实验三 分治与贪心.docx

1、实验三 分治与贪心南华大学计算机科学与技术学院实 验 报 告 （ 2012 2013学年度 第2学期 ）课程名称算法设计与分析实验名称分治与贪心姓名古古天学号xx姓名xx学号xx姓名xx学号xx班级软卓01班教师余xx实验三 分治与贪心一、 实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对分治法、贪心算法的理解。二、 实验内容:掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。三、 实验题1. 【删数】给定一个n位正整数A，去掉其中任意k (k=n)个数字后，剩下的数字按原次序排列组成一个新的正整数，对于给定的n位正整数A和正整数k，找出剩下

2、数字组成的新数最小的删数方案。例如，给定的n位正整数为A为276841，k为4，则删数后最小的新数为21。2. 【循环赛日程安排问题】计算机学院准备举办一次男生羽毛球单打比赛，现在总共有16名选手报名，首轮比赛准备采取循环赛的形式进行角逐，要求必须在15天内比完，且每个选手每天只能安排一场比赛，请你帮助学生会安排首轮循环赛的比赛日程表。3. (*选做)【钓鱼】豆豆有h（1=h=16）个小时的空闲时间，他打算去钓鱼。豆豆钓鱼的地方共有n（2=n=25）个湖，所有的湖沿着一条单向路顺序排列（豆豆每在一个湖钓完鱼后，他只能走到下一个湖继续钓）， 豆豆必须从1号湖开始钓起，但是他可以在任何一个湖结束他

3、此次钓鱼的行程。ti（0 ti =0）以及每个湖中相邻5分钟钓鱼数的减少量di（di=0），输入中均会给出。求一种方案，使得豆豆在有限的h小时中可以钓到尽可能多的鱼。输入：第一行为一个整数n，表示有n个湖，第二行为一个整数h，表示有h个小时，第三行有n个整数表示每个湖中头5分钟可以钓到的鱼数fi，接下来一行n个整数表示每个湖中相邻5分钟钓鱼数的减少量di，最后一行为n-1个整数描述顺序的相邻湖之间的路程所要花费的时间ti。输出：输出在各个湖分别呆多长时间（已分钟计且应为5的倍数），以及钓鱼的总数量。四、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实

4、验结果；整理出实验报告。五、 实验程序实验题1程序：#include #include using namespace std;int main() string s; int n; while(cins) cinn; if(ns.length()/异常处理 coutERRORendl; else if(n=s.length()/异常处理 cout0endl; else while(n-) for(int i=0; is.length()-1&si1&s0=0)/删数结束,处理第一位为零的情况 s.erase(0,1); coutsendl; return 0;实验题2程序：#include#

5、includeusing namespace std;const int N=1000;int a10001000;void getresult(int aN,int k) int n=1,m=1,i; for(i=1;i=k;i+) n*=2; for(i=0;in;i+)/比赛选手记录 ai0=i+1; for(int s=0; sk; s+) /k个阶段，从左到右 n/=2; for(int t=0; tn; t+) for(int j=m; j2*m; j+) for(int i=m; i2*m; i+) /十字形交叉赋值 ai-m+2*t*mj = ai+2*t*mj-m; ai+2

6、*t*mj = ai-m+2*t*mj-m; m *= 2; int main() coutn&n) k=0; for(i=n;i=1;i=i/2) k+; getresult(a,k); for(i=0;in;i+) for(int j=0;jn;j+) coutsetw(2)aij ; coutendl; cout输入比赛队伍数（输入0结束）：; return 0;实验题3程序：#includeusing namespace std;struct get_fish int fish_num;/5分钟可以钓到的鱼数 int dis;/5分钟钓鱼数的减少量 int count;/记录每个湖的钓

7、鱼时间fish26,fish126;int get_max(get_fish a,int n) int max=1; for(int i=2;i=n;i+) if(amax.fish_numai.fish_num) max=i; /coutm=maxtmax=amax.fish_numn&n) temp+; cinh; int time=h*12;/小时换算为若干个5分钟 int i,sum_fish=0; for(i=1;ifishi.fish_num; for(i=1;ifishi.dis; for(i=1;icosti; for(int m=1;m=n;m+)/钓完前m个湖 int te

8、mp_time=time; for(i=1;i=n;i+) fish1i.fish_num=fishi.fish_num; fish1i.dis=fishi.dis; fish1i.count=0; /coutm=mendl; int temp_fish=0; int fish_lake=0;/在哪个湖钓鱼 for(i=1;im;i+)/总时间减去钓完前m个湖在路途中花费的时间 temp_time=temp_time-costi; /couttime0=temp_time0;i-)/时间逐步减少,直至时间耗尽 /couttime=it; fish_lake=get_max(fish1,m);/

9、得到当前最大钓鱼数 temp_fish=temp_fish+fish1fish_lake.fish_num; /couttemp_fish=temp_fishendl; fish1fish_lake.fish_num=fish1fish_lake.fish_num-fish1fish_lake.dis;/减少下个5分钟钓的鱼数 fish1fish_lake.count+;/记录钓鱼次数 if(fish1fish_lake.fish_numsum_fish) for(i=1;i=n;i+) fishi.count=fish1i.count; sum_fish=temp_fish; /coutte

10、mp_fish=temp_fishendl; if(temp!=1) coutendl; for(i=1;i=n;i+) if(i=1) coutfishi.count*5; else cout, fishi.count*5; coutendl; coutNumber of fish expected: sum_fishendl; return 0;六、 实验结果实验题1结果：实验题2结果：（说明：上图给出的是n个选手的比赛日程表，其中第一列表示1-n个选手，第2列到第n列表示各个选手在第1天到第n-1天的所遇到的选手。）实验题3结果：七、 实验分析1实验题1逐步删除最大数，若干次循环后，就可以得到目的数。是简单贪心的应用。2实验题2是采用的分治方法，考虑好后，即可解决。3实验题3需要思索一番，找到贪心的条件，即以逐步增加钓鱼的湖数为贪心条件，这样就可以假设在任何时间，他可以移动到任何想去的湖，而移动的过程无需时间。只需在每个5分钟的开始“瞬间移动”到当前5分钟中能钓到最多的鱼的湖中，且只钓5分钟的鱼。这样逐步积累，等到时间耗尽时，就得到一次分治条件下的最大钓鱼数。最后，分治完成，得到最大钓鱼数。