課程設計--貪心算法(已修改)
2025-01-25 18:44 本頁面
【正文】 數(shù)據(jù)結構課程設計——貪心算法：任務調度問題數(shù)據(jù)結構課程設計貪心算法專業(yè)軟件工程班級B軟件121學號1210701132學生姓名 1目 錄1 設計題目 12 設計分析 13 設計實現(xiàn) 44測試方法 7 7 測試輸入 7 正確輸出 7 實際輸出 75 分析與探討 8 測試結果分析 8 探討與改進 86 設計小結 8 11 設計題目 有n項任務，要求按順序執(zhí)行，并設定第i項任務需要t[i]單位時間。如果任務完成的順序為1，2，…，n，那么第i項任務完成的時間為c[i]=t[1]+…+t[i]，平均完成時間（Average Completion Time，ACT）即為（c[1]+…+c[n]）/n。本題要求找到最小的任務平均時間。輸入要求：輸入數(shù)據(jù)中包含幾個測試案例。每一個案例的第一行給出一個不大于2000000的整數(shù)n，接著下面一行開始列出n個非負整數(shù)t（t=1000000000），每個數(shù)之間用空格相互隔開，以一個負數(shù)來結束輸入。輸出要求：對每一個測試案例，打印它的最小平均完成時間。每個案例對應的輸出結果都占一行。若輸入某一個案例中任務數(shù)目n=0，則對應輸出一個空行。輸入例子：44 2 8 11表示有四個任務，各自完成需要的時間單位分別是4，2，8，1，第三行輸入1表示結束。輸出例子：要求程序運行后的輸出結果為：。2 設計分析算法是為了求解一個問題需要遵循的，被青春地指定的簡單指令的集合。任何程序基本上都是要用特點的算法來實現(xiàn)的。算法性能的好壞，直接決定了所實現(xiàn)程序性能的優(yōu)劣。貪心算法通過一系列的選擇來的得到一個問題的解。它所做的每一個選擇都是當前的狀態(tài)下某種意義的最好選擇，即貪心選擇。希望通過每次所做的貪心選擇導致最終結果問題的一個最優(yōu)解。這種啟發(fā)式的策略并不總能奏效，然而在許多情況下能達到預期的目的。這個題目屬于貪心算法應用中的任務調度問題。要得到所有任務的平均完成時間，只需要將各個任務完成時間從小到大排序，任務實際完成需要的時間等于它等待的時間與自身執(zhí)行需要的時間之和。這樣給出的調度是按照最短作業(yè)優(yōu)先進行來安排的。明確了可以用最短作業(yè)優(yōu)先的思想后，就可以正式來設計題目的實現(xiàn)了。首先，輸入的測試案例可以有很多組，每一個案例的輸入格式都是第一行輸入任務的個數(shù)，然后下面一行輸入每一個任務需要的時間單位，輸入完成另起一行，可以再繼續(xù)輸入下一個案例的數(shù)據(jù)。最后用一個任意的負數(shù)來表示輸入的結束。
電大資料相關推薦
鄂ICP備17016276號-1