數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告

1、數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計 報 告貪心算法 貪心算法任務(wù)調(diào)度問題 任務(wù)調(diào)度問題專業(yè) 專業(yè) 計算機科學(xué)與技術(shù)學(xué)生姓名 學(xué)生姓名 吳小會班級 班級 M 計算機 112學(xué)號 學(xué)號 1151401225指導(dǎo)教師 指導(dǎo)教師 吳 素 芹貪心算法的設(shè)計 貪心算法的設(shè)計1 課程設(shè)計目的及要求 課程設(shè)計目的及要求 （1） 、課程設(shè)計的內(nèi)容及目的有 n 項任務(wù)，要求按順序執(zhí)行，并設(shè)定第 i 項任務(wù)需要 t[i]單位時間。如果任務(wù)完成的順序為 1

2、,2，……，n，那么第 i 項任務(wù)完成的時間為c[i]=t[1]+…+t[i],平均完成時間（Average Completion Time, ACT）即為（c[1]+…c[n]）/n。本題要求找到最小的任務(wù)平均完成時間。本實驗的目的是設(shè)計一個程序，并且通過運用貪心算法來解決該題的任務(wù)調(diào)度問題。認(rèn)識且熟練運用貪心算法，掌握貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。清晰了解運用貪心算法解決任務(wù)調(diào)度問題的步驟。（2） 、要求輸入要求：輸入數(shù)據(jù)中包

3、含幾個測試案例。每一個案例的第一行給出不大于 2000000 的整數(shù) n，接著下面一行開始列出 n 個非負(fù)整數(shù) t（t<=1000000000）,每個數(shù)之間用空格相互隔開，以一個負(fù)數(shù)來結(jié)束輸入。輸出要求：對每一個測試案例，打印它的最小平均完成時間，并精確到 0.01。每個案例對應(yīng)的輸出結(jié)果都占一行。若輸出某一個案例中任務(wù)數(shù)目 n=0，則對應(yīng)輸出一個空行。輸入例子：44 2 8 1-1表示有四個任務(wù)，各自完成需要的時間單位分別為 4