1、課程實(shí)驗(yàn)報(bào)告課程名稱算法分析與設(shè)計(jì)班級(jí)計(jì)算161實(shí)驗(yàn)日期2018/5/06姓名何嚴(yán)鴻學(xué)號(hào)201607019實(shí)驗(yàn)成績(jī)實(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ù)問(wèn)題問(wèn)題描述：給定n位正整數(shù)a,去掉其中任意k n個(gè)數(shù)字后，剩下的數(shù)字按原次序排列組成一個(gè)新的正整數(shù)。對(duì)于給定的n位正整數(shù)a和正整數(shù)k,設(shè)一個(gè)算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。輸入(A行為a,第二行為k):6579431483輸出：543148(2)線段覆蓋問(wèn)題描述：在一維空間中告訴你N條線段的

2、起始坐標(biāo)與終止坐標(biāo)，要求求出這些線段一共覆蓋了多大的長(zhǎng)度。輸入：4/表示輸入的線段個(gè)數(shù)2 5/線段起始坐標(biāo)線段終止坐標(biāo)6 71 33 4輸出:51.調(diào) 試 過(guò) 程 及2.(2)把求解的問(wèn)題分成若干個(gè)問(wèn)題。6579431483 543142 C:U5ersctien經(jīng)過(guò)這次實(shí)驗(yàn)，對(duì)貪心法有了更深的了解。貪心算法的基本思路如下:建立數(shù)學(xué)建模來(lái)描述問(wèn)題。對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解。(4)把子問(wèn)題的局部最優(yōu)解合成原來(lái)問(wèn)題的一個(gè)解。實(shí)現(xiàn)該算法的過(guò)程如下:從問(wèn)題的某一初始解出發(fā)。(2)while 能向給定總目標(biāo)前進(jìn)rH o(3)求出可行解的一個(gè)解元素。(4)由所有解元素組合問(wèn)題的一個(gè)可行解。

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ù)字的個(gè)數(shù)i=-1;/從頭開(kāi)始查遞減區(qū)間)if(i=l-x-2&xs)m=1;/已經(jīng)無(wú)遞減區(qū)間，m=1脫離循環(huán))coutn.substr(0,l-s+x)endl;只打印剩下的左邊 l-(s-x)個(gè)數(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)生了覆蓋。此時(shí)還要更新last坐標(biāo)(length=di.r-di-1.l;last=di.r; )else if (di.r=last) /線段 di的左坐標(biāo)在 Last 之后，此時(shí) last之后的部分不會(huì)對(duì)之前的部分產(chǎn)生影響，更新 last坐標(biāo)。length的值加上之