數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-文庫吧
2025-01-06 15:57 本頁面
【正文】 擇后，原問題簡化為一個規(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)鍵特征。 這個題目屬于貪心算法應(yīng)用中任務(wù)調(diào)度問題。要得到所有任務(wù)的平均完成時間，只需要將各個任務(wù)完成時間從小到排序，任務(wù)實際完成需要的時間等于它等待的時間與自身執(zhí)行需要的時間之和。這樣給出的調(diào)度是按照最短作業(yè)優(yōu)先進(jìn)行來安排的。4詳細(xì)設(shè)計 for循環(huán)模塊設(shè)計 明確了可以用最短作業(yè)優(yōu)先的思想后，就可以正式來設(shè)計題目的實現(xiàn)了。首先，輸入的測試案例可以有很多組，每一個案例的輸入格式都是第一行輸入任務(wù)的個數(shù)，然后下面一行輸入每一個任務(wù)需要的時間單位，輸入完成另起一行，可以再繼續(xù)輸入下一個案例的數(shù)據(jù)。最后用一個任意的負(fù)數(shù)來表示輸入的結(jié)束。這樣，由于案例的個數(shù)開始不得知，所以可以套用一個for循環(huán)，如下所示for(n=0。n=0。) /*當(dāng)n小于0的時候，退出程序*/{ scanf(“%1d”,amp。n)。 if(n0) { 建立一個具有n個元素的數(shù)組；for（i=0。in。i++）{ 繼續(xù)讀入這個n作業(yè)的完成時間；}進(jìn)行主要的調(diào)度運(yùn)算；輸入得到的最優(yōu)調(diào)度結(jié)果；}else if(n==0){ 輸入一個空行；}}所以，對每組輸入，其基本過程是：讀入n個任務(wù)的運(yùn)行時間，進(jìn)行主要的調(diào)度運(yùn)算。開始n=0YN輸入任務(wù)i=0ini++YN繼續(xù)讀入n個作業(yè)完成時間輸出一個空行退出程序 希爾排序模塊設(shè)計（1）、排序：將數(shù)組按照從小到大排序。排序的方法很多，如：冒泡排序、希爾排序、堆排序等，這些排序的方法都可以使用。這里采用希爾排序來實現(xiàn)。它的基本思想是：先取一個小于n的整數(shù)作為第一個增量；這里選取n的一半作為第一個增量（increment=n1），把數(shù)組的全部元素分成個組。所有距離為的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個增量重復(fù)上述的分組和排序，直至所取的增量=1（…）,即所有記錄放在同一組中進(jìn)行直接插入排序為止。該方法實質(zhì)上是一種分組插入排序方法。希爾排序如下所示void Shellsort(long *a,long n){ long i,j,increment。 long temp。/*第一個增量值為n/2，以后每一次的增量都是上一個增量值的一半*/ for(increment =n1。increment0。increment1)/*每次的步長都是通過n值又移位來得到的*/{ for(i=increment。in。i++) { /*對每一組里面的元素進(jìn)行插入排序*/ temp= *(a+i)。 for(j=i。j=increment。j=increment) { if(te
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1