數(shù)據(jù)結構課程設計--貪心算法的設計

1、<p>　　數(shù)據(jù)結構課程設計報告</p><p><b>　　貪心算法</b></p><p><b>　　任務調度問題</b></p><p><b>　　目 錄</b></p><p>　　1 課程設計目的及要求1</p><p>

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

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

4、</p><p><b>　　參考文獻13</b></p><p><b>　　附 錄14</b></p><p>　　附錄1 源程序清單14</p><p><b>　　貪心算法的設計</b></p><p>　　1 課程設計目的及要求

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

6、><p>　　本實驗的目的是設計一個程序，并且通過運用貪心算法來解決該題的任務調度問題。認識且熟練運用貪心算法，掌握貪心選擇性質和最優(yōu)子結構性質。清晰了解運用貪心算法解決任務調度問題的步驟。</p><p><b>　?。?）、要求</b></p><p><b>　　輸入要求：</b></p><p&g

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

8、。若輸出某一個案例中任務數(shù)目n=0，則對應輸出一個空行。</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>　　表示有四個任務，各自完成需要的時間單位分別為4,2,8,1，第三行輸入-1表示輸入結束。</p><p><b>　　輸出例子：</b></p><p>　　要求程序運行后的輸出結果為:6.50。 </p><p><b>　　2課題總體設計</b></p><p>

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

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

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

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

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

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

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

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

18、<p><b>　　{</b></p><p><b>　　輸入一個空行；</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　所以，對每組輸入，其基本過程是：讀入n個任務的運行時間，進

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

20、個增量（increment=n>>1），把數(shù)組的全部元素分成個組。所有距離為的倍數(shù)的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量<重復上述的分組和排序，直至所取的增量=1（<<…<<）,即所有記錄放在同一組中進行直接插入排序為止。該方法實質上是一種分組插入排序方法。希爾排序如下所示</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>　　/*第一個增量值為n/2，以后每一次的增量都是上一個增量值的一半*/</p><p>　　for(increment =n

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

23、b></p><p>　　/*對每一組里面的元素進行插入排序*/</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>　　計算總的平均完成時間：排序完成后，數(shù)組a中的元素以升序的方式排列，因此總的平均完成時間為&l

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

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

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

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

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

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

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

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

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

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

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

37、的過程中還有很多不會的東西，但是通過查看書本和資料還有問同學，基本上都解決了。但仍然有一些有待提高的地方，比如在排序前后的結果比較和如果運行時間長的任務在等待很長時間都沒有運行等較高的要求還沒有解決。</p><p>　　我覺得課程設計的作用一方面是最基本的就是要完成這一科目，差不多也是對自己的一個階段性的總結；還有就是在整個設計的過程中，讓我們認真的獨立思考，在和同學交流的過程中也增強了我們的語言組織能力和彼此

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

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

40、<p>　　[6] Mark Allen Weiss,陳越改編.Data Structures and Algorithm Analysis in C(second edition).人民郵電出版社，2005</p><p>　　[7] [美]S巴斯.計算計算法：設計和分析引論.朱洪等譯.復旦大學出版社，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ù)庫系統(tǒ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];/**** 用來存放每個測試案例的計算結果 ***/</p><p>　　j=0;/*** 記錄測試案例的個數(shù) ***/</p><

44、p>　　/*****讀入用戶的輸入，若當前輸入為負數(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>　　/*** 對輸入中出現(xiàn)任務時間為負數(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>　　/***** 計算平均完成時間 *****/</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、* 當n為0時，標志相應的r數(shù)組值為－1，輸出時碰到－1則輸出一個空行***/</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");/** 輸出一個空行 **/ </p><p><b>　　else

54、</b></p><p>　　printf( "%.2f\n", r[i] );/** 輸出的結果要求精確到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>　　/** 第一個增量值為(n/2)，以后每一次的增量都是上一個增量值的一半 **/</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><