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