數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(已修改)
2025-02-02 15:57 本頁(yè)面
【正文】 數(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é)生姓名吳小會(huì)班級(jí)M計(jì)算機(jī)112學(xué)號(hào)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)試與測(cè)試 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]單位時(shí)間。如果任務(wù)完成的順序?yàn)?,2，……，n，那么第i項(xiàng)任務(wù)完成的時(shí)間為c[i]=t[1]+…+t[i],平均完成時(shí)間（Average Completion Time, ACT）即為（c[1]+…c[n]）/n。本題要求找到最小的任務(wù)平均完成時(shí)間。本實(shí)驗(yàn)的目的是設(shè)計(jì)一個(gè)程序，并且通過(guò)運(yùn)用貪心算法來(lái)解決該題的任務(wù)調(diào)度問題。認(rèn)識(shí)且熟練運(yùn)用貪心算法，掌握貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。清晰了解運(yùn)用貪心算法解決任務(wù)調(diào)度問題的步驟。（2）、要求 輸入要求： 輸入數(shù)據(jù)中包含幾個(gè)測(cè)試案例。每一個(gè)案例的第一行給出不大于2000000的整數(shù)n，接著下面一行開始列出n個(gè)非負(fù)整數(shù)t（t=1000000000）,每個(gè)數(shù)之間用空格相互隔開，以一個(gè)負(fù)數(shù)來(lái)結(jié)束輸入。輸出要求：對(duì)每一個(gè)測(cè)試案例，打印它的最小平均完成時(shí)間。每個(gè)案例對(duì)應(yīng)的輸出結(jié)果都占一行。若輸出某一個(gè)案例中任務(wù)數(shù)目n=0，則對(duì)應(yīng)輸出一個(gè)空行。輸入例子：44 2 8 11表示有四個(gè)任務(wù)，各自完成需要的時(shí)間單位分別為4,2,8,1，第三行輸入1表示輸入結(jié)束。輸出例子：要求程序運(yùn)行后的輸出結(jié)果為:。 2課題總體設(shè)計(jì)這個(gè)題目屬于貪心算法應(yīng)用中任務(wù)調(diào)度問題。要得到所有任務(wù)的平均完成時(shí)間，只需要將各個(gè)任務(wù)完成時(shí)間從小到排序，任務(wù)實(shí)際完成需要的時(shí)間等于它等待的時(shí)間與自身執(zhí)行需要的時(shí)間之和。這樣給出的調(diào)度是按照最短作業(yè)優(yōu)先進(jìn)行來(lái)安排的。Main函數(shù)Case 1輸出排序之前結(jié)果排序sort()輸出排序之后結(jié)果Menu==1Menu==0程序結(jié)束輸入一組或多組案例輸入對(duì)應(yīng)每個(gè)任務(wù)的時(shí)間單位讀入任務(wù)的運(yùn)行時(shí)間進(jìn)行調(diào)度運(yùn)算對(duì)數(shù)組進(jìn)行排序計(jì)算總平均完成時(shí)間輸出調(diào)度結(jié)果 概念設(shè)計(jì) 貪心算法通過(guò)一系列的選擇來(lái)得到一個(gè)問題的解。它所做的每一個(gè)選擇都是當(dāng)前狀態(tài)下某種意義的最好選擇，即貪心選擇。在許多可以用貪心算法求解的問題中一般具有兩個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最有子結(jié)構(gòu)性質(zhì)。所謂貪心選擇性只是指所求問題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到，這是貪心算法可行的第一基本要素。對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所做的貪心選擇最終將會(huì)得到問題的一個(gè)整體最優(yōu)解。首先考察問題的一個(gè)整體最優(yōu)解，并證明可修改這個(gè)最優(yōu)解，使其以貪心選擇開始。而且做了貪心選
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1