數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-wenkub
2023-04-26 22:48:35 本頁面
【正文】 于它等待的時間與自身執(zhí)行需要的時間之和。然后，用數(shù)學(xué)歸納法證明，通過每一步做貪心選擇，最終可得到問題的一個整體最優(yōu)解。所謂貪心選擇性只是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到，這是貪心算法可行的第一基本要素。這樣給出的調(diào)度是按照最短作業(yè)優(yōu)先進(jìn)行來安排的。輸入例子：44 2 8 11表示有四個任務(wù)，各自完成需要的時間單位分別為4,2,8,1，第三行輸入1表示輸入結(jié)束。每一個案例的第一行給出不大于2000000的整數(shù)n，接著下面一行開始列出n個非負(fù)整數(shù)t（t=1000000000）,每個數(shù)之間用空格相互隔開，以一個負(fù)數(shù)來結(jié)束輸入。本實(shí)驗(yàn)的目的是設(shè)計(jì)一個程序，并且通過運(yùn)用貪心算法來解決該題的任務(wù)調(diào)度問題。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2013）數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告貪心算法任務(wù)調(diào)度問題專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生姓名吳小會班級M計(jì)算機(jī)112學(xué)號1151401225指導(dǎo)教師吳 素 芹1目 錄1 課程設(shè)計(jì)目的及要求 12課題總體設(shè)計(jì) 1 2 3 概念設(shè)計(jì) 3 44詳細(xì)設(shè)計(jì) 4 for循環(huán)模塊設(shè)計(jì) 4 希爾排序模塊設(shè)計(jì) 5 75調(diào)試與測試 96小結(jié) 11參考文獻(xiàn) 13附 錄 14附錄1 源程序清單 141貪心算法的設(shè)計(jì)1 課程設(shè)計(jì)目的及要求 （1）、課程設(shè)計(jì)的內(nèi)容及目的 有n項(xiàng)任務(wù)，要求按順序執(zhí)行，并設(shè)定第i項(xiàng)任務(wù)需要t[i]單位時間。認(rèn)識且熟練運(yùn)用貪心算法，掌握貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。輸出要求：對每一個測試案例，打印它的最小平均完成時間。輸出例子：要求程序運(yùn)行后的輸出結(jié)果為:。Main函數(shù)Case 1輸出排序之前結(jié)果排序sort()輸出排序之后結(jié)果Menu==1Menu==0程序結(jié)束輸入一組或多組案例輸入對應(yīng)每個任務(wù)的時間單位讀入任務(wù)的運(yùn)行時間進(jìn)行調(diào)度運(yùn)算對數(shù)組進(jìn)行排序計(jì)算總平均完成時間輸出調(diào)度結(jié)果 概念設(shè)計(jì) 貪心算法通過一系列的選擇來得到一個問題的解。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所做的貪心選擇最終將會得到問題的一個整體最優(yōu)解。其中，證明貪心選擇后問題簡化為規(guī)模更小的類似子問題的關(guān)鍵在于利用該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。這樣給出的調(diào)度是按照最短作業(yè)優(yōu)先進(jìn)行來安排的。這樣，由于案例的個數(shù)開始不得知，所以可以套用一個for循環(huán)，如下所示for(n=0。 if(n0) { 建立一個具有n個元素的數(shù)組；for（i=0。排序的方法很多，如：冒泡排序、希爾排序、堆排序等，這些排序的方法都可以使用。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個增量重復(fù)上述的分組和排序，直至所取的增量=1（…）,即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?*第一個增量值為n/2，以后每一次的增量都是上一個增量值的一半*/ for(increment =n1。i++) { /*對每一組里面的元素進(jìn)行插入排序*/ tem
公司管理相關(guān)推薦
鄂ICP備17016276號-1