算法分析与设计试验报告试验5：贪心算法的应用

1、课程实验报告课程名称算法分析与设计班级计算161实验日期2018/5/06姓名何严鸿学号201607019实验成绩实验名称实验5:贪心算法的应用实验目的及要求.理解贪心算法的概念；.掌握贪心算法的基本思想。实 验 环 境操作系统：WindowsIDE： Visual C+实 验 内 容(1)删数问题问题描述：给定n位正整数a,去掉其中任意k n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k,设一个算法找出剩下数字组成的新数最小的删数方案。输入(A行为a,第二行为k):6579431483输出：543148(2)线段覆盖问题描述：在一维空间中告诉你N条线段的

2、起始坐标与终止坐标，要求求出这些线段一共覆盖了多大的长度。输入：4/表示输入的线段个数2 5/线段起始坐标线段终止坐标6 71 33 4输出:51.调 试 过 程 及2.(2)把求解的问题分成若干个问题。6579431483 543142 C:U5ersctien经过这次实验，对贪心法有了更深的了解。贪心算法的基本思路如下:建立数学建模来描述问题。对每一子问题求解，得到子问题的局部最优解。(4)把子问题的局部最优解合成原来问题的一个解。实现该算法的过程如下:从问题的某一初始解出发。(2)while 能向给定总目标前进rH o(3)求出可行解的一个解元素。(4)由所有解元素组合问题的一个可行解。

3、1.#include #include using namespace std;int main()string n;int s,i,x,l,m;while(cinns)(i=-1,m=0,x=0;l=n.length();while(xni+1)/出现递减，删除递减的首数字(n=n.erase(i,1);x+;/ x统计删除数字的个数i=-1;/从头开始查递减区间)if(i=l-x-2&xs)m=1;/已经无递减区间，m=1脱离循环)coutn.substr(0,l-s+x)endl;只打印剩下的左边 l-(s-x)个数字)return 0;)2.#include#include#inclu

4、de using namespace std;struct point(int l,r;d1100006;bool cmp(const struct point &a,const struct point &b)(return a.rn;for(int i=0;idi.r)swap(di.l,di.r);sort(d,d+n,cmp);/按纵坐标升序排列last=d0.r;/记录当前线段被覆盖的最大坐标值for(int i=1;in;i+)(if(di.l=last)线段 di的右坐标在 last 之后,左坐标在Last之前的情况，即产生了覆盖。此时还要更新last坐标(length=di.r-di-1.l;last=di.r; )else if (di.r=last) /线段 di的左坐标在 Last 之后，此时 last之后的部分不会对之前的部分产生影响，更新 last坐标。length的值加上之