算法設計與分析上機指導-資料下載頁
2025-07-23 01:57本頁面
【正文】 for j←low+1 to high //j指向當前處理的元素4. if A[j]≤x then //處理過程中有：A[i+1..j]x=A[low]5. i←i+16. if i≠j then 互換A[i]和A[j]7. end if8. end for9. if low≠i then 互換A[low]和A[i]10. w←i11. return w用C語言實現(xiàn)上述算法并上機通過。習題二（工程名為20源程序名為202）解最長公共子序列問題的偽代碼描述如下：算法 LCSRec（遞歸算法）輸入：字符串A和B，設A和B的長度分別為n和m。輸出：A和B的最長公共子序列的長度 1. LCSRec(n,m)過程procedure LCSRec(i,j)1. if i=0 or j=0 then return 02. else3. if A[i]=B[j] then4. return LCSRec(i1,j1)+15. else6. return max(LCSRec(i,j1),LCSRec(i1,j))7. end if8. end if用C語言實現(xiàn)上述算法并上機通過。選做題：給出最長公共子序列問題的非遞歸算法（動態(tài)規(guī)劃法），并上機通過。習題三（工程名為20源程序名為203）解背包問題的偽代碼描述如下： Knapsack（參見Page 139）輸入：背包容量C、物品體積集合 S = {s1,s2,...,sn}、物品價值集合V = {v1,v2,...,vn}輸出：可裝入背包物品的最大總價值1. for i←0 to n V[i,0]←0 //背包容量為02. for j←0 to C V[0,j]←0 //背包未裝入任何物品3. for i←1 to n4. for j←1 to C5. if si j then //物品ui的體積si超過容量j,不裝入。6. V[i,j]←V[i1,j] //取上一次的計算結(jié)果7. else //物品ui的體積si不超過容量j,可裝入。8. V[i,j]←max(V[i1,j],V[i1,jsi]+vi)9. end if10. end for11. end for12. return V[n,C] //返回最大總價值用C語言實現(xiàn)上述算法并上機通過。選做題1：如何修改算法Knapsack，使它只需要Θ(C)空間，其中C是背包容量。選做題2：給出背包問題的遞歸算法，并上機通過。㈢提交方式 首先建立個人目錄，目錄名為“學號姓名”，例 “57053001某某某”。在目錄“57053001某某某”中，建立子目錄2（本次實習）。在目錄“57053001某某某\2”中，應具有如下文件： 、、12
化學相關推薦
鄂ICP備17016276號-1