算法設計與實驗題解

第1章 算法概述
習題11 函數的漸近表達式
習題12 O(1)和O(2)的區(qū)別
習題14 按漸近階排列表達式
習題15 算法效率
習題16 硬件效率
習題17 函數漸近階
習題18 n!的階
習題110 平均情況下的計算時間復雜性
算法實現題11 統計數字問題
算法實現題12 字典序問題
算法實現題13 最多約數問題
算法實現題14 金幣陣列問題
算法實現題15 最大間隙問題
第2章 遞歸與分治策略 習題21 Hanoi塔問題的非遞歸算法
習題22 7個二分搜索算法
習題23 改寫二分搜索算法
習題24 大整數乘法的O(nmlog(3/2))算法
習題25 5次n/3位整數的乘法
習題26 矩陣乘法
習題27 多項式乘積
習題28 不動點問題的O(logn)時間算法
習題29 主元素問題的線性時間算法
習題210 無序集主元素問題的線性時間算法
習題211 O(1)空間子數組換位算法
習題212 O(1)空間合并算法
習題213 n段合并排序算法 習題214 自然合并排序算法
習題215 最大值和最小值問題的最優(yōu)算法 習題216 最大值和次大值問題的最優(yōu)算法 習題217 整數集合排序
習題218 第k小元素問題的計算時間下界 習題219 非增序快速排序算法
習題220 隨機化算法
習題221 隨機化快速排序算法
習題222 隨機排列算法
習題223 算法QuickSort中的尾遞歸
習題224 用棧模擬遞歸
習題225 算法Select中的元素劃分
習題226 O(nlogn)時間快速排序算法 習題227 最接近中位數的k個數
習題228 X和Y的中位數
習題229 網絡開關設計
習題232 帶權中位數問題
習題234 構造Gray碼的分治算法
習題235 網球循環(huán)賽日程表
習題236 二叉樹T的前序、中序和后序序列 算法實現題21 輸油管道問題（習題230） 算法實現題22 眾數問題（習題231） 算法實現題23 郵局選址問題（習題232） 算法實現題24 馬的Hamilton周游路線問題（習題233） 算法實現題25 半數集問題
算法實現題26 半數單集問題
算法實現題27 士兵站隊問題
算法實現題28 有重復元素的排列問題
算法實現題29 排列的字典序問題
算法實現題210 集合劃分問題
算法實現題211 集合劃分問題
算法實現題212 雙色Hanoi塔問題
算法實現題213 標準二維表問題
算法實現題214 整數因子分解問題
第3章 動態(tài)規(guī)劃
習題31 最長單調遞增子序列
習題32 最長單調遞增子序列的O(nlogn)算法 習題37 漂亮打印
習題311 整數線性規(guī)劃問題
習題312 二維01背包問題
習題314 Ackermann函數
習題317 最短行駛路線
習題319 最優(yōu)旅行路線
算法實現題31 獨立任務最優(yōu)調度問題(習題33) 算法實現題32 最少硬幣問題(習題34) 算法實現題33 序關系計數問題(習題35) 算法實現題34 多重冪計數問題(習題36)
算法實現題35 編輯距離問題(習題38) 算法實現題36 石子合并問題(習題39) 算法實現題37 數字三角形問題(習題310)
算法實現題38 乘法表問題(習題313)
算法實現題39 租用游艇問題(習題315) 算法實現題310 汽車加油行駛問題(習題316) 算法實現題311 最小m段和問題
算法實現題312 圈乘運算問題(習題318) 算法實現題313 最大長方體問題(習題321) 算法實現題314 正則表達式匹配問題(習題322) 算法實現題315 雙調旅行售貨員問題(習題323) 算法實現題316 最大k乘積問題(習題528)
算法實現題317 最少費用購物問題(習題320)
算法實現題318 收集樣本問題
算法實現題319 最優(yōu)時間表問題
算法實現題320 字符串比較問題
算法實現題321 有向樹k中值問題
算法實現題322 有向樹獨立k中值問題
算法實現題323 有向直線m中值問題
算法實現題324 有向直線2中值問題
算法實現題325 樹的最大連通分支問題
算法實現題326 直線k中值問題
算法實現題327 直線k覆蓋問題
算法實現題328 m處理器問題
算法實現題329 紅黑樹的紅色內結點問題
第4章 貪心算法
習題42 活動安排問題的貪心選擇
習題43 背包問題的貪心選擇性質
習題44 特殊的01背包問題
習題410 程序最優(yōu)存儲問題
習題413 最優(yōu)裝載問題的貪心算法
習題418 Fibonacci序列的哈夫曼編碼
習題419 最優(yōu)前綴碼的編碼序列
習題421 任務集獨立性問題
習題422 矩陣擬陣
習題423 最小權最大獨立子集擬陣
習題427 整數邊權Prim算法
習題428 最大權最小生成樹
習題429 最短路徑的負邊權
習題430 整數邊權Dijkstra算法
算法實現題41 會場安排問題(習題41)
算法實現題42 最優(yōu)合并問題(習題45)
算法實現題43 磁帶最優(yōu)存儲問題(習題46)
算法實現題44 磁盤文件最優(yōu)存儲問題(習題47)
算法實現題45 程序存儲問題(習題48)
算法實現題46 最優(yōu)服務次序問題(習題411)
算法實現題47 多處最優(yōu)服務次序問題(習題412)
算法實現題48 d森林問題(習題414)
算法實現題49 汽車加油問題(習題416)
算法實現題410 區(qū)間覆蓋問題(習題417)
算法實現題411 硬幣找錢問題(習題424)
算法實現題412 刪數問題(習題425)
算法實現題413 數列極差問題(習題426)
算法實現題414 嵌套箱問題(習題431)
算法實現題415 套匯問題(習題432)
算法實現題416 信號增強裝置問題(習題520)
算法實現題417 磁帶最大利用率問題(習題49)
算法實現題418 非單位時間任務安排問題(習題415)
算法實現題419 多元Huffman編碼問題(習題420)
算法實現題420 多元Huffman編碼變形
算法實現題421 區(qū)間相交問題
算法實現題422 任務時間表問題
算法實現題423 最優(yōu)分解問題
算法實現題424 可重復最優(yōu)分解問題
算法實現題425 可重復最優(yōu)組合分解問題
算法實現題426 旅行規(guī)劃問題
算法實現題427 登山機器人問題
第5章 回溯法
習題51 裝載問題改進回溯法1
習題52 裝載問題改進回溯法2
習題54 01背包問題的最優(yōu)解
習題55 最大團問題的迭代回溯法
習題57 旅行售貨員問題的費用上界
習題58 旅行售貨員問題的上界函數
算法實現題51 子集和問題（習題53） 算法實現題52 最小長度電路板排列問題（習題59） 算法實現題53 最小重量機器設計問題（習題510）
算法實現題54 運動員最佳配對問題（習題514）
算法實現題55 無分隔符字典問題（習題515）
算法實現題56 無和集問題（習題516）
算法實現題57 n色方柱問題（習題517）
算法實現題58 整數變換問題（習題518）
算法實現題59 拉丁矩陣問題
算法實現題510 排列寶石問題（習題519）
算法實現題511 重復拉丁矩陣問題（習題519）
算法實現題512 羅密歐與朱麗葉的迷宮問題（習題521） 算法實現題513 工作分配問題（習題522）
算法實現題514 獨立鉆石跳棋問題（習題523）
算法實現題515 智力拼圖問題（習題524）
算法實現題516 布線問題（習題525）
算法實現題517 最佳調度問題（習題526）
算法實現題518 無優(yōu)先級運算問題（習題527）
算法實現題519 世界名畫陳列館問題（習題529）
算法實現題520 世界名畫陳列館問題（不重復監(jiān)視）（習題5
30） 算法實現題521 2×2×2魔方問題
算法實現題522 魔方(Rubik’s Cube)問題（習題531） 算法實現題523 算24點問題
算法實現題524 算m點問題
算法實現題525 雙軌車皮編序問題
算法實現題526 多軌車皮編序問題
算法實現題527 部落衛(wèi)隊問題（習題56）
算法實現題528 蟲蝕算式問題
算法實現題529 完備環(huán)序列問題
算法實現題530 離散01串問題
算法實現題531 噴漆機器人問題
算法實現題532 子集樹問題（習題511）
算法實現題533 01背包問題（習題511）
算法實現題534 排列樹問題（習題512）
算法實現題535 一般解空間搜索問題（習題513）
算法實現題536 最短加法鏈問題
算法實現題537 n2-1謎問題
第6章 分支限界法
習題61 01背包問題的棧式分支限界法 習題62 釋放結點空間的隊列式分支限界法 習題63 及時刪除不用的結點
習題64 用最大堆存儲活結點的優(yōu)先隊列式分支限界法
習題65 釋放結點空間的優(yōu)先隊列式分支限界法
習題66 團頂點數的上界
習題67 團頂點數改進的上界
習題68 修改解旅行售貨員問題的分支限界法
習題69 解旅行售貨員問題的分支限界法中保存已產生的排列
樹
習題610 電路板排列問題的隊列式分支限界法
算法實現題61 最小長度電路板排列問題（習題611）
算法實現題62 最小長度電路板排列問題（習題612）
算法實現題63 最小權頂點覆蓋問題（習題613）
算法實現題64 無向圖的最大割問題（習題614）
算法實現題65 最小重量機器設計問題（習題615）
算法實現題66 運動員最佳配對問題（習題616）
算法實現題67 n皇后問題（習題618）
算法實現題68 圓排列問題（習題619）
算法實現題69 布線問題（習題620）
算法實現題610 最佳調度問題（習題621）
算法實現題611 無優(yōu)先級運算問題（習題622）
算法實現題612 世界名畫陳列館問題（習題624）
算法實現題613 子集空間樹問題（習題625）
算法實現題614 排列空間樹問題（習題626）
算法實現題615 一般解空間的隊列式分支限界法（習題627）
算法實現題616 子集空間樹問題（習題628）
算法實現題617 排列空間樹問題（習題629）
算法實現題618 一般解空間的優(yōu)先隊列式分支限界法（習題630）
算法實現題619 騎士征途問題
算法實現題620 推箱子問題
算法實現題621 圖形變換問題
算法實現題622 行列變換問題
算法實現題623 重排n2宮問題
算法實現題624 最長距離問題
第7章 概率算法
習題71 模擬正態(tài)分布隨機變量
習題72 隨機抽樣算法
習題73 隨機產生m個整數
習題74 集合大小的概率算法
習題75 生日問題
習題76 易驗證問題的拉斯維加斯算法
習題77 用數組模擬有序鏈表
習題78 O(n3/2)舍伍德型排序算法
習題79 n后問題解的存在性
習題711 整數因子分解算法
習題712 非蒙特卡羅算法的例子
習題713 重復3次的蒙特卡羅算法
習題714 集合隨機元素算法
習題715 由蒙特卡羅算法構造拉斯維加斯算法
習題716 產生素數算法
習題719 矩陣方程問題
算法實現題71 模平方根問題（習題710）
算法實現題72 素數測試問題（習題717）
算法實現題73 集合相等問題（習題718）
算法實現題74 逆矩陣問題（習題720）
算法實現題75 多項式乘積問題（習題721）
算法實現題76 皇后控制問題
算法實現題77 3SAT問題
算法實現題78 戰(zhàn)車問題
算法實現題79 圓排列問題
算法實現題710 騎士控制問題
算法實現題711 騎士對攻問題
第8章 線性規(guī)劃與網絡流
習題81 線性規(guī)劃可行區(qū)域無界的例子
習題82 單源最短路與線性規(guī)劃
習題83 網絡最大流與線性規(guī)劃
習題84 最小費用流與線性規(guī)劃
習題85 運輸計劃問題
習題86 單純形算法
習題87 邊連通度問題
習題88 有向無環(huán)網絡的最大流
習題89 無向網絡的最大流
習題812 最大流更新算法
習題816 混合圖歐拉回路問題
習題822 單源最短路與最小費用流
習題823 中國郵路問題
算法實現題81 飛行員配對方案問題（習題810）
算法實現題82 太空飛行計劃問題（習題811）
算法實現題83 最小路徑覆蓋問題（習題813）
算法實現題84 魔術球問題（習題814）
算法實現題85 圓桌問題（習題815）
算法實現題86 最長遞增子序列問題（習題817）
算法實現題87 試題庫問題（習題818）
算法實現題88 機器人路徑規(guī)劃問題（習題819）
算法實現題89 方格取數問題（習題820）
算法實現題810 餐巾計劃問題（習題821）
算法實現題811 航空路線問題（習題824）
算法實現題812 軟件補丁問題（習題825）
算法實現題813 星際轉移問題（習題826）
算法實現題814 孤島營救問題（習題827）
算法實現題815 汽車加油行駛問題（習題828）
算法實現題816 數字梯形問題
算法實現題817 運輸問題
算法實現題818 分配工作問題
算法實現題819 負載平衡問題
算法實現題820 深海機器人問題
算法實現題821 最長k可重區(qū)間集問題
算法實現題822 最長k可重線段集問題
算法實現題823 火星探險問題
算法實現題824 騎士共存問題
第9章 NP完全性理論與近似算法
習題91 RAM和RASP程序
習題92 RAM和RASP程序的復雜性
習題93 計算nn的RAM程序
習題94 平面圖著色問題的絕對近似算法
習題95 最優(yōu)程序存儲問題
習題96 樹的最優(yōu)頂點覆蓋
習題97 頂點覆蓋算法的性能比
習題98 團的常數性能比近似算法
習題910 旅行售貨員問題的常數性能比近似算法
習題911 瓶頸旅行售貨員問題
習題912 最優(yōu)旅行售貨員回路不自相交
習題914 集合覆蓋問題的實例
習題916 多機調度問題的近似算法
習題917 LPT算法的最壞情況實例
習題918 多機調度問題的多項式時間近似算法
算法實現題91 旅行售貨員問題的近似算法（習題99）
算法實現題92 可滿足問題的近似算法（習題919）
算法實現題93 最大可滿足問題的近似算法（習題920）
算法實現題94 子集和問題的近似算法（習題915）
算法實現題95 子集和問題的完全多項式時間近似算法
算法實現題96 2SAT問題的線性時間算法
算法實現題97 實現算法greedySetCover（習題913）
參考文獻