最新計算機算法設(shè)計與分析習題及答案-文庫吧資料
2025-07-02 15:15本頁面
【正文】 ； //sum存儲當前最大的b[j], b存儲b[j] for (int j=1； j=n； j++) { if (b0) b+= a[j] ； else b=a[i]。 c=w[i]。i++) {if (w[i]c) break。 for (i=1。i++) x[i]=0。 for (i=1。三、算法填空void Knapsack(int n,float M,float v[],float w[],float x[]){//重量為w[1..n]],價值為v[1..n]的 n個物品，裝入容量為M的背包//用貪心算法求最優(yōu)解向量x[1..n]int i。，該問題的解空間結(jié)構(gòu)為 排列樹 結(jié)構(gòu)。 子集樹 算法框架與 排列樹 算法框架。在任何時刻，算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。 具有限界函數(shù)的深度優(yōu)先生成法 。 所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到 。 規(guī)模 有關(guān)。 系統(tǒng)性 又帶有 跳躍性 的搜索算法。 系統(tǒng)性 又帶有 跳躍性 的搜索算法。 分治策略 的一種排序算法。1以廣度優(yōu)先或以最小耗費方式搜索問題解的算法稱為 分支限界法 。，且要滿足輸入、 輸出 、確定性和 有限性 四條性質(zhì)。 貪心選擇 性質(zhì)和 最優(yōu)子結(jié)構(gòu) 性質(zhì) 。1 貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。解決0/1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是 動態(tài)規(guī)劃 ，需要排序的是 回溯法 ，分支限界法 。以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 回溯法 。從分治法的一般設(shè)計模式可以看出，用它設(shè)計出的程序一般是 遞歸算法 。4. 矩陣連乘問題的算法可由 動態(tài)規(guī)劃 設(shè)計實現(xiàn)。用某種程序設(shè)計語言的具體實現(xiàn)。 }} D.51. 常見的兩種分支限界法為（D）A. 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B. 隊列式（FIFO）分支限界法與堆棧式分支限界法；C. 排列樹法與子集樹法；D. 隊列式（FIFO）分支限界法與優(yōu)先隊列式分支限界法；二、填空題 時間 復(fù)雜性和 空間 復(fù)雜性之分。i++) { swap(x[t], x[i])。 else for (int i=t。 if (legal(t)) backtrack(t1)。i=1。 }} B. C.void backtrack (int t){ if (tn) output(x)。i++) { x[t]=i。 else for (int i=0。 swap(x[t], x[i])。i++) { swap(x[t], x[i])。 else for (int i=t。 B. 活結(jié)點優(yōu)先 D. 深度優(yōu)先50. 程序塊（ A ）是回溯法中遍歷排列樹的算法框架程序。 } }46. 動態(tài)規(guī)劃算法的基本要素為（ C ）A. 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì) B．重疊子問題性質(zhì)與貪心選擇性質(zhì)C．最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì) D. 預(yù)排序與遞歸調(diào)用47. 能采用貪心算法求最優(yōu)解的問題，一般具有的重要性質(zhì)為：（ A ）A. 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì) B．重疊子問題性質(zhì)與貪心選擇性質(zhì)C．最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì) D. 預(yù)排序與遞歸調(diào)用48. 回溯法在問題的解空間樹中，按（ D ）策略，從根結(jié)點出發(fā)搜索解空間樹。 move(n,a,b)。 hanoi(n1, C, B, A)。 } }C. void hanoi(int n, int C, int B, int A) { if (n 0) { hanoi(n1, A, C, B)。 move(n,a,b)。移動圓盤時遵守Hanoi塔問題的移動規(guī)則。 } }45. Hanoi塔問題如下圖所示。
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1