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

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

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

3、p><p>　　3.1 for循環(huán)模塊設(shè)計2</p><p>　　3.2 希爾排序模塊設(shè)計2</p><p>　　3.3 輸出調(diào)度結(jié)果模塊設(shè)計2</p><p><b>　　4調(diào)試與測試2</b></p><p><b>　　5小結(jié)2</b></p>&l

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

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

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

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

8、則對應(yīng)輸出一個空行。</p><p><b>　　輸入例子：</b></p><p><b>　　4</b></p><p><b>　　4 2 8 1</b></p><p><b>　　-1</b></p><p>　　表示有四

9、個任務(wù)，各自完成需要的時間單位分別為4,2,8,1，第三行輸入-1表示輸入結(jié)束。</p><p><b>　　輸出例子：</b></p><p>　　要求程序運(yùn)行后的輸出結(jié)果為:6.50。 </p><p><b>　　2課題總體設(shè)計</b></p><p>　　這個題目屬于貪心算法應(yīng)用中任務(wù)調(diào)

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

11、過一系列的選擇來得到一個問題的解。它所做的每一個選擇都是當(dāng)前狀態(tài)下某種意義的最好選擇，即貪心選擇。在許多可以用貪心算法求解的問題中一般具有兩個重要的性質(zhì)：貪心選擇性質(zhì)和最有子結(jié)構(gòu)性質(zhì)。所謂貪心選擇性只是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到，這是貪心算法可行的第一基本要素。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所做的貪心選擇最終將會得到問題的一個整體最優(yōu)解。首先考察問題的一個整體最優(yōu)

12、解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。而且做了貪心選擇后，原問題簡化為一個規(guī)模更小的類似子問題。然后，用數(shù)學(xué)歸納法證明，通過每一步做貪心選擇，最終可得到問題的一個整體最優(yōu)解。其中，證明貪心選擇后問題簡化為規(guī)模更小的類似子問題的關(guān)鍵在于利用該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。當(dāng)一個問題的最優(yōu)解包含著它的子問題最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這個性質(zhì)是該問題可用貪心算法求解的一個關(guān)鍵特征。</p><p><

13、;b>　　2.3邏輯設(shè)計</b></p><p>　　@@@@@@@@@@@@@@@@@@@@@@@@@</p><p><b>　　4詳細(xì)設(shè)計</b></p><p>　　4.1 for循環(huán)模塊設(shè)計</p><p>　　明確了可以用最短作業(yè)優(yōu)先的思想后，就可以正式來設(shè)計題目的實(shí)現(xiàn)了。首先，輸入的測試案

14、例可以有很多組，每一個案例的輸入格式都是第一行輸入任務(wù)的個數(shù)，然后下面一行輸入每一個任務(wù)需要的時間單位，輸入完成另起一行，可以再繼續(xù)輸入下一個案例的數(shù)據(jù)。最后用一個任意的負(fù)數(shù)來表示輸入的結(jié)束。這樣，由于案例的個數(shù)開始不得知，所以可以套用一個for循環(huán)，如下所示</p><p>　　for(n=0;n>=0;) /*當(dāng)n小于0的時候，退出程序*/</p><p><b>　　

15、{</b></p><p>　　scanf(“%1d”,&n);</p><p><b>　　if(n>0)</b></p><p><b>　　{</b></p><p>　　建立一個具有n個元素的數(shù)組；</p><p>　　for（i=0;i&l

16、t;n;i++）</p><p><b>　　{</b></p><p>　　繼續(xù)讀入這個n作業(yè)的完成時間；</p><p><b>　　}</b></p><p>　　進(jìn)行主要的調(diào)度運(yùn)算；</p><p>　　輸入得到的最優(yōu)調(diào)度結(jié)果；</p><p>

17、;<b>　　}</b></p><p>　　else if(n==0)</p><p><b>　　{</b></p><p><b>　　輸入一個空行；</b></p><p><b>　　}</b></p><p><b

18、>　　}</b></p><p>　　所以，對每組輸入，其基本過程是：讀入n個任務(wù)的運(yùn)行時間，進(jìn)行主要的調(diào)度運(yùn)算。</p><p>　　4.2 希爾排序模塊設(shè)計</p><p>　　（1）、排序：將數(shù)組按照從小到大排序。</p><p>　　排序的方法很多，如：冒泡排序、希爾排序、堆排序等，這些排序的方法都可以使用。這里采用

19、希爾排序來實(shí)現(xiàn)。</p><p>　　它的基本思想是：先取一個小于n的整數(shù)作為第一個增量；這里選取n的一半作為第一個增量（increment=n>>1），把數(shù)組的全部元素分成個組。所有距離為的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個增量<重復(fù)上述的分組和排序，直至所取的增量=1（<<…<<）,即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。該方法?shí)

20、質(zhì)上是一種分組插入排序方法。希爾排序如下所示</p><p>　　void Shellsort(long *a,long n)</p><p><b>　　{</b></p><p>　　long i,j,increment;</p><p>　　long temp;</p><p>　　/*第一

21、個增量值為n/2，以后每一次的增量都是上一個增量值的一半*/</p><p>　　for(increment =n>>1;increment>0;increment>>1)</p><p>　　/*每次的步長都是通過n值又移位來得到的*/</p><p><b>　　{</b></p><p&g

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

23、t;<p><b>　　{</b></p><p>　　if(temp<*(a +(j-increment)))</p><p>　　*(a+j)=*(a+(j-increment));</p><p><b>　　else</b></p><p><b>　　brea

24、k;</b></p><p><b>　　}</b></p><p>　　*(a+j)=temp;</p><p><b>　　} </b></p><p><b>　　}</b></p><p><b>　　}</b>

25、</p><p>　　計算總的平均完成時間：排序完成后，數(shù)組a中的元素以升序的方式排列，因此總的平均完成時間為</p><p><b>　　ACT=</b></p><p>　　4.3輸出調(diào)度結(jié)果模塊設(shè)計</p><p>　　由于輸出的結(jié)果要求精確到0.01，所以輸出的時候需要采用以下輸出格式。</p>&

26、lt;p>　　double r[100]; /*依次存放每個案例的ACT*/</p><p><b>　　……</b></p><p>　　printf(“%.2f\n”,r[i]);</p><p>　　/*輸出的結(jié)果要求精確到0.01*/</p><p>　　另外，程序?qū)崿F(xiàn)的時候，要求用戶一次可以輸入一組或

27、者多組測試案例的數(shù)據(jù)，當(dāng)用戶的輸入完成后，程序經(jīng)過計算在屏幕上分行顯示這幾個案例結(jié)果。因此，在有多個測試案例的情況下，需要設(shè)置一個數(shù)組，用來存放每一組測試案例的計算結(jié)果，如下所示</p><p>　　double r[100]; /*用來存放每個測試案例的計算結(jié)果*/</p><p><b>　　j=0;</b></p><p>　　for(

28、對每一個測試案例)</p><p><b>　　{</b></p><p>　　把計算得到的最有調(diào)度時間存入r[j]中；</p><p><b>　　j++;</b></p><p><b>　　} </b></p><p>　　/*當(dāng)輸入的n值為負(fù)數(shù)時

29、，跳出上面的for循環(huán)*/</p><p><b>　　for(從0到j(luò))</b></p><p><b>　　{</b></p><p>　　if(r[i]==-1)printf(“\n”); /*輸出一個空行*/</p><p>　　else printf(“%.2f\n”,r[i]); /

30、*輸出的結(jié)果要求精確到0.01*/</p><p><b>　　}</b></p><p><b>　　5調(diào)試與測試</b></p><p>　　調(diào)試方法，測試結(jié)果的分析與討論，測試過程中遇到的主要問題及采取的解決措施</p><p><b>　　@@</b></p>

31、;<p><b>　　6小結(jié)</b></p><p>　　@這周的課程設(shè)計就要結(jié)束了。從最開始的選題到現(xiàn)在的報告總結(jié)我完成了一個過程。在這個過程里我領(lǐng)悟了很多。</p><p>　　在最開始的選題時，我也是改了好幾次，最終就選了第五個任務(wù)調(diào)度的問題，因?yàn)榭吹竭@個題目后理解了它的設(shè)計要求和程序運(yùn)行的過程。雖然在中間寫的過程中還有很多不會的東西，但是通過查看

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

33、自己的不足從而去改善，這是一種學(xué)習(xí)的態(tài)度，不僅僅是在這次的課程設(shè)計中，在以后的無論生活還是學(xué)習(xí)方面都應(yīng)該注意和努力改善。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 劉振安,劉燕君.C程序設(shè)計課程設(shè)計[M].[北京]機(jī)械工業(yè)出版社,2004年9月</p><p>　　[2] 譚浩強(qiáng).C程序設(shè)計（第三版）.清華大學(xué)出

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

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

36、ll,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)基礎(chǔ) .計算機(jī)工程應(yīng)用，1981年第8期</p><p><b>　　附 錄</b><

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

38、;/b></p><p>　　long n,i,j;</p><p>　　long *a,*b;</p><p>　　double r[100];/**** 用來存放每個測試案例的計算結(jié)果 ***/</p><p>　　j=0;/*** 記錄測試案例的個數(shù) ***/</p><p>　　/*****讀入用戶的輸入

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

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

41、t;　　{</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>　　{</b></

42、p><p>　　scanf( "%ld", b+i );</p><p>　　/*** 檢查輸入的數(shù)據(jù)是否大于1000 000 000****/</p><p>　　if(*(b+i) > 1000000000){</p><p>　　printf("too much for the project!\n&qu

43、ot;);</p><p>　　exit(0);</p><p><b>　　}</b></p><p>　　/*** 對輸入中出現(xiàn)任務(wù)時間為負(fù)數(shù)的異常處理 ******/</p><p>　　if(*(b+i)<0)</p><p><b>　　{</b>&

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

45、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]+= (double)*a/(doubl

46、e)n * i; </p><p><b>　　}</b></p><p><b>　　j++;</b></p><p>　　free( b );</p><p><b>　　}</b></p><p>　　/*** 當(dāng)n為0時，標(biāo)志相應(yīng)的r數(shù)組值為－1

47、，輸出時碰到－1則輸出一個空行***/</p><p>　　else if ( n == 0 )</p><p><b>　　{</b></p><p>　　r[j++]=-1;</p><p><b>　　}</b></p><p><b>　　}</b

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

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

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

51、;<p>　　/** 第一個增量值為(n/2)，以后每一次的增量都是上一個增量值的一半 **/</p><p>　　for( increment = n>>1; increment>0; increment>>=1 )</p><p><b>　　{</b></p><p>　　for(i = inc

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

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