word版可編輯-北京大學(xué)算法設(shè)計與分析課期末試題精心整理-資料下載頁
2025-03-24 05:11本頁面
【正文】 j = i4。 j = 0。 j = 2) f[i] += f[j]*2。 } return f[n]。} 五、田忌賽馬（20分）裝訂線內(nèi) 不要答題你一定聽過田忌賽馬的故事吧？如果3匹馬變成n匹，齊王仍然讓他的馬按從優(yōu)到劣的順序出賽，田忌可以按任意順序選擇他的賽馬出賽。贏一局，田忌可以得到200兩銀子，輸一局，田忌就要輸?shù)?00兩銀子。已知國王和田忌的所有馬的奔跑速度，并且所有馬奔跑的速度均不相同，現(xiàn)已經(jīng)對兩人的馬分別從快到慢排好序，請設(shè)計一個算法，幫助田忌贏得最多的銀子。寫出偽代碼，證明算法的正確性，并分析算法的復(fù)雜度。（提示：可以設(shè)計一個貪心策略的算法，面對國王每匹順序出場的馬，如果田忌的馬快，就派最快的出場；否則派最慢的馬出場） 裝訂線內(nèi) 不要答題六、（20分）給出n項(xiàng)作業(yè)，對應(yīng)每項(xiàng)作業(yè)有一個運(yùn)行時間，在m個處理器上調(diào)度這些作業(yè)，使完成的時間最小。完成的時間定義為在所有的處理器中運(yùn)行時間最長的處理器運(yùn)行的時間。采用如下的近似算法：即，按照原始給定的作業(yè)順序: ，把每一項(xiàng)作業(yè)分配給當(dāng)前情況下最近可用的那個處理器，使該作業(yè)盡可能早被處理（其它沒有任何約束）1. 試證明該算法的近似度為。（10分）2. 構(gòu)造邊界情況，說明這個界是緊的。（10分）（提示：） 裝訂線內(nèi) 不要答題
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1