數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-展示頁
2025-01-30 15:57本頁面
【正文】 行調(diào)度運算對數(shù)組進(jìn)行排序計算總平均完成時間輸出調(diào)度結(jié)果 概念設(shè)計 貪心算法通過一系列的選擇來得到一個問題的解。要得到所有任務(wù)的平均完成時間，只需要將各個任務(wù)完成時間從小到排序，任務(wù)實際完成需要的時間等于它等待的時間與自身執(zhí)行需要的時間之和。輸出例子：要求程序運行后的輸出結(jié)果為:。若輸出某一個案例中任務(wù)數(shù)目n=0，則對應(yīng)輸出一個空行。輸出要求：對每一個測試案例，打印它的最小平均完成時間。（2）、要求 輸入要求： 輸入數(shù)據(jù)中包含幾個測試案例。認(rèn)識且熟練運用貪心算法，掌握貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。本題要求找到最小的任務(wù)平均完成時間。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告（2013）數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告貪心算法任務(wù)調(diào)度問題專業(yè)計算機科學(xué)與技術(shù)學(xué)生姓名吳小會班級M計算機112學(xué)號1151401225指導(dǎo)教師吳 素 芹1目 錄1 課程設(shè)計目的及要求 12課題總體設(shè)計 1 2 3 概念設(shè)計 3 44詳細(xì)設(shè)計 4 for循環(huán)模塊設(shè)計 4 希爾排序模塊設(shè)計 5 75調(diào)試與測試 96小結(jié) 11參考文獻(xiàn) 13附 錄 14附錄1 源程序清單 141貪心算法的設(shè)計1 課程設(shè)計目的及要求 （1）、課程設(shè)計的內(nèi)容及目的 有n項任務(wù)，要求按順序執(zhí)行，并設(shè)定第i項任務(wù)需要t[i]單位時間。如果任務(wù)完成的順序為1,2，……，n，那么第i項任務(wù)完成的時間為c[i]=t[1]+…+t[i],平均完成時間（Average Completion Time, ACT）即為（c[1]+…c[n]）/n。本實驗的目的是設(shè)計一個程序，并且通過運用貪心算法來解決該題的任務(wù)調(diào)度問題。清晰了解運用貪心算法解決任務(wù)調(diào)度問題的步驟。每一個案例的第一行給出不大于2000000的整數(shù)n，接著下面一行開始列出n個非負(fù)整數(shù)t（t=1000000000）,每個數(shù)之間用空格相互隔開，以一個負(fù)數(shù)來結(jié)束輸入。每個案例對應(yīng)的輸出結(jié)果都占一行。輸入例子：44 2 8 11表示有四個任務(wù)，各自完成需要的時間單位分別為4,2,8,1，第三行輸入1表示輸入結(jié)束。 2課題總體設(shè)計這個題目屬于貪心算法應(yīng)用中任務(wù)調(diào)度問題。這樣給出的調(diào)度是按照最短作業(yè)優(yōu)先進(jìn)行來安排的。它所做的每一個選擇都是當(dāng)前狀態(tài)下某種意義的最好選擇，即貪心選擇。所謂貪心選擇性只是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到，這是貪心算法可行的第一基本要素。首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。然后，用數(shù)學(xué)歸納法證明，通過每一步做貪心選擇，最終可得到問題的一個整體最優(yōu)解。當(dāng)一個問題的最優(yōu)解包含著它的子問題最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這個性質(zhì)是該問題可用貪心算法求解的一個關(guān)鍵特征。要得到所有任務(wù)的平均完成時間，只需要將各個任務(wù)完成時間從小到排序，任務(wù)實際完成需要的時間等于它等待的時間與自身執(zhí)行需要的時間之和。4詳細(xì)設(shè)計 for循環(huán)模塊設(shè)計 明確了可以用最短作業(yè)優(yōu)先的思想后，就可以正式來設(shè)計題目的實現(xiàn)了。最
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1