計算機算法設(shè)計與分析習(xí)題解答

前言

　　一些著名的計算機科學(xué)家在有關(guān)計算機科學(xué)教育的論述中認為，計算機科學(xué)是一種創(chuàng)造性思維活動，其教育必須面向設(shè)計。計算機算法設(shè)計與分析正是一門面向設(shè)計，且處于計算機學(xué)科核心地位的教育課程。通過對計算機算法系統(tǒng)的學(xué)習(xí)與研究，理解和掌握算法設(shè)計的主要方法，培養(yǎng)對算法的計算復(fù)雜性進行正確分析的能力，為獨立地設(shè)計算法和對給定算法進行復(fù)雜性分析奠定堅實的理論基礎(chǔ)，對從事計算機系統(tǒng)結(jié)構(gòu)、系統(tǒng)軟件和應(yīng)用軟件研究與開發(fā)的科技工作者是非常重要和必不可少的?！　‰娮庸I(yè)出版社出版的《計算機算法設(shè)計與分析（第4版）》是普通高等教育“十一五”國家級規(guī)劃教材，它是根據(jù)教育部高教司主持評審的《中國計算機科學(xué)與技術(shù)學(xué)科教程2002》以及ACM和IEEE/CS CC2001組織編寫的教材，在內(nèi)容選材、深度把握、系統(tǒng)性和可用性方面進行了精心設(shè)計，力圖適合高校本科生教學(xué)對學(xué)時數(shù)和知識結(jié)構(gòu)的要求。本書是與《計算機算法設(shè)計與分析（第4版）》配套的輔助教材，對該書中的習(xí)題做了解答或給出了解題思路提示。　　算法設(shè)計與分析是計算學(xué)科的9個主科目之一，而且在整個學(xué)科知識體系中具有學(xué)科核心的重要地位，它充分體現(xiàn)了計算機科學(xué)方法論的理論、抽象和設(shè)計3個過程，知識面較寬，且有一定的深度；算法設(shè)計與分析課程需要反復(fù)再現(xiàn)計算機科學(xué)中用到的大問題的復(fù)雜性、效率、抽象的層次、重用、折中等帶有普遍性的概念。根據(jù)作者多年的教學(xué)經(jīng)驗，算法設(shè)計與分析課程教學(xué)有以下3個特點，這使許多學(xué)生感到學(xué)習(xí)相當(dāng)困難?！　。?） 按照《中國計算機科學(xué)與技術(shù)學(xué)科教程2002》以及ACM和IEEE/CS CC2001的要求，算法設(shè)計與分析課程教學(xué)包括的知識點多，內(nèi)容十分豐富，學(xué)習(xí)量大?！　。?） 課程內(nèi)容理論性很強，對學(xué)生的抽象思維能力和邏輯推理能力要求較高?！　。?） 課程內(nèi)容還有很強的實踐性，要求學(xué)生靈活運用所學(xué)到的算法設(shè)計策略解決實際問題?！　〗滩闹械恼n后習(xí)題能在很大程度上解決上面所說的困難?！队嬎銠C算法設(shè)計與分析（第4版）》所配備的習(xí)題正是為此目的而設(shè)計的。教材出版后，許多讀者紛紛要求給出習(xí)題解答和提示。為了讓使用《計算機算法設(shè)計與分析（第4版）》作為教材的師生在廣度和深度的各個層面更深刻地理解理論、抽象和設(shè)計這3個過程以及重復(fù)出現(xiàn)的12個基本概念（綁定、大問題的復(fù)雜性、概念和形式模型、一致性和完備性、演化、效率、抽象層次、按空間排序、按時間排序、重用、安全性、折中的結(jié)論），作者根據(jù)多年的教學(xué)經(jīng)驗編寫了這本輔助教材，旨在讓使用該書的教師更容易教，學(xué)生更容易學(xué)。為了便于對照閱讀，本書的章序與《計算機算法設(shè)計與分析（第4版）》保持一致，且一一對應(yīng)?！　”緯膬?nèi)容是對教材《計算機算法設(shè)計與分析（第4版）》的擴展，一些在教材中無法講述的較深入的主題通過習(xí)題的形式展現(xiàn)出來。為了提高學(xué)生靈活運用算法設(shè)計策略解決實際問題的能力，本書將原教材中的許多習(xí)題改造成算法實現(xiàn)題，要求學(xué)生不僅設(shè)計出解決具體問題的算法，而且能上機實現(xiàn)。其中很多題目使用了多種不同解法，體現(xiàn)了算法的靈活性和適用性。根據(jù)作者多年的教學(xué)實踐，這類算法實現(xiàn)題的教學(xué)效果非常好?！　”緯鴥?nèi)容豐富，理論聯(lián)系實際，可作為高等學(xué)校計算機科學(xué)與技術(shù)、軟件工程、信息安全、信息與計算科學(xué)等專業(yè)本科生和研究生學(xué)習(xí)計算機算法設(shè)計的輔助教材，也是工程技術(shù)人員和自學(xué)者的參考書?！　∽髡哌€結(jié)合國家精品課程建設(shè)  ，進行了教材的立體化開發(fā)，包括主教材、習(xí)題解答、電子課件和教學(xué)網(wǎng)站等資源  。歡迎廣大讀者訪問教學(xué)網(wǎng)站并提出寶貴意見?！　”緯峁┑慕虒W(xué)資源包含各章算法實現(xiàn)題的題目、測試數(shù)據(jù)和答案。共有12個子目錄，包括：ch1，ch2，…，ch8，midexam1，midexam2，finalexam1，finalexam2。每章的每個算法實現(xiàn)題都對應(yīng)一個子目錄，其中的test子目錄中是測試數(shù)據(jù)，answer子目錄中是相應(yīng)的答案。midexam1和midexam2目錄中是兩套期中試卷。finalexam1和finalexam2目錄中是兩套期終試卷。本書主教材提供電子課件，需要者可登錄華信教育資源網(wǎng)免費注冊下載。算法設(shè)計的實現(xiàn)平臺是Microsoft Visual Studio 60或Microsoft Visual Studio.NET。采用面向?qū)ο蟮腃++語言作為算法描述手段?！　≡诒緯帉戇^程中，福州大學(xué)“211工程”計算機與信息工程重點學(xué)科實驗室提供了優(yōu)良的設(shè)備與工作環(huán)境。電子工業(yè)出版社負責(zé)本書編輯出版工作的全體同仁為本書的　　出版付出了大量辛勤勞動，他們認真細致，一絲不茍的工作精神保證了本書的出版質(zhì)量。在此，謹向每位曾經(jīng)關(guān)心和支持本書編寫工作的各方面人士表示衷心的謝意！　　作 者

內(nèi)容概要

《計算機算法設(shè)計與分析習(xí)題解答(第2版高等學(xué)校規(guī)劃教材)》編著者王曉東。
《計算機算法設(shè)計與分析習(xí)題解答(第2版高等學(xué)校規(guī)劃教材)》內(nèi)容提要：本書是與普通高等教育“十一五”國家級規(guī)劃教材《計算機算法設(shè)計與分析（第4版）》配套的輔助教材和國家精品課程教材，分別對主教材中的算法分析題和算法實現(xiàn)題給出了解答或解題思路提示。為了提高學(xué)生靈活運用算法設(shè)計策略解決實際問題的能力，本書還將主教材中的許多習(xí)題改造成算法實現(xiàn)題，要求學(xué)生設(shè)計出求解算法并上機實現(xiàn)。作者還結(jié)合國家精品課程建設(shè)，進行了教材的立體化開發(fā)，包括主教材、習(xí)題解答、電子課件和教學(xué)網(wǎng)站等資源。本書教學(xué)資料包含各章算法實現(xiàn)題、測試數(shù)據(jù)和答案，可在華信教育資源網(wǎng)免費注冊下載。
本書內(nèi)容豐富，理論聯(lián)系實際，可作為高等學(xué)校計算機科學(xué)與技術(shù)、軟件工程、信息安全、信息與計算科學(xué)等專業(yè)本科生和研究生學(xué)習(xí)計算機算法設(shè)計的輔助教材，也是工程技術(shù)人員和自學(xué)者的參考書。

書籍目錄

第1章 算法概述 
 算法分析題1 
 1-1 函數(shù)的漸近表達式 
 1-2 O(1)和O(2)的區(qū)別 
 1-3 按漸近階排列表達式 
 1-4 算法效率 
 1-5 硬件效率 
 1-6 函數(shù)漸近階 
 1-7 n!的階 
 1-8 3n+1問題 
 1-9 平均情況下的計算時間復(fù)雜性
 算法實現(xiàn)題1 
 1-1 統(tǒng)計數(shù)字問題 
 1-2 字典序問題 
 1-3 最多約數(shù)問題 
 1-4 金幣陣列問題 
 1-5 最大間隙問題 
第2章 遞歸與分治策略 
 算法分析題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(1)空間子數(shù)組換位算法 
 2-9 O(1)空間合并算法 
 2-10 n段合并排序算法 
 2-11 自然合并排序算法 
 2-12 第k小元素問題的計算時間下界 
 2-13 非增序快速排序算法 
 2-14 構(gòu)造Gray碼的分治算法 
 2-15 網(wǎng)球循環(huán)賽日程表 
 2-16 二叉樹T的前序、中序和后序序列 
 算法實現(xiàn)題2 
 2-1 眾數(shù)問題 
 2-2 馬的Hamilton周游路線問題
 2-3 半數(shù)集問題 
 2-4 半數(shù)單集問題 
 2-5 有重復(fù)元素的排列問題 
 2-6 排列的字典序問題 
 2-7 集合劃分問題 
 2-8 集合劃分問題 
 2-9 雙色Hanoi塔問題 
 2-10 標準二維表問題 
 2-11 整數(shù)因子分解問題 
第3章 動態(tài)規(guī)劃 
 算法分析題3 
 3-1 最長單調(diào)遞增子序列 
 3-2 最長單調(diào)遞增子序列的O(nlogn)算法 
 3-3 整數(shù)線性規(guī)劃問題 
 3-4 二維0-1背包問題 
 3-5 Ackermann函數(shù) 
 算法實現(xiàn)題3 
 3-1 獨立任務(wù)最優(yōu)調(diào)度問題 
 3-2 編輯距離問題 
 3-3 石子合并問題 
 3-4 數(shù)字三角形問題 
 3-5 乘法表問題 
 3-6 租用游艇問題 
 3-7 汽車加油行駛問題 
 3-8 最小m段和問題 
 3-9 圈乘運算問題 
 3-10 最大長方體問題 
 3-11 正則表達式匹配問題 
 3-12 雙調(diào)旅行售貨員問題 
 3-13 最大k乘積問題 
 3-14 最少費用購物問題 
 3-15 收集樣本問題 
 3-16 最優(yōu)時間表問題 
 3-17 字符串比較問題 
 3-18 有向樹k中值問題 
 3-19 有向樹獨立k中值問題 
 3-20 有向直線m中值問題
 3-21 有向直線2中值問題 
 3-22 樹的最大連通分支問題 
 3-23 直線k中值問題 
 3-24 直線k覆蓋問題 
 3-25 m處理器問題 
第4章 貪心算法
 算法分析題4 
 4-1 程序最優(yōu)存儲問題 
 4-2 最優(yōu)裝載問題的貪心算法
 4-3 Fibonacci序列的哈夫曼編碼 
 4-4 最優(yōu)前綴碼的編碼序列 
 算法實現(xiàn)題4 
 4-1 會場安排問題 
 4-2 最優(yōu)合并問題 
 4-3 磁帶最優(yōu)存儲問題 
 4-4 磁盤文件最優(yōu)存儲問題 
 4-5 程序存儲問題 
 4-6 最優(yōu)服務(wù)次序問題 
 4-7 多處最優(yōu)服務(wù)次序問題 
 4-8 d森林問題 
 4-9 汽車加油問題 
 4-10 區(qū)間覆蓋問題 
 4-11 刪數(shù)問題 
 4-12 磁帶最大利用率問題 
 4-13 非單位時間任務(wù)安排問題
 4-14 多元Huffman編碼問題 
 4-15 最優(yōu)分解問題 
第5章 回溯法 
 算法分析題5 
 5-1 裝載問題改進回溯法1 
 5-2 裝載問題改進回溯法2 
 5-3 0-1背包問題的最優(yōu)解 
 5-4 最大團問題的迭代回溯法
 5-5 旅行售貨員問題的費用上界
 5-6 旅行售貨員問題的上界函數(shù)
 算法實現(xiàn)題5 
 5-1 子集和問題 
 5-2 最小長度電路板排列問題 
 5-3 最小重量機器設(shè)計問題 
 5-4 運動員最佳配對問題 
 5-5 無分隔符字典問題 
 5-6 無和集問題 
 5-7 n色方柱問題 
 5-8 整數(shù)變換問題 
 5-9 拉丁矩陣問題 
 5-10 排列寶石問題 
 5-11 重復(fù)拉丁矩陣問題 
 5-12 羅密歐與朱麗葉的迷宮問題
 5-13 工作分配問題 
 5-14 布線問題 
 5-15 最佳調(diào)度問題 
 5-16 無優(yōu)先級運算問題 
 5-17 世界名畫陳列館問題 
 5-18 世界名畫陳列館問題（不重復(fù)監(jiān)視） 
 5-19 算m點問題 
 5-20 部落衛(wèi)隊問題 
 5-21 子集樹問題 
 5-22 0-1背包問題 
 5-23 排列樹問題 
 5-24 一般解空間搜索問題 
 5-25 最短加法鏈問題 
第6章 分支限界法 
 算法分析題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 
 6-1 最小長度電路板排列問題
 6-2 最小權(quán)頂點覆蓋問題 
 6-3 無向圖的最大割問題 
 6-4 最小重量機器設(shè)計問題 
 6-5 運動員最佳配對問題 
 6-6 n皇后問題 
 6-7 布線問題 
 6-8 最佳調(diào)度問題 
 6-9 無優(yōu)先級運算問題 
 6-10 世界名畫陳列館問題 
 6-11 子集空間樹問題 
 6-12 排列空間樹問題 
 6-13 一般解空間的隊列式分支限界法 
 6-14 子集空間樹問題 
 6-15 排列空間樹問題 
 6-16 一般解空間的優(yōu)先隊列式分支限界法 
 6-17 推箱子問題 
第7章 概率算法 
 算法分析題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-10 整數(shù)因子分解算法 
 7-11 非蒙特卡羅算法的例子
 7-12 重復(fù)3次的蒙特卡羅算法
 7-13 集合隨機元素算法 
 7-14 由蒙特卡羅算法構(gòu)造拉斯維加斯算法 
 7-15 產(chǎn)生素數(shù)算法 
 7-16 矩陣方程問題 
算法實現(xiàn)題7 
 7-1 模平方根問題 
 7-2 素數(shù)測試問題 
 7-3 集合相等問題 
 7-4 逆矩陣問題 
 7-5 多項式乘積問題 
 7-6 皇后控制問題 
 7-7 3-SAT問題 
 7-8 戰(zhàn)車問題 
第8章 線性規(guī)劃與網(wǎng)絡(luò)流 算法分析題8 
 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-10 最大流更新算法 
 8-11 混合圖歐拉回路問題 
 8-12 單源最短路與最小費用流
 8-13 中國郵路問題 
算法實現(xiàn)題8 
 8-1 飛行員配對方案問題 
 8-2 太空飛行計劃問題 
 8-3 最小路徑覆蓋問題 
 8-4 魔術(shù)球問題 
 8-5 圓桌問題 
 8-6 最長遞增子序列問題 
 8-7 試題庫問題 
 8-8 機器人路徑規(guī)劃問題 
 8-9 方格取數(shù)問題 
 8-10 餐巾計劃問題 
 8-11 航空路線問題 
 8-12 軟件補丁問題 
 8-13 星際轉(zhuǎn)移問題 
 8-14 孤島營救問題 
 8-15 汽車加油行駛問題 
 8-16 數(shù)字梯形問題 
 8-17 運輸問題 
 8-18 分配工作問題 
 8-19 負載平衡問題 
 8-20 最長k可重區(qū)間集問題 
 8-21 最長k可重線段集問題 
參考文獻

章節(jié)摘錄

版權(quán)頁：   插圖：   問題描述：1944年，特種兵麥克接到國防部的命令，要求立即趕赴太平洋上的一個孤島，營救被敵軍俘虜?shù)拇蟊鸲?。瑞恩被關(guān)押在一個迷宮里，迷宮地形復(fù)雜，但幸好麥克得到了迷宮的地形圖。迷宮的外形是一個長方形，其南北方向被劃分為N行，東西方向被劃分為M列，于是整個迷宮被劃分為N×M個單元。每一個單元的位置可用一個有序數(shù)對（單元的行號，單元的列號）來表示。南北或東西方向相鄰的2個單元之間可能互通，也可能有一扇鎖著的門，或者是一堵不可逾越的墻。迷宮中有一些單元存放著鑰匙，并且所有的門被分成P類，打開同一類的門的鑰匙相同，不同類門的鑰匙不同。 大兵瑞恩被關(guān)押在迷宮的東南角，即（N，M）單元里，并已經(jīng)昏迷。迷宮只有一個入口，在西北角。也就是說，麥克可以直接進入（1，1）單元。另外，麥克從一個單元移動到另一個相鄰單元的時間為1，拿取所在單元鑰匙的時間及用鑰匙開門的時間可忽略不計。

編輯推薦

《國家精品課程教材?高等學(xué)校規(guī)劃教材:計算機算法設(shè)計與分析習(xí)題解答(第2版)》內(nèi)容豐富，理論聯(lián)系實際，可作為高等學(xué)校計算機科學(xué)與技術(shù)、軟件工程、信息安全、信息與計算科學(xué)等專業(yè)本科生和研究生學(xué)習(xí)計算機算法設(shè)計的輔助教材，也是工程技術(shù)人員和自學(xué)者的參考書。

圖書封面

評論、評分、閱讀與下載

---

    計算機算法設(shè)計與分析習(xí)題解答 PDF格式下載

---