課程設(shè)計--貪心算法

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p><b>　　貪心算法</b></p><p><b>　　目 錄</b></p><p><b>　　1 設(shè)計題目1</b></p><p><b>　　2 設(shè)計分析

2、1</b></p><p><b>　　3 設(shè)計實(shí)現(xiàn)4</b></p><p><b>　　4測試方法7</b></p><p><b>　　4.1測試目的7</b></p><p>　　4.2 測試輸入7</p><p>　　4.

3、3 正確輸出7</p><p>　　4.4 實(shí)際輸出7</p><p><b>　　5 分析與探討8</b></p><p>　　5.1 測試結(jié)果分析8</p><p>　　5.2 探討與改進(jìn)8</p><p><b>　　6 設(shè)計小結(jié)8</b></p>

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

5、t;<b>　　輸入要求：</b></p><p>　　輸入數(shù)據(jù)中包含幾個測試案例。每一個案例的第一行給出一個不大于2000000的整數(shù)n，接著下面一行開始列出n個非負(fù)整數(shù)t（t<=1000000000），每個數(shù)之間用空格相互隔開，以一個負(fù)數(shù)來結(jié)束輸入。</p><p><b>　　輸出要求：</b></p><p>

6、;　　對每一個測試案例，打印它的最小平均完成時間，并精確到0.01。每個案例對應(yīng)的輸出結(jié)果都占一行。若輸入某一個案例中任務(wù)數(shù)目n=0，則對應(yīng)輸出一個空行。</p><p><b>　　輸入例子：</b></p><p><b>　　4</b></p><p><b>　　4 2 8 1</b><

7、/p><p><b>　　-1</b></p><p>　　表示有四個任務(wù)，各自完成需要的時間單位分別是4，2，8，1，第三行輸入-1表示結(jié)束。</p><p><b>　　輸出例子：</b></p><p>　　要求程序運(yùn)行后的輸出結(jié)果為：6.50。</p><p><b

8、>　　2 設(shè)計分析</b></p><p>　　算法是為了求解一個問題需要遵循的，被青春地指定的簡單指令的集合。任何程序基本上都是要用特點(diǎn)的算法來實(shí)現(xiàn)的。算法性能的好壞，直接決定了所實(shí)現(xiàn)程序性能的優(yōu)劣。貪心算法通過一系列的選擇來的得到一個問題的解。它所做的每一個選擇都是當(dāng)前的狀態(tài)下某種意義的最好選擇，即貪心選擇。希望通過每次所做的貪心選擇導(dǎo)致最終結(jié)果問題的一個最優(yōu)解。這種啟發(fā)式的策略并不總能奏效

9、，然而在許多情況下能達(dá)到預(yù)期的目的。</p><p>　　這個題目屬于貪心算法應(yīng)用中的任務(wù)調(diào)度問題。要得到所有任務(wù)的平均完成時間，只需要將各個任務(wù)完成時間從小到大排序，任務(wù)實(shí)際完成需要的時間等于它等待的時間與自身執(zhí)行需要的時間之和。這樣給出的調(diào)度是按照最短作業(yè)優(yōu)先進(jìn)行來安排的。</p><p>　　明確了可以用最短作業(yè)優(yōu)先的思想后，就可以正式來設(shè)計題目的實(shí)現(xiàn)了。首先，輸入的測試案例可以有很

10、多組，每一個案例的輸入格式都是第一行輸入任務(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>　　{</b&

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

12、</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><b&g

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

14、</b></p><p>　　所以，對每組輸入，其基本過程是：讀入n個任務(wù)的運(yùn)行時間，進(jìn)行主要的調(diào)度運(yùn)算。已經(jīng)明確了采用最短作業(yè)優(yōu)先的程序思想，所以主要的調(diào)度運(yùn)算包括3個步驟：</p><p>　　(1)排序：將數(shù)組按照從小到大排序。</p><p>　　排序的方法很多，如：冒泡排序、希爾排序、堆排序等，這些排序的方法都可以使用。這里采用希爾排序來實(shí)現(xiàn)，

15、如圖2.2所示。</p><p>　　它的基本思想是：先取一個小于n的整數(shù)d1作為第一個增量；這里選取n的一半作為第一個增量（increment=n>>1），把數(shù)組的全部元素分成d1個組。所有距離為d1的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1（dt<d(t-1)<…<d2<d1），即所

16、有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。該方法?shí)質(zhì)上是一種分組插入排序方法。</p><p>　　void Shellsort( long *a, long n )</p><p><b>　　{</b></p><p>　　long i, j, increment;</p><p>　　long temp;</p

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

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

19、 = i; j>=increment; j-= increment)</p><p><b>　　{</b></p><p>　　if( temp < *(a + (j-increment)) )</p><p>　　*(a+j)= *( a+ (j-increment) );</p><p><b&g

20、t;　　else</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　*(a+j) = temp;</p><p><b>　　}</b></p><p><b>　

21、　}</b></p><p><b>　　}</b></p><p>　?。?）計算總的平均完成時間：排序完成后，數(shù)組a中的元素以升序的方式排序，因此總的平均完成時間為</p><p>　　ACT＝∑(i=0,N)a[i]*(n-i)/n</p><p>　　（3）輸出調(diào)度結(jié)果：由于輸出的結(jié)果要求精確到0.0

22、1，所以輸出的時候需要采用以下輸出格式。</p><p>　　另外，程序?qū)崿F(xiàn)的時候，要求用戶一次可以輸入一組或者多組測試案例的數(shù)據(jù)，當(dāng)用戶的輸入完成后，程序經(jīng)過計算在屏幕上分行顯示這幾個案例的結(jié)果。因此，在有多個測試案例的情況下，需要設(shè)置一個數(shù)組，用來存放每一組測試案例的計算結(jié)果。</p><p><b>　　3 設(shè)計實(shí)現(xiàn)</b></p><p&g

23、t;　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　/* run this program using the console pauser or add your own getch, system("pause") or input loop */</p>

24、<p>　　void Shellsort( long *a, long n );</p><p>　　int main()</p><p><b>　　{</b></p><p>　　long n,i,j;</p><p>　　long *a,*b;</p><p>　　double

25、r[100];/**** 用來存放每個測試案例的計算結(jié)果 ***/</p><p>　　j=0;/*** 記錄測試案例的個數(shù) ***/</p><p>　　/*****讀入用戶的輸入，若當(dāng)前輸入為負(fù)數(shù)，則程序終止******/</p><p>　　for( n = 0; n >= 0 ; )</p><p><b>　　{&l

26、t;/b></p><p>　　scanf( "%ld", &n );</p><p>　　if(n > 2000000){</p><p>　　printf("too much for the project!\n");</p><p><b>　　exit(0);<

27、;/b></p><p><b>　　}</b></p><p>　　if( n > 0 )</p><p><b>　　{</b></p><p>　　b = (long*)malloc( n * sizeof( long ) );</p><p><b&

28、gt;　　a = b;</b></p><p>　　for(i=0; i< n ; i++)</p><p><b>　　{</b></p><p>　　scanf( "%ld", b+i );</p><p>　　/*** 檢查輸入的數(shù)據(jù)是否大于1000 000 000****/&

29、lt;/p><p>　　if(*(b+i) > 1000000000){</p><p>　　printf("too much for the project!\n");</p><p>　　exit(0);</p><p><b>　　}</b></p><p>

30、　　/*** 對輸入中出現(xiàn)任務(wù)時間為負(fù)數(shù)的異常處理 ******/</p><p>　　if(*(b+i)<0)</p><p><b>　　{</b></p><p>　　printf("input error！\n");</p><p><b>　　return 0;</b&

31、gt;</p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　Shellsort( b, n );</p><p>　　/***** 計算平均完成時間 *****/</p><p>　　for( i = n, r[j] =

32、0.0; i > 0 ; i--,a++ )</p><p><b>　　{</b></p><p>　　r[j]+= (double)*a/(double)n * i; </p><p><b>　　}</b></p><p><b>　　j++;</b></p&

33、gt;<p>　　free( b );</p><p><b>　　}</b></p><p>　　/*** 當(dāng)n為0時，標(biāo)志相應(yīng)的r數(shù)組值為－1，輸出時碰到－1則輸出一個空行***/</p><p>　　else if ( n == 0 )</p><p><b>　　{</b>&l

34、t;/p><p>　　r[j++]=-1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=0;i<j;i++)</p><p><b>　　{</b></p><

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

36、>　　}</b></p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　/*** 希爾排序方法 ***/</p><p>　　void Shellsort( long *a, long n )</p>&l

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

38、 increment>0; increment>>=1 )</p><p><b>　　{</b></p><p>　　for(i = increment; i < n; i++)</p><p><b>　　{</b></p><p>　　temp = *(a+i);<

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

40、;/p><p><b>　　else</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　*(a+j) = temp;</p><p><b>　　}</b></p

41、><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　4測試方法</b></p><p><b>　　4.1測試目的</b></p><p>　　檢驗(yàn)程序是否正常運(yùn)行并完成算法的要求。&l

42、t;/p><p><b>　　4.2 測試輸入</b></p><p><b>　　4</b></p><p><b>　　4 1 2 3</b></p><p><b>　　5</b></p><p><b>　　2 3 4

43、 1 5</b></p><p><b>　　-1</b></p><p><b>　　4.3 正確輸出</b></p><p><b>　　5.00</b></p><p><b>　　7.00</b></p><p>

44、;<b>　　4.4 實(shí)際輸出 </b></p><p><b>　　5 分析與探討</b></p><p>　　5.1 測試結(jié)果分析 </p><p>　　調(diào)試與運(yùn)行過程中，程序可以正常運(yùn)行，并在輸入不同數(shù)據(jù)情況下分別給出正確的結(jié)果，說明該程序正確無誤，完成了此次課程設(shè)計題目的要求。</p><p&g

45、t;<b>　　5.2 探討與改進(jìn)</b></p><p>　　總的來說，該程序已基本實(shí)現(xiàn)了貪心算法的要求功能，但還可以對其中的一些細(xì)節(jié)進(jìn)行優(yōu)化，比如程序的運(yùn)行結(jié)果界面可以加上更多的文字描述與提示，增加觀賞性，也可以用起來更方便。 </p><p><b>　　6 設(shè)計小結(jié)</b></p><p>　　在本次為期一周的數(shù)據(jù)

46、結(jié)構(gòu)課程設(shè)計中，我的題目是貪心算法：任務(wù)調(diào)度問題，貪心算法采用的是逐步構(gòu)造最優(yōu)解的方法，類似的任務(wù)調(diào)度問題在生活有很多，雖然有時候我們都沒感覺到它的存在，但不能否認(rèn)有時候我們不經(jīng)意間已經(jīng)使用了貪心算法去尋找最優(yōu)解的方法。這個是我對這個題目最基本的認(rèn)識，也增加了自己在以后生活中的經(jīng)驗(yàn)。從數(shù)據(jù)結(jié)構(gòu)這門課的角度，雖然書中給了源代碼供我們參考，但在通過自己去調(diào)試，成功的運(yùn)行這個程序的過程中，還是會遇到一些問題，通過自己查閱書上的內(nèi)容，向同學(xué)請教

47、，最終得以圓滿解決，這也讓自己學(xué)到很多，用的有C語言的知識，還有數(shù)據(jù)結(jié)構(gòu)這門課本身，不僅鞏固以前的知識，加深了認(rèn)識，還得到了很多實(shí)踐的過程中帶給自己的收獲。</p><p>　　在本次課程設(shè)計中，面對很多問題也發(fā)現(xiàn)了自己的不足之處還很多，很多知識不牢固，不明晰，不能熟練的運(yùn)用，這需要自己以后在學(xué)習(xí)過程中不斷的深化改進(jìn)。 當(dāng)然，我也認(rèn)識到了理論和實(shí)踐相結(jié)合的重要性，課本上的知識是不夠的，只有自己多操作，多練習(xí)，才能