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

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