算法分析與設計試驗報告試驗5：貪心算法的應用

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

2、起始坐標與終止坐標，要求求出這些線段一共覆蓋了多大的長度。輸入：4/表示輸入的線段個數(shù)2 5/線段起始坐標線段終止坐標6 71 33 4輸出:51.調 試 過 程 及2.(2)把求解的問題分成若干個問題。6579431483 543142 C:U5ersctien經(jīng)過這次實驗，對貪心法有了更深的了解。貪心算法的基本思路如下:建立數(shù)學建模來描述問題。對每一子問題求解，得到子問題的局部最優(yōu)解。(4)把子問題的局部最優(yōu)解合成原來問題的一個解。實現(xiàn)該算法的過程如下:從問題的某一初始解出發(fā)。(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)/出現(xiàn)遞減，刪除遞減的首數(shù)字(n=n.erase(i,1);x+;/ x統(tǒng)計刪除數(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);/按縱坐標升序排列l(wèi)ast=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的值加上之