出版時(shí)間:2012-6 出版社:電子工業(yè)出版社 作者:王曉東 頁(yè)數(shù):311 字?jǐn)?shù):507000
前言
一些著名的計(jì)算機(jī)科學(xué)家在有關(guān)計(jì)算機(jī)科學(xué)教育的論述中認(rèn)為,計(jì)算機(jī)科學(xué)是一種創(chuàng)造性思維活動(dòng),其教育必須面向設(shè)計(jì)。計(jì)算機(jī)算法設(shè)計(jì)與分析正是一門面向設(shè)計(jì),且處于計(jì)算機(jī)學(xué)科核心地位的教育課程。通過(guò)對(duì)計(jì)算機(jī)算法系統(tǒng)的學(xué)習(xí)與研究,理解和掌握算法設(shè)計(jì)的主要方法,培養(yǎng)對(duì)算法的計(jì)算復(fù)雜性進(jìn)行正確分析的能力,為獨(dú)立地設(shè)計(jì)算法和對(duì)給定算法進(jìn)行復(fù)雜性分析奠定堅(jiān)實(shí)的理論基礎(chǔ),對(duì)從事計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、系統(tǒng)軟件和應(yīng)用軟件研究與開(kāi)發(fā)的科技工作者是非常重要和必不可少的?! ‰娮庸I(yè)出版社出版的《計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)》是普通高等教育“十一五”國(guó)家級(jí)規(guī)劃教材,它是根據(jù)教育部高教司主持評(píng)審的《中國(guó)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科教程2002》以及ACM和IEEE/CS CC2001組織編寫的教材,在內(nèi)容選材、深度把握、系統(tǒng)性和可用性方面進(jìn)行了精心設(shè)計(jì),力圖適合高校本科生教學(xué)對(duì)學(xué)時(shí)數(shù)和知識(shí)結(jié)構(gòu)的要求。本書是與《計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)》配套的輔助教材,對(duì)該書中的習(xí)題做了解答或給出了解題思路提示?! ∷惴ㄔO(shè)計(jì)與分析是計(jì)算學(xué)科的9個(gè)主科目之一,而且在整個(gè)學(xué)科知識(shí)體系中具有學(xué)科核心的重要地位,它充分體現(xiàn)了計(jì)算機(jī)科學(xué)方法論的理論、抽象和設(shè)計(jì)3個(gè)過(guò)程,知識(shí)面較寬,且有一定的深度;算法設(shè)計(jì)與分析課程需要反復(fù)再現(xiàn)計(jì)算機(jī)科學(xué)中用到的大問(wèn)題的復(fù)雜性、效率、抽象的層次、重用、折中等帶有普遍性的概念。根據(jù)作者多年的教學(xué)經(jīng)驗(yàn),算法設(shè)計(jì)與分析課程教學(xué)有以下3個(gè)特點(diǎn),這使許多學(xué)生感到學(xué)習(xí)相當(dāng)困難?! 。?) 按照《中國(guó)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科教程2002》以及ACM和IEEE/CS CC2001的要求,算法設(shè)計(jì)與分析課程教學(xué)包括的知識(shí)點(diǎn)多,內(nèi)容十分豐富,學(xué)習(xí)量大?! 。?) 課程內(nèi)容理論性很強(qiáng),對(duì)學(xué)生的抽象思維能力和邏輯推理能力要求較高。 ?。?) 課程內(nèi)容還有很強(qiáng)的實(shí)踐性,要求學(xué)生靈活運(yùn)用所學(xué)到的算法設(shè)計(jì)策略解決實(shí)際問(wèn)題?! 〗滩闹械恼n后習(xí)題能在很大程度上解決上面所說(shuō)的困難?!队?jì)算機(jī)算法設(shè)計(jì)與分析(第4版)》所配備的習(xí)題正是為此目的而設(shè)計(jì)的。教材出版后,許多讀者紛紛要求給出習(xí)題解答和提示。為了讓使用《計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)》作為教材的師生在廣度和深度的各個(gè)層面更深刻地理解理論、抽象和設(shè)計(jì)這3個(gè)過(guò)程以及重復(fù)出現(xiàn)的12個(gè)基本概念(綁定、大問(wèn)題的復(fù)雜性、概念和形式模型、一致性和完備性、演化、效率、抽象層次、按空間排序、按時(shí)間排序、重用、安全性、折中的結(jié)論),作者根據(jù)多年的教學(xué)經(jīng)驗(yàn)編寫了這本輔助教材,旨在讓使用該書的教師更容易教,學(xué)生更容易學(xué)。為了便于對(duì)照閱讀,本書的章序與《計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)》保持一致,且一一對(duì)應(yīng)?! ”緯膬?nèi)容是對(duì)教材《計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)》的擴(kuò)展,一些在教材中無(wú)法講述的較深入的主題通過(guò)習(xí)題的形式展現(xiàn)出來(lái)。為了提高學(xué)生靈活運(yùn)用算法設(shè)計(jì)策略解決實(shí)際問(wèn)題的能力,本書將原教材中的許多習(xí)題改造成算法實(shí)現(xiàn)題,要求學(xué)生不僅設(shè)計(jì)出解決具體問(wèn)題的算法,而且能上機(jī)實(shí)現(xiàn)。其中很多題目使用了多種不同解法,體現(xiàn)了算法的靈活性和適用性。根據(jù)作者多年的教學(xué)實(shí)踐,這類算法實(shí)現(xiàn)題的教學(xué)效果非常好。 本書內(nèi)容豐富,理論聯(lián)系實(shí)際,可作為高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、信息安全、信息與計(jì)算科學(xué)等專業(yè)本科生和研究生學(xué)習(xí)計(jì)算機(jī)算法設(shè)計(jì)的輔助教材,也是工程技術(shù)人員和自學(xué)者的參考書?! ∽髡哌€結(jié)合國(guó)家精品課程建設(shè) ,進(jìn)行了教材的立體化開(kāi)發(fā),包括主教材、習(xí)題解答、電子課件和教學(xué)網(wǎng)站等資源 。歡迎廣大讀者訪問(wèn)教學(xué)網(wǎng)站并提出寶貴意見(jiàn)?! ”緯峁┑慕虒W(xué)資源包含各章算法實(shí)現(xiàn)題的題目、測(cè)試數(shù)據(jù)和答案。共有12個(gè)子目錄,包括:ch1,ch2,…,ch8,midexam1,midexam2,finalexam1,finalexam2。每章的每個(gè)算法實(shí)現(xiàn)題都對(duì)應(yīng)一個(gè)子目錄,其中的test子目錄中是測(cè)試數(shù)據(jù),answer子目錄中是相應(yīng)的答案。midexam1和midexam2目錄中是兩套期中試卷。finalexam1和finalexam2目錄中是兩套期終試卷。本書主教材提供電子課件,需要者可登錄華信教育資源網(wǎng)免費(fèi)注冊(cè)下載。算法設(shè)計(jì)的實(shí)現(xiàn)平臺(tái)是Microsoft Visual Studio 60或Microsoft Visual Studio.NET。采用面向?qū)ο蟮腃++語(yǔ)言作為算法描述手段?! ≡诒緯帉戇^(guò)程中,福州大學(xué)“211工程”計(jì)算機(jī)與信息工程重點(diǎn)學(xué)科實(shí)驗(yàn)室提供了優(yōu)良的設(shè)備與工作環(huán)境。電子工業(yè)出版社負(fù)責(zé)本書編輯出版工作的全體同仁為本書的 出版付出了大量辛勤勞動(dòng),他們認(rèn)真細(xì)致,一絲不茍的工作精神保證了本書的出版質(zhì)量。在此,謹(jǐn)向每位曾經(jīng)關(guān)心和支持本書編寫工作的各方面人士表示衷心的謝意! 作 者
內(nèi)容概要
《計(jì)算機(jī)算法設(shè)計(jì)與分析習(xí)題解答(第2版高等學(xué)校規(guī)劃教材)》編著者王曉東。
《計(jì)算機(jī)算法設(shè)計(jì)與分析習(xí)題解答(第2版高等學(xué)校規(guī)劃教材)》內(nèi)容提要:本書是與普通高等教育“十一五”國(guó)家級(jí)規(guī)劃教材《計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)》配套的輔助教材和國(guó)家精品課程教材,分別對(duì)主教材中的算法分析題和算法實(shí)現(xiàn)題給出了解答或解題思路提示。為了提高學(xué)生靈活運(yùn)用算法設(shè)計(jì)策略解決實(shí)際問(wèn)題的能力,本書還將主教材中的許多習(xí)題改造成算法實(shí)現(xiàn)題,要求學(xué)生設(shè)計(jì)出求解算法并上機(jī)實(shí)現(xiàn)。作者還結(jié)合國(guó)家精品課程建設(shè),進(jìn)行了教材的立體化開(kāi)發(fā),包括主教材、習(xí)題解答、電子課件和教學(xué)網(wǎng)站等資源。本書教學(xué)資料包含各章算法實(shí)現(xiàn)題、測(cè)試數(shù)據(jù)和答案,可在華信教育資源網(wǎng)免費(fèi)注冊(cè)下載。
本書內(nèi)容豐富,理論聯(lián)系實(shí)際,可作為高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、信息安全、信息與計(jì)算科學(xué)等專業(yè)本科生和研究生學(xué)習(xí)計(jì)算機(jī)算法設(shè)計(jì)的輔助教材,也是工程技術(shù)人員和自學(xué)者的參考書。
書籍目錄
第1章 算法概述
算法分析題1
1-1 函數(shù)的漸近表達(dá)式
1-2 O(1)和O(2)的區(qū)別
1-3 按漸近階排列表達(dá)式
1-4 算法效率
1-5 硬件效率
1-6 函數(shù)漸近階
1-7 n!的階
1-8 3n+1問(wèn)題
1-9 平均情況下的計(jì)算時(shí)間復(fù)雜性
算法實(shí)現(xiàn)題1
1-1 統(tǒng)計(jì)數(shù)字問(wèn)題
1-2 字典序問(wèn)題
1-3 最多約數(shù)問(wèn)題
1-4 金幣陣列問(wèn)題
1-5 最大間隙問(wèn)題
第2章 遞歸與分治策略
算法分析題2
2-1 Hanoi塔問(wèn)題的非遞歸算法
2-2 7個(gè)二分搜索算法
2-3 改寫二分搜索算法
2-4 大整數(shù)乘法的O(nmlog(3/2))算法
2-5 5次n/3位整數(shù)的乘法
2-6 矩陣乘法
2-7 多項(xiàng)式乘積
2-8 O(1)空間子數(shù)組換位算法
2-9 O(1)空間合并算法
2-10 n段合并排序算法
2-11 自然合并排序算法
2-12 第k小元素問(wèn)題的計(jì)算時(shí)間下界
2-13 非增序快速排序算法
2-14 構(gòu)造Gray碼的分治算法
2-15 網(wǎng)球循環(huán)賽日程表
2-16 二叉樹(shù)T的前序、中序和后序序列
算法實(shí)現(xiàn)題2
2-1 眾數(shù)問(wèn)題
2-2 馬的Hamilton周游路線問(wèn)題
2-3 半數(shù)集問(wèn)題
2-4 半數(shù)單集問(wèn)題
2-5 有重復(fù)元素的排列問(wèn)題
2-6 排列的字典序問(wèn)題
2-7 集合劃分問(wèn)題
2-8 集合劃分問(wèn)題
2-9 雙色Hanoi塔問(wèn)題
2-10 標(biāo)準(zhǔn)二維表問(wèn)題
2-11 整數(shù)因子分解問(wèn)題
第3章 動(dòng)態(tài)規(guī)劃
算法分析題3
3-1 最長(zhǎng)單調(diào)遞增子序列
3-2 最長(zhǎng)單調(diào)遞增子序列的O(nlogn)算法
3-3 整數(shù)線性規(guī)劃問(wèn)題
3-4 二維0-1背包問(wèn)題
3-5 Ackermann函數(shù)
算法實(shí)現(xiàn)題3
3-1 獨(dú)立任務(wù)最優(yōu)調(diào)度問(wèn)題
3-2 編輯距離問(wèn)題
3-3 石子合并問(wèn)題
3-4 數(shù)字三角形問(wèn)題
3-5 乘法表問(wèn)題
3-6 租用游艇問(wèn)題
3-7 汽車加油行駛問(wèn)題
3-8 最小m段和問(wèn)題
3-9 圈乘運(yùn)算問(wèn)題
3-10 最大長(zhǎng)方體問(wèn)題
3-11 正則表達(dá)式匹配問(wèn)題
3-12 雙調(diào)旅行售貨員問(wèn)題
3-13 最大k乘積問(wèn)題
3-14 最少費(fèi)用購(gòu)物問(wèn)題
3-15 收集樣本問(wèn)題
3-16 最優(yōu)時(shí)間表問(wèn)題
3-17 字符串比較問(wèn)題
3-18 有向樹(shù)k中值問(wèn)題
3-19 有向樹(shù)獨(dú)立k中值問(wèn)題
3-20 有向直線m中值問(wèn)題
3-21 有向直線2中值問(wèn)題
3-22 樹(shù)的最大連通分支問(wèn)題
3-23 直線k中值問(wèn)題
3-24 直線k覆蓋問(wèn)題
3-25 m處理器問(wèn)題
第4章 貪心算法
算法分析題4
4-1 程序最優(yōu)存儲(chǔ)問(wèn)題
4-2 最優(yōu)裝載問(wèn)題的貪心算法
4-3 Fibonacci序列的哈夫曼編碼
4-4 最優(yōu)前綴碼的編碼序列
算法實(shí)現(xiàn)題4
4-1 會(huì)場(chǎng)安排問(wèn)題
4-2 最優(yōu)合并問(wèn)題
4-3 磁帶最優(yōu)存儲(chǔ)問(wèn)題
4-4 磁盤文件最優(yōu)存儲(chǔ)問(wèn)題
4-5 程序存儲(chǔ)問(wèn)題
4-6 最優(yōu)服務(wù)次序問(wèn)題
4-7 多處最優(yōu)服務(wù)次序問(wèn)題
4-8 d森林問(wèn)題
4-9 汽車加油問(wèn)題
4-10 區(qū)間覆蓋問(wèn)題
4-11 刪數(shù)問(wèn)題
4-12 磁帶最大利用率問(wèn)題
4-13 非單位時(shí)間任務(wù)安排問(wèn)題
4-14 多元Huffman編碼問(wèn)題
4-15 最優(yōu)分解問(wèn)題
第5章 回溯法
算法分析題5
5-1 裝載問(wèn)題改進(jìn)回溯法1
5-2 裝載問(wèn)題改進(jìn)回溯法2
5-3 0-1背包問(wèn)題的最優(yōu)解
5-4 最大團(tuán)問(wèn)題的迭代回溯法
5-5 旅行售貨員問(wèn)題的費(fèi)用上界
5-6 旅行售貨員問(wèn)題的上界函數(shù)
算法實(shí)現(xiàn)題5
5-1 子集和問(wèn)題
5-2 最小長(zhǎng)度電路板排列問(wèn)題
5-3 最小重量機(jī)器設(shè)計(jì)問(wèn)題
5-4 運(yùn)動(dòng)員最佳配對(duì)問(wèn)題
5-5 無(wú)分隔符字典問(wèn)題
5-6 無(wú)和集問(wèn)題
5-7 n色方柱問(wèn)題
5-8 整數(shù)變換問(wèn)題
5-9 拉丁矩陣問(wèn)題
5-10 排列寶石問(wèn)題
5-11 重復(fù)拉丁矩陣問(wèn)題
5-12 羅密歐與朱麗葉的迷宮問(wèn)題
5-13 工作分配問(wèn)題
5-14 布線問(wèn)題
5-15 最佳調(diào)度問(wèn)題
5-16 無(wú)優(yōu)先級(jí)運(yùn)算問(wèn)題
5-17 世界名畫陳列館問(wèn)題
5-18 世界名畫陳列館問(wèn)題(不重復(fù)監(jiān)視)
5-19 算m點(diǎn)問(wèn)題
5-20 部落衛(wèi)隊(duì)問(wèn)題
5-21 子集樹(shù)問(wèn)題
5-22 0-1背包問(wèn)題
5-23 排列樹(shù)問(wèn)題
5-24 一般解空間搜索問(wèn)題
5-25 最短加法鏈問(wèn)題
第6章 分支限界法
算法分析題6
6-1 0-1背包問(wèn)題的棧式分支限界法
6-2 釋放結(jié)點(diǎn)空間的隊(duì)列式分支限界法
6-3 及時(shí)刪除不用的結(jié)點(diǎn)
6-4 用最大堆存儲(chǔ)活結(jié)點(diǎn)的優(yōu)先隊(duì)列式分支限界法
6-5 釋放結(jié)點(diǎn)空間的優(yōu)先隊(duì)列式分支限界法
6-6 團(tuán)頂點(diǎn)數(shù)的上界
6-7 團(tuán)頂點(diǎn)數(shù)改進(jìn)的上界
6-8 修改解旅行售貨員問(wèn)題的分支限界法
6-9 解旅行售貨員問(wèn)題的分支限界法中保存已產(chǎn)生的排列樹(shù)
6-10 電路板排列問(wèn)題的隊(duì)列式分支限界法
算法實(shí)現(xiàn)題6
6-1 最小長(zhǎng)度電路板排列問(wèn)題
6-2 最小權(quán)頂點(diǎn)覆蓋問(wèn)題
6-3 無(wú)向圖的最大割問(wèn)題
6-4 最小重量機(jī)器設(shè)計(jì)問(wèn)題
6-5 運(yùn)動(dòng)員最佳配對(duì)問(wèn)題
6-6 n皇后問(wèn)題
6-7 布線問(wèn)題
6-8 最佳調(diào)度問(wèn)題
6-9 無(wú)優(yōu)先級(jí)運(yùn)算問(wèn)題
6-10 世界名畫陳列館問(wèn)題
6-11 子集空間樹(shù)問(wèn)題
6-12 排列空間樹(shù)問(wèn)題
6-13 一般解空間的隊(duì)列式分支限界法
6-14 子集空間樹(shù)問(wèn)題
6-15 排列空間樹(shù)問(wèn)題
6-16 一般解空間的優(yōu)先隊(duì)列式分支限界法
6-17 推箱子問(wèn)題
第7章 概率算法
算法分析題7
7-1 模擬正態(tài)分布隨機(jī)變量
7-2 隨機(jī)抽樣算法
7-3 隨機(jī)產(chǎn)生m個(gè)整數(shù)
7-4 集合大小的概率算法
7-5 生日問(wèn)題
7-6 易驗(yàn)證問(wèn)題的拉斯維加斯算法
7-7 用數(shù)組模擬有序鏈表
7-8 O(n3/2)舍伍德型排序算法
7-9 n后問(wèn)題解的存在性
7-10 整數(shù)因子分解算法
7-11 非蒙特卡羅算法的例子
7-12 重復(fù)3次的蒙特卡羅算法
7-13 集合隨機(jī)元素算法
7-14 由蒙特卡羅算法構(gòu)造拉斯維加斯算法
7-15 產(chǎn)生素?cái)?shù)算法
7-16 矩陣方程問(wèn)題
算法實(shí)現(xiàn)題7
7-1 模平方根問(wèn)題
7-2 素?cái)?shù)測(cè)試問(wèn)題
7-3 集合相等問(wèn)題
7-4 逆矩陣問(wèn)題
7-5 多項(xiàng)式乘積問(wèn)題
7-6 皇后控制問(wèn)題
7-7 3-SAT問(wèn)題
7-8 戰(zhàn)車問(wèn)題
第8章 線性規(guī)劃與網(wǎng)絡(luò)流 算法分析題8
8-1 線性規(guī)劃可行區(qū)域無(wú)界的例子
8-2 單源最短路與線性規(guī)劃
8-3 網(wǎng)絡(luò)最大流與線性規(guī)劃
8-4 最小費(fèi)用流與線性規(guī)劃
8-5 運(yùn)輸計(jì)劃問(wèn)題
8-6 單純形算法
8-7 邊連通度問(wèn)題
8-8 有向無(wú)環(huán)網(wǎng)絡(luò)的最大流
8-9 無(wú)向網(wǎng)絡(luò)的最大流
8-10 最大流更新算法
8-11 混合圖歐拉回路問(wèn)題
8-12 單源最短路與最小費(fèi)用流
8-13 中國(guó)郵路問(wèn)題
算法實(shí)現(xiàn)題8
8-1 飛行員配對(duì)方案問(wèn)題
8-2 太空飛行計(jì)劃問(wèn)題
8-3 最小路徑覆蓋問(wèn)題
8-4 魔術(shù)球問(wèn)題
8-5 圓桌問(wèn)題
8-6 最長(zhǎng)遞增子序列問(wèn)題
8-7 試題庫(kù)問(wèn)題
8-8 機(jī)器人路徑規(guī)劃問(wèn)題
8-9 方格取數(shù)問(wèn)題
8-10 餐巾計(jì)劃問(wèn)題
8-11 航空路線問(wèn)題
8-12 軟件補(bǔ)丁問(wèn)題
8-13 星際轉(zhuǎn)移問(wèn)題
8-14 孤島營(yíng)救問(wèn)題
8-15 汽車加油行駛問(wèn)題
8-16 數(shù)字梯形問(wèn)題
8-17 運(yùn)輸問(wèn)題
8-18 分配工作問(wèn)題
8-19 負(fù)載平衡問(wèn)題
8-20 最長(zhǎng)k可重區(qū)間集問(wèn)題
8-21 最長(zhǎng)k可重線段集問(wèn)題
參考文獻(xiàn)
章節(jié)摘錄
版權(quán)頁(yè): 插圖: 問(wèn)題描述:1944年,特種兵麥克接到國(guó)防部的命令,要求立即趕赴太平洋上的一個(gè)孤島,營(yíng)救被敵軍俘虜?shù)拇蟊鸲鳌H鸲鞅魂P(guān)押在一個(gè)迷宮里,迷宮地形復(fù)雜,但幸好麥克得到了迷宮的地形圖。迷宮的外形是一個(gè)長(zhǎng)方形,其南北方向被劃分為N行,東西方向被劃分為M列,于是整個(gè)迷宮被劃分為N×M個(gè)單元。每一個(gè)單元的位置可用一個(gè)有序數(shù)對(duì)(單元的行號(hào),單元的列號(hào))來(lái)表示。南北或東西方向相鄰的2個(gè)單元之間可能互通,也可能有一扇鎖著的門,或者是一堵不可逾越的墻。迷宮中有一些單元存放著鑰匙,并且所有的門被分成P類,打開(kāi)同一類的門的鑰匙相同,不同類門的鑰匙不同。 大兵瑞恩被關(guān)押在迷宮的東南角,即(N,M)單元里,并已經(jīng)昏迷。迷宮只有一個(gè)入口,在西北角。也就是說(shuō),麥克可以直接進(jìn)入(1,1)單元。另外,麥克從一個(gè)單元移動(dòng)到另一個(gè)相鄰單元的時(shí)間為1,拿取所在單元鑰匙的時(shí)間及用鑰匙開(kāi)門的時(shí)間可忽略不計(jì)。
編輯推薦
《國(guó)家精品課程教材?高等學(xué)校規(guī)劃教材:計(jì)算機(jī)算法設(shè)計(jì)與分析習(xí)題解答(第2版)》內(nèi)容豐富,理論聯(lián)系實(shí)際,可作為高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、信息安全、信息與計(jì)算科學(xué)等專業(yè)本科生和研究生學(xué)習(xí)計(jì)算機(jī)算法設(shè)計(jì)的輔助教材,也是工程技術(shù)人員和自學(xué)者的參考書。
圖書封面
評(píng)論、評(píng)分、閱讀與下載
計(jì)算機(jī)算法設(shè)計(jì)與分析習(xí)題解答 PDF格式下載