算法設(shè)計與實驗題解

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