演算法作業答案

① 作業調度演算法一道題的解析——FCFS演算法

10.1時，①裝入主存，主存：15k，85k空閑，計算：①，等待隊列：空
10.3時，②裝入主存，主存：15k，60k，25k空閑，計算：①，等待隊列：②
10.4時，①完成計算，主存：15k空閑，60k，25k空閑，計算：②，等待隊列：空
10.5時，③要裝入主存，但由於內存不足，等待
10.6時，④裝入主存，主存：10k，5k空閑，60k，25k空閑，計算：②，等待隊列：④
10.7時，⑤裝入主存，主存：10k，5k空閑，60k，20k，5k空閑，計算：②，等待隊列：④，⑤
10.9時，②完成計算，主存：10k，65k空閑，20k，5k空閑，計算：④，等待隊列：⑤
10.9時，③由於存在超過50k的空間，裝入主存，主存：10k，50k，15k空閑，20k，5k空閑
計算：④，等待：⑤，③（此時按照先來先服務調度，⑤為先來的作業）
10.13時，④完成計算，主存：10k空閑，50k，15k空閑，20k，5k空閑，計算：⑤，等待隊列：③
10.15時，⑤完成計算，主存：15k空閑，60k，25k空閑，計算：②，等待隊列：空
10.19時，③完成計算，主存：100k空閑，計算：空，等待隊列：空
因此，順序為①②④⑤③

② 求幫演算法作業！用動態規劃法求解最長路徑問題

先對圖進行拓撲排序 一個結果為s b a c d t 拓撲排序的時候初始化dist[i] 表示從s到i的距離
dist[i]=max{dist[u]+edge[u][i], dist[i]}.
i從s取到t 最終得結果