數據結構課程設計報告--貪心算法的設計

1、<p>　　數據結構課程設計報告</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)流程圖1</p><p><b>　　2.2概念設計1</b></p><p><b>　　2.3邏輯設計1</b></p><p><b>　　3詳細設計2</b></

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

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

5、p>　　（1）、課程設計的內容及目的</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><p>　　

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

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

8、則對應輸出一個空行。</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、個任務，各自完成需要的時間單位分別為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><p>　　貪心算法通

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

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

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

14、例可以有很多組，每一個案例的輸入格式都是第一行輸入任務的個數，然后下面一行輸入每一個任務需要的時間單位，輸入完成另起一行，可以再繼續(xù)輸入下一個案例的數據。最后用一個任意的負數來表示輸入的結束。這樣，由于案例的個數開始不得知，所以可以套用一個for循環(huán)，如下所示</p><p>　　for(n=0;n>=0;) /*當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個元素的數組；</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>　　進行主要的調度運算；</p><p>　　輸入得到的最優(yōu)調度結果；</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個任務的運行時間，進行主要的調度運算。</p><p>　　4.2 希爾排序模塊設計</p><p>　　（1）、排序：將數組按照從小到大排序。</p><p>　　排序的方法很多，如：冒泡排序、希爾排序、堆排序等，這些排序的方法都可以使用。這里采用

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

20、質上是一種分組插入排序方法。希爾排序如下所示</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>　　/*對每一組里面的元素進行插入排序*/</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>　　計算總的平均完成時間：排序完成后，數組a中的元素以升序的方式排列，因此總的平均完成時間為</p><p><b>　　ACT=</b></p><p>　　4.3輸出調度結果模塊設計</p><p>　　由于輸出的結果要求精確到0.01，所以輸出的時候需要采用以下輸出格式。</p>&

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

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

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

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

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

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

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

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

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

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

39、，若當前輸入為負數，則程序終止******/</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>　　/*** 檢查輸入的數據是否大于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>　　/*** 對輸入中出現任務時間為負數的異常處理 ******/</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>　　/*** 當n為0時，標志相應的r數組值為－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] );/** 輸出的結果要求精確到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><