算法分析與設(shè)計(jì)試驗(yàn)報(bào)告試驗(yàn)5：貪心算法的應(yīng)用

1、課程實(shí)驗(yàn)報(bào)告課程名稱算法分析與設(shè)計(jì)班級計(jì)算161實(shí)驗(yàn)日期2018/5/06姓名何嚴(yán)鴻學(xué)號201607019實(shí)驗(yàn)成績實(shí)驗(yàn)名稱實(shí)驗(yàn)5:貪心算法的應(yīng)用實(shí)驗(yàn)?zāi)康募耙?理解貪心算法的概念；.掌握貪心算法的基本思想。實(shí) 驗(yàn) 環(huán) 境操作系統(tǒng)：WindowsIDE： Visual C+實(shí) 驗(yàn) 內(nèi) 容(1)刪數(shù)問題問題描述：給定n位正整數(shù)a,去掉其中任意k n個數(shù)字后，剩下的數(shù)字按原次序排列組成一個新的正整數(shù)。對于給定的n位正整數(shù)a和正整數(shù)k,設(shè)一個算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。輸入(A行為a,第二行為k):6579431483輸出：543148(2)線段覆蓋問題描述：在一維空間中告訴你N條線段的

2、起始坐標(biāo)與終止坐標(biāo)，要求求出這些線段一共覆蓋了多大的長度。輸入：4/表示輸入的線段個數(shù)2 5/線段起始坐標(biāo)線段終止坐標(biāo)6 71 33 4輸出:51.調(diào) 試 過 程 及2.(2)把求解的問題分成若干個問題。6579431483 543142 C:U5ersctien經(jīng)過這次實(shí)驗(yàn)，對貪心法有了更深的了解。貪心算法的基本思路如下:建立數(shù)學(xué)建模來描述問題。對每一子問題求解，得到子問題的局部最優(yōu)解。(4)把子問題的局部最優(yōu)解合成原來問題的一個解。實(shí)現(xiàn)該算法的過程如下:從問題的某一初始解出發(fā)。(2)while 能向給定總目標(biāo)前進(jìn)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)/出現(xiàn)遞減，刪除遞減的首數(shù)字(n=n.erase(i,1);x+;/ x統(tǒng)計(jì)刪除數(shù)字的個數(shù)i=-1;/從頭開始查遞減區(qū)間)if(i=l-x-2&xs)m=1;/已經(jīng)無遞減區(qū)間，m=1脫離循環(huán))coutn.substr(0,l-s+x)endl;只打印剩下的左邊 l-(s-x)個數(shù)字)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);/按縱坐標(biāo)升序排列l(wèi)ast=d0.r;/記錄當(dāng)前線段被覆蓋的最大坐標(biāo)值for(int i=1;in;i+)(if(di.l=last)線段 di的右坐標(biāo)在 last 之后,左坐標(biāo)在Last之前的情況，即產(chǎn)生了覆蓋。此時還要更新last坐標(biāo)(length=di.r-di-1.l;last=di.r; )else if (di.r=last) /線段 di的左坐標(biāo)在 Last 之后，此時 last之后的部分不會對之前的部分產(chǎn)生影響，更新 last坐標(biāo)。length的值加上之