數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--貪心算法的設(shè)計(jì)

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p><b>　　貪心算法</b></p><p><b>　　任務(wù)調(diào)度問(wèn)題</b></p><p><b>　　目 錄</b></p><p>　　1 課程設(shè)計(jì)目的及要求1</p><p>

2、<b>　　2課題總體設(shè)計(jì)1</b></p><p>　　2.1系統(tǒng)流程圖2</p><p>　　2.2功能模塊圖3</p><p>　　2.3 概念設(shè)計(jì)3</p><p><b>　　2.3邏輯設(shè)計(jì)4</b></p><p><b>　　4詳細(xì)設(shè)計(jì)4&

3、lt;/b></p><p>　　4.1 for循環(huán)模塊設(shè)計(jì)4</p><p>　　4.2 希爾排序模塊設(shè)計(jì)5</p><p>　　4.3輸出調(diào)度結(jié)果模塊設(shè)計(jì)7</p><p><b>　　5調(diào)試與測(cè)試9</b></p><p><b>　　6小結(jié)11</b>

4、</p><p><b>　　參考文獻(xiàn)13</b></p><p><b>　　附 錄14</b></p><p>　　附錄1 源程序清單14</p><p><b>　　貪心算法的設(shè)計(jì)</b></p><p>　　1 課程設(shè)計(jì)目的及要求

5、 </p><p>　?。?）、課程設(shè)計(jì)的內(nèi)容及目的</p><p>　　有n項(xiàng)任務(wù)，要求按順序執(zhí)行，并設(shè)定第i項(xiàng)任務(wù)需要t[i]單位時(shí)間。如果任務(wù)完成的順序?yàn)?,2，……，n，那么第i項(xiàng)任務(wù)完成的時(shí)間為c[i]=t[1]+…+t[i],平均完成時(shí)間（Average Completion Time, ACT）即為（c[1]+…c[n]）/n。本題要求找到最小的任務(wù)平均完成時(shí)間。</p

6、><p>　　本實(shí)驗(yàn)的目的是設(shè)計(jì)一個(gè)程序，并且通過(guò)運(yùn)用貪心算法來(lái)解決該題的任務(wù)調(diào)度問(wèn)題。認(rèn)識(shí)且熟練運(yùn)用貪心算法，掌握貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。清晰了解運(yùn)用貪心算法解決任務(wù)調(diào)度問(wèn)題的步驟。</p><p><b>　?。?）、要求</b></p><p><b>　　輸入要求：</b></p><p&g

7、t;　　輸入數(shù)據(jù)中包含幾個(gè)測(cè)試案例。每一個(gè)案例的第一行給出不大于2000000的整數(shù)n，接著下面一行開始列出n個(gè)非負(fù)整數(shù)t（t<=1000000000）,每個(gè)數(shù)之間用空格相互隔開，以一個(gè)負(fù)數(shù)來(lái)結(jié)束輸入。</p><p><b>　　輸出要求：</b></p><p>　　對(duì)每一個(gè)測(cè)試案例，打印它的最小平均完成時(shí)間，并精確到0.01。每個(gè)案例對(duì)應(yīng)的輸出結(jié)果都占一行

8、。若輸出某一個(gè)案例中任務(wù)數(shù)目n=0，則對(duì)應(yīng)輸出一個(gè)空行。</p><p><b>　　輸入例子：</b></p><p><b>　　4</b></p><p><b>　　4 2 8 1</b></p><p><b>　　-1</b></p>

9、;<p>　　表示有四個(gè)任務(wù)，各自完成需要的時(shí)間單位分別為4,2,8,1，第三行輸入-1表示輸入結(jié)束。</p><p><b>　　輸出例子：</b></p><p>　　要求程序運(yùn)行后的輸出結(jié)果為:6.50。 </p><p><b>　　2課題總體設(shè)計(jì)</b></p><p>

10、　　這個(gè)題目屬于貪心算法應(yīng)用中任務(wù)調(diào)度問(wèn)題。要得到所有任務(wù)的平均完成時(shí)間，只需要將各個(gè)任務(wù)完成時(shí)間從小到排序，任務(wù)實(shí)際完成需要的時(shí)間等于它等待的時(shí)間與自身執(zhí)行需要的時(shí)間之和。這樣給出的調(diào)度是按照最短作業(yè)優(yōu)先進(jìn)行來(lái)安排的。</p><p><b>　　2.1系統(tǒng)流程圖</b></p><p><b>　　2.2功能模塊圖</b></p>

11、<p><b>　　2.3 概念設(shè)計(jì)</b></p><p>　　貪心算法通過(guò)一系列的選擇來(lái)得到一個(gè)問(wèn)題的解。它所做的每一個(gè)選擇都是當(dāng)前狀態(tài)下某種意義的最好選擇，即貪心選擇。在許多可以用貪心算法求解的問(wèn)題中一般具有兩個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最有子結(jié)構(gòu)性質(zhì)。所謂貪心選擇性只是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到，這是貪心算法可行的第一基本要素。

12、對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所做的貪心選擇最終將會(huì)得到問(wèn)題的一個(gè)整體最優(yōu)解。首先考察問(wèn)題的一個(gè)整體最優(yōu)解，并證明可修改這個(gè)最優(yōu)解，使其以貪心選擇開始。而且做了貪心選擇后，原問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的類似子問(wèn)題。然后，用數(shù)學(xué)歸納法證明，通過(guò)每一步做貪心選擇，最終可得到問(wèn)題的一個(gè)整體最優(yōu)解。其中，證明貪心選擇后問(wèn)題簡(jiǎn)化為規(guī)模更小的類似子問(wèn)題的關(guān)鍵在于利用該問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)。當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含著它的子問(wèn)

13、題最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這個(gè)性質(zhì)是該問(wèn)題可用貪心算法求解的一個(gè)關(guān)鍵特征。</p><p><b>　　2.3邏輯設(shè)計(jì)</b></p><p>　　這個(gè)題目屬于貪心算法應(yīng)用中任務(wù)調(diào)度問(wèn)題。要得到所有任務(wù)的平均完成時(shí)間，只需要將各個(gè)任務(wù)完成時(shí)間從小到排序，任務(wù)實(shí)際完成需要的時(shí)間等于它等待的時(shí)間與自身執(zhí)行需要的時(shí)間之和。這樣給出的調(diào)度是按照最短作業(yè)優(yōu)先進(jìn)行來(lái)

14、安排的。</p><p><b>　　4詳細(xì)設(shè)計(jì)</b></p><p>　　4.1 for循環(huán)模塊設(shè)計(jì)</p><p>　　明確了可以用最短作業(yè)優(yōu)先的思想后，就可以正式來(lái)設(shè)計(jì)題目的實(shí)現(xiàn)了。首先，輸入的測(cè)試案例可以有很多組，每一個(gè)案例的輸入格式都是第一行輸入任務(wù)的個(gè)數(shù)，然后下面一行輸入每一個(gè)任務(wù)需要的時(shí)間單位，輸入完成另起一行，可以再繼續(xù)輸入下

15、一個(gè)案例的數(shù)據(jù)。最后用一個(gè)任意的負(fù)數(shù)來(lái)表示輸入的結(jié)束。這樣，由于案例的個(gè)數(shù)開始不得知，所以可以套用一個(gè)for循環(huán)，如下所示</p><p>　　for(n=0;n>=0;) /*當(dāng)n小于0的時(shí)候，退出程序*/</p><p><b>　　{</b></p><p>　　scanf(“%1d”,&n);</p><

16、;p><b>　　if(n>0)</b></p><p><b>　　{</b></p><p>　　建立一個(gè)具有n個(gè)元素的數(shù)組；</p><p>　　for（i=0;i<n;i++）</p><p><b>　　{</b></p><p&

17、gt;　　繼續(xù)讀入這個(gè)n作業(yè)的完成時(shí)間；</p><p><b>　　}</b></p><p>　　進(jìn)行主要的調(diào)度運(yùn)算；</p><p>　　輸入得到的最優(yōu)調(diào)度結(jié)果；</p><p><b>　　}</b></p><p>　　else if(n==0)</p>

18、<p><b>　　{</b></p><p><b>　　輸入一個(gè)空行；</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　所以，對(duì)每組輸入，其基本過(guò)程是：讀入n個(gè)任務(wù)的運(yùn)行時(shí)間，進(jìn)

19、行主要的調(diào)度運(yùn)算。</p><p>　　4.2 希爾排序模塊設(shè)計(jì)</p><p>　?。?）、排序：將數(shù)組按照從小到大排序。</p><p>　　排序的方法很多，如：冒泡排序、希爾排序、堆排序等，這些排序的方法都可以使用。這里采用希爾排序來(lái)實(shí)現(xiàn)。</p><p>　　它的基本思想是：先取一個(gè)小于n的整數(shù)作為第一個(gè)增量；這里選取n的一半作為第一

20、個(gè)增量（increment=n>>1），把數(shù)組的全部元素分成個(gè)組。所有距離為的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量<重復(fù)上述的分組和排序，直至所取的增量=1（<<…<<）,即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。該方法?shí)質(zhì)上是一種分組插入排序方法。希爾排序如下所示</p><p>　　void Shellsort(long *a,l

21、ong n)</p><p><b>　　{</b></p><p>　　long i,j,increment;</p><p>　　long temp;</p><p>　　/*第一個(gè)增量值為n/2，以后每一次的增量都是上一個(gè)增量值的一半*/</p><p>　　for(increment =n

22、>>1;increment>0;increment>>1)</p><p>　　/*每次的步長(zhǎng)都是通過(guò)n值又移位來(lái)得到的*/</p><p><b>　　{</b></p><p>　　for(i=increment;i<n;i++)</p><p><b>　　{</

23、b></p><p>　　/*對(duì)每一組里面的元素進(jìn)行插入排序*/</p><p>　　temp= *(a+i);</p><p>　　for(j=i;j>=increment;j-=increment)</p><p><b>　　{</b></p><p>　　if(temp<

24、*(a +(j-increment)))</p><p>　　*(a+j)=*(a+(j-increment));</p><p><b>　　else</b></p><p><b>　　break;</b></p><p><b>　　}</b></p>&l

25、t;p>　　*(a+j)=temp;</p><p><b>　　} </b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　計(jì)算總的平均完成時(shí)間：排序完成后，數(shù)組a中的元素以升序的方式排列，因此總的平均完成時(shí)間為&l

26、t;/p><p><b>　　ACT=</b></p><p>　　4.3輸出調(diào)度結(jié)果模塊設(shè)計(jì)</p><p>　　由于輸出的結(jié)果要求精確到0.01，所以輸出的時(shí)候需要采用以下輸出格式。</p><p>　　double r[100]; /*依次存放每個(gè)案例的ACT*/</p><p><b

27、>　　……</b></p><p>　　printf(“%.2f\n”,r[i]);</p><p>　　/*輸出的結(jié)果要求精確到0.01*/</p><p>　　另外，程序?qū)崿F(xiàn)的時(shí)候，要求用戶一次可以輸入一組或者多組測(cè)試案例的數(shù)據(jù)，當(dāng)用戶的輸入完成后，程序經(jīng)過(guò)計(jì)算在屏幕上分行顯示這幾個(gè)案例結(jié)果。因此，在有多個(gè)測(cè)試案例的情況下，需要設(shè)置一個(gè)數(shù)組，用

28、來(lái)存放每一組測(cè)試案例的計(jì)算結(jié)果，如下所示</p><p>　　double r[100]; /*用來(lái)存放每個(gè)測(cè)試案例的計(jì)算結(jié)果*/</p><p><b>　　j=0;</b></p><p>　　for(對(duì)每一個(gè)測(cè)試案例)</p><p><b>　　{</b></p><p

29、>　　把計(jì)算得到的最有調(diào)度時(shí)間存入r[j]中；</p><p><b>　　j++;</b></p><p><b>　　} </b></p><p>　　/*當(dāng)輸入的n值為負(fù)數(shù)時(shí)，跳出上面的for循環(huán)*/</p><p><b>　　for(從0到j(luò))</b></

30、p><p><b>　　{</b></p><p>　　if(r[i]==-1)printf(“\n”); /*輸出一個(gè)空行*/</p><p>　　else printf(“%.2f\n”,r[i]); /*輸出的結(jié)果要求精確到0.01*/</p><p><b>　　}</b></p>

31、;<p><b>　　5調(diào)試與測(cè)試</b></p><p>　　調(diào)試方法，測(cè)試結(jié)果的分析與討論，測(cè)試過(guò)程中遇到的主要問(wèn)題及采取的解決措施</p><p>　　這個(gè)程序主要需要測(cè)試一下幾個(gè)方面：</p><p>　　當(dāng)任務(wù)個(gè)數(shù)為0時(shí)，需要對(duì)應(yīng)輸出一個(gè)空行。</p><p>　　當(dāng)輸入的作業(yè)數(shù)目大于200000

32、0，或者單個(gè)作業(yè)完成的時(shí)間大于1000000000的時(shí)候，程序要求報(bào)錯(cuò)。</p><p>　　另外，當(dāng)任務(wù)數(shù)比較大的時(shí)候，輸入對(duì)應(yīng)的任務(wù)時(shí)間時(shí)要仔細(xì)，務(wù)必保證輸入的任務(wù)個(gè)數(shù)與要求的任務(wù)數(shù)一致。如果出現(xiàn)輸入的任務(wù)數(shù)與n值不相符時(shí)，程序會(huì)報(bào)錯(cuò)，輸出“input error！”的錯(cuò)誤。</p><p>　　下圖5.1-5.3為執(zhí)行使各種不同的正確結(jié)果：</p><p>&

33、lt;b>　　圖5.1</b></p><p><b>　　圖5.2</b></p><p><b>　　圖5.3</b></p><p>　　在開始編譯的時(shí)候不是很順利，出現(xiàn)了各種不同的小錯(cuò)誤比如忘記分號(hào)，小括號(hào)等等。經(jīng)過(guò)一一修改后開始執(zhí)行。因?yàn)閷?duì)該程序不是特別熟悉總是輸入錯(cuò)誤不知怎么輸入。后來(lái)經(jīng)過(guò)查書

34、和同學(xué)討論最終完成執(zhí)行這個(gè)階段。</p><p>　　以下幾幅圖是我執(zhí)行時(shí)發(fā)現(xiàn)的錯(cuò)誤：</p><p><b>　　圖5.4</b></p><p>　　該圖錯(cuò)誤的原因是，已知輸入5個(gè)任務(wù)但是輸入的時(shí)間單位只有4個(gè)。</p><p><b>　　圖5.5</b></p><p&g

35、t;　　該圖錯(cuò)誤的原因是，已知輸入5個(gè)任務(wù)但是輸入的時(shí)間單位卻有6個(gè)。</p><p><b>　　圖5.6</b></p><p>　　該圖的錯(cuò)誤原因是，作業(yè)數(shù)目大于200000。</p><p><b>　　6小結(jié)</b></p><p>　　這周的課程設(shè)計(jì)就要結(jié)束了。從最開始的選題到現(xiàn)在的報(bào)告

36、總結(jié)我完成了一個(gè)過(guò)程。在這個(gè)過(guò)程里我領(lǐng)悟了很多。</p><p>　　開始上實(shí)驗(yàn)課的時(shí)候老師給我們這樣一個(gè)題目，當(dāng)時(shí)感覺(jué)挺好笑的挺奇怪的。因?yàn)楫?dāng)時(shí)我根本就沒(méi)有聽過(guò)談心算法這個(gè)詞，“貪心”貌似都是在生活中被提起但是突然出現(xiàn)在我的課程設(shè)計(jì)中感覺(jué)挺好玩的。后來(lái)貪心算法基本知識(shí)的閱讀我才了解什么叫貪心算法，如何應(yīng)用貪心算法來(lái)解決問(wèn)題。這是我感覺(jué)一切的方法都來(lái)源于生活，再難懂的問(wèn)題通過(guò)生活的解釋都變得言簡(jiǎn)意賅。雖然在中間寫

37、的過(guò)程中還有很多不會(huì)的東西，但是通過(guò)查看書本和資料還有問(wèn)同學(xué)，基本上都解決了。但仍然有一些有待提高的地方，比如在排序前后的結(jié)果比較和如果運(yùn)行時(shí)間長(zhǎng)的任務(wù)在等待很長(zhǎng)時(shí)間都沒(méi)有運(yùn)行等較高的要求還沒(méi)有解決。</p><p>　　我覺(jué)得課程設(shè)計(jì)的作用一方面是最基本的就是要完成這一科目，差不多也是對(duì)自己的一個(gè)階段性的總結(jié)；還有就是在整個(gè)設(shè)計(jì)的過(guò)程中，讓我們認(rèn)真的獨(dú)立思考，在和同學(xué)交流的過(guò)程中也增強(qiáng)了我們的語(yǔ)言組織能力和彼此

38、之間的友誼。通過(guò)課程設(shè)計(jì)讓我們不斷的發(fā)現(xiàn)自己的不足從而去改善，這是一種學(xué)習(xí)的態(tài)度，不僅僅是在這次的課程設(shè)計(jì)中，在以后的無(wú)論生活還是學(xué)習(xí)方面都應(yīng)該注意和努力改善。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 劉振安,劉燕君.C程序設(shè)計(jì)課程設(shè)計(jì)[M].[北京]機(jī)械工業(yè)出版社,2004年9月</p><p>　　[2]

39、譚浩強(qiáng).C程序設(shè)計(jì)（第三版）.清華大學(xué)出版社,2005年7月</p><p>　　[3] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.清華大學(xué)出版社,1997年4月</p><p>　　[4] 何欽銘，陳根才.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).浙江大學(xué)出版社，2007年8月</p><p>　　[5] 魏寶鋼，陳越，王申康.數(shù)據(jù)結(jié)構(gòu)與算法分析.浙江大學(xué)出版社，2004</p>

40、<p>　　[6] Mark Allen Weiss,陳越改編.Data Structures and Algorithm Analysis in C(second edition).人民郵電出版社，2005</p><p>　　[7] [美]S巴斯.計(jì)算計(jì)算法：設(shè)計(jì)和分析引論.朱洪等譯.復(fù)旦大學(xué)出版社，1985</p><p>　　[8] Donovan JJ.Operat

41、ing System.McGraw-Hill,Inc.,1976</p><p>　　[9] Gotlieb CC,Gotlieb L R.Data Types and Structures. Prentice-Hall Inc,1978</p><p>　　[10]姚施斌 .數(shù)據(jù)庫(kù)系統(tǒng)基礎(chǔ) .計(jì)算機(jī)工程應(yīng)用，1981年第8期</p><p><b>　　

42、附 錄</b></p><p><b>　　附錄1 源程序清單</b></p><p>　　#include <stdio.h></p><p>　　void Shellsort( long *a, long n );</p><p>　　int main()</p><

43、p><b>　　{</b></p><p>　　long n,i,j;</p><p>　　long *a,*b;</p><p>　　double r[100];/**** 用來(lái)存放每個(gè)測(cè)試案例的計(jì)算結(jié)果 ***/</p><p>　　j=0;/*** 記錄測(cè)試案例的個(gè)數(shù) ***/</p><

44、p>　　/*****讀入用戶的輸入，若當(dāng)前輸入為負(fù)數(shù)，則程序終止******/</p><p>　　for( n = 0; n >= 0 ; )</p><p><b>　　{</b></p><p>　　scanf( "%ld", &n );</p><p>　　if(n >

45、; 2000000){</p><p>　　printf("too much for the project!\n");</p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p>　　if( n > 0 )</p&g

46、t;<p><b>　　{</b></p><p>　　b = (long*)malloc( n * sizeof( long ) );</p><p><b>　　a = b;</b></p><p>　　for(i=0; i< n ; i++)</p><p><b&g

47、t;　　{</b></p><p>　　scanf( "%ld", b+i );</p><p>　　/*** 檢查輸入的數(shù)據(jù)是否大于1000 000 000****/</p><p>　　if(*(b+i) > 1000000000){</p><p>　　printf("too much f

48、or the project!\n");</p><p>　　exit(0);</p><p><b>　　}</b></p><p>　　/*** 對(duì)輸入中出現(xiàn)任務(wù)時(shí)間為負(fù)數(shù)的異常處理 ******/</p><p>　　if(*(b+i)<0)</p><p><

49、;b>　　{</b></p><p>　　printf("input error！\n");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　} </b><

50、;/p><p>　　Shellsort( b, n );</p><p>　　/***** 計(jì)算平均完成時(shí)間 *****/</p><p>　　for( i = n, r[j] = 0.0; i > 0 ; i--,a++ )</p><p><b>　　{</b></p><p>　　r[j]

51、+= (double)*a/(double)n * i; </p><p><b>　　}</b></p><p><b>　　j++;</b></p><p>　　free( b );</p><p><b>　　}</b></p><p>　　/**

52、* 當(dāng)n為0時(shí)，標(biāo)志相應(yīng)的r數(shù)組值為－1，輸出時(shí)碰到－1則輸出一個(gè)空行***/</p><p>　　else if ( n == 0 )</p><p><b>　　{</b></p><p>　　r[j++]=-1;</p><p><b>　　}</b></p><p&g

53、t;<b>　　}</b></p><p>　　for(i=0;i<j;i++)</p><p><b>　　{</b></p><p>　　if(r[i]==-1)printf("\n");/** 輸出一個(gè)空行 **/ </p><p><b>　　else

54、</b></p><p>　　printf( "%.2f\n", r[i] );/** 輸出的結(jié)果要求精確到0.01 **/ </p><p><b>　　}</b></p><p><b>　　return 1;</b></p><p><b&

55、gt;　　}</b></p><p>　　/*** 希爾排序方法 ***/</p><p>　　void Shellsort( long *a, long n )</p><p><b>　　{</b></p><p>　　long i, j, increment;</p><p>　

56、　long temp;</p><p>　　/** 第一個(gè)增量值為(n/2)，以后每一次的增量都是上一個(gè)增量值的一半 **/</p><p>　　for( increment = n>>1; increment>0; increment>>=1 )</p><p><b>　　{</b></p>&l

57、t;p>　　for(i = increment; i < n; i++)</p><p><b>　　{</b></p><p>　　temp = *(a+i);</p><p>　　for(j = i; j>=increment; j-= increment)</p><p><b>　　{

58、</b></p><p>　　if( temp < *(a + (j-increment)) )</p><p>　　*(a+j)= *( a+ (j-increment) );</p><p><b>　　else</b></p><p><b>　　break;</b><