算法設計與分析

本書介紹計算機算法分析與設計的基本概念、典型算法和經典案例，使讀者掌握常用的算法分析與設計技術。全書共分為8章，第1章介紹算法的概念與特徵，算法分析與設計的相關數學基礎，算法複雜性的概念、表示方法和衡量刻度標準；第2章講述了算法相關的數據組織方式和組織結構，包括線性表、樹、二叉搜索樹、紅黑樹、B樹、散列表、最小生成樹等；第3～8章分別介紹分治法、動態規劃法、貪心算法、回溯法、分支限界法、概率分析和隨機算法等經典算法，並通過典型案例加以分析和説明。本書給出了各種算法的具體代碼實現，其中，分治法、動態規劃法採用傳統的類C語言偽代碼進行描述；貪心算法、回溯法、分支限界法、概率分析和隨機算法則採用C#語言實現。

本書適合作為高等學校計算機及相關專業“算法設計與分析”課程的教材，也可供相關專業人員參考使用。 ^[1] 

目錄

第1章算法基礎/1

1.1算法概念與特徵1

1.1.1算法概念1

1.1.2算法特徵1

1.2數學基礎1

1.2.1數學歸納法1

1.2.2取整函數3

1.2.3二項式定理5

1.2.4二項式係數6

1.2.5斐波那契數8

1.2.6生成函數8

1.3算法複雜性分析11

1.3.1算法複雜性概念11

1.3.2算法複雜性刻度標準11

1.3.3算法複雜性耗費標準12

1.3.4漸進表示12

1.3.5漸進記號的常用函數14

1.4排序算法16

1.4.1插入排序16

1.4.2希爾排序16

1.4.3選擇排序17

1.4.4冒泡排序18

1.4.5合併排序19

1.4.6快速排序19

1.4.7排序算法的穩定性問題20

1.5遞歸與遞推20

1.5.1遞歸20

1.5.2遞推20

第2章信息結構/23

2.1線性表23

2.1.1線性表的操作23

2.1.2棧和隊列24

2.1.3表的存儲24

2.1.4表的操作25

2.2樹26

2.2.1樹的定義26

2.2.2二叉樹27

2.2.3二叉樹的遍歷28

2.3二叉搜索樹29

2.3.1二叉搜索樹的建立與插入29

2.3.2二叉搜索樹的刪除31

2.3.3二叉搜索樹的查找32

2.3.4二叉搜索樹操作算法複雜度分析33

2.4紅黑樹33

2.4.1定義34

2.4.2紅黑樹性質34

2.4.3樹結構的調整35

2.4.4插入35

2.4.5刪除38

2.5B樹40

2.5.1定義40

2.5.2B樹插入操作41

2.5.3B樹刪除操作43

2.6散列表46

2.6.1定義46

2.6.2散列表性能分析47

2.6.3散列函數47

2.7最小生成樹47

2.7.1定義47

2.7.2Kruskal算法48

2.7.3Prime算法48

第3章分治法/50

3.1概念50

3.1.1分治法的基本思想50

3.1.2分治法所處理問題的基本特徵51

3.1.3分治算法的實現思路51

3.2折半查找53

3.2.1問題描述53

3.2.2問題分析53

3.2.3問題求解53

3.2.4算法實現54

3.2.5折半查找判定樹55

3.2.6算法複雜度分析55

3.3順序統計56

3.3.1問題描述56

3.3.2問題分析56

3.3.3問題求解56

3.3.4算法實現56

3.3.5算法複雜度分析58

3.4大整數乘法58

3.4.1問題描述58

3.4.2問題分析58

3.4.3分治法求解問題59

3.4.4改進的分治法59

3.5最大子數組問題59

3.5.1問題描述59

3.5.2算法分析60

3.5.3分治法求解最大子數組問題60

3.5.4算法實現60

3.5.5算法複雜性分析61

3.6矩陣乘法61

3.6.1問題描述61

3.6.2問題分析62

3.6.3分治法求解矩陣相乘62

3.6.4Strassen算法實現矩陣乘法63

3.7遞歸式求解63

3.7.1問題描述63

3.7.2代入法求解遞歸式64

3.7.3遞歸樹法求解遞歸式65

3.7.4主方法求解遞歸式66

3.8證明主定理67

3.8.1主定理67

3.8.2主定理遞歸樹表示67

3.8.3主定理證明68

3.9馬的周遊路線問題73

3.9.1問題描述73

3.9.2問題分析73

3.9.3問題求解73

3.9.4求解過程74

3.10循環賽日程安排76

3.10.1問題描述76

3.10.2問題分析76

3.10.3問題求解76

3.10.4算法實現77

3.10.5算法複雜度分析78

第4章動態規劃法/79

4.1概述79

4.1.1概念79

4.1.2算法實現79

4.1.3使用條件及特點80

4.2鋼條切割問題81

4.2.1問題描述81

4.2.2問題分析81

4.2.3問題求解82

4.2.4算法實現82

4.2.5小結83

4.3矩陣連乘問題83

4.3.1問題描述83

4.3.2問題分析83

4.3.3問題求解83

4.3.4算法實現84

4.3.5複雜性分析84

4.4最長公共子序列問題85

4.4.1問題描述85

4.4.2問題分析85

4.4.3問題求解86

4.4.4算法實現86

4.4.5複雜性分析87

4.5最優二叉樹搜索問題87

4.5.1問題描述87

4.5.2問題分析87

4.5.3問題求解88

4.5.4算法實現88

4.6單源最短路徑問題89

4.6.1問題描述89

4.6.2問題分析90

4.6.3問題求解90

4.6.4算法實現91

4.7資源分配問題91

4.7.1問題描述91

4.7.2問題分析91

4.7.3問題求解91

4.7.4算法實現93

4.8多重配置系統可靠性問題93

4.8.1問題描述93

4.8.2問題分析94

4.8.3問題求解94

4.8.4算法實現95

4.9貨郎擔問題96

4.9.1問題描述96

4.9.2問題分析96

4.9.3問題求解96

4.9.4算法實現97

4.9.5複雜性分析98

4.10流水作業車間調度問題98

4.10.1問題描述98

4.10.2問題分析99

4.10.3問題求解99

4.10.4算法實現100

第5章貪心算法/101

5.1概念101

5.1.1貪心算法的基本要素101

5.1.2貪心算法的基本思想101

5.1.3貪心算法的實現過程101

5.1.4適用條件102

5.2揹包問題102

5.2.1問題描述102

5.2.2問題求解102

5.2.3算法實現103

5.2.4算法分析104

5.3帶時限的作業調度問題105

5.3.1問題描述105

5.3.2問題分析105

5.3.3以利潤最大作為貪心策略106

5.3.4以最大時限作為貪心策略107

5.3.5快速調度法108

5.4最佳合併順序109

5.4.1問題描述109

5.4.2問題分析109

5.4.3問題求解109

5.4.4算法實現110

5.4.5算法正確性證明111

5.5磁盤文件的最佳存儲111

5.5.1問題描述111

5.5.2問題分析111

5.5.3問題求解112

5.5.4算法實現113

5.5.5算法分析113

5.6活動安排問題115

5.6.1問題描述115

5.6.2問題分析115

5.6.3問題求解116

5.6.4算法實現117

5.6.5算法分析117

5.7哈夫曼編碼118

5.7.1概述118

5.7.2前綴碼118

5.7.3哈夫曼編碼方案119

5.7.4算法實現120

5.7.5算法分析120

5.8擬陣121

5.8.1擬陣定義121

5.8.2加權擬陣上的貪心算法122

5.8.3用擬陣求解帶時限的作業調度問題123

第6章回溯法/125

6.1概述125

6.1.1概念125

6.1.2基本思想125

6.1.3回溯法的基本理論125

6.1.4實現步驟126

6.2n皇后問題127

6.2.1問題描述127

6.2.2問題分析127

6.2.3問題求解127

6.2.4算法實現128

6.3子集和問題129

6.3.1問題描述129

6.3.2問題分析129

6.3.3問題求解130

6.3.4算法實現132

6.4圖的M着色問題133

6.4.1問題描述133

6.4.2問題分析133

6.4.3問題求解134

6.4.4算法實現135

6.4.5複雜度分析136

6.501揹包問題136

6.5.1問題描述136

6.5.2問題分析136

6.5.3問題求解137

6.5.4算法實現138

6.6哈密頓迴路問題140

6.6.1問題描述140

6.6.2問題分析140

6.6.3問題求解141

6.6.4算法實現142

6.7連續郵資問題143

6.7.1問題描述143

6.7.2問題分析143

6.7.3問題求解144

6.7.4算法實現144

第7章分支限界法/147

7.1概述147

7.1.1基本思想147

7.1.2與回溯法的區別147

7.1.3剪枝函數147

7.1.4實現步驟147

7.1.5求解目標148

7.1.6搜索策略148

7.1.7分支限界法的分類148

7.215迷問題149

7.2.1問題描述149

7.2.2問題分析149

7.2.3問題求解149

7.2.4算法實現152

7.2.5算法複雜度分析156

7.3貨郎擔問題157

7.3.1問題描述157

7.3.2問題分析157

7.3.3問題求解159

7.3.4算法實現161

7.401揹包問題164

7.4.1問題描述164

7.4.2問題分析164

7.4.3問題求解165

7.4.4算法實現167

7.5同順序任務加工問題170

7.5.1問題描述170

7.5.2問題分析170

7.5.3n項任務m台處理機任務啓動時間171

7.5.4問題求解173

7.5.5算法實現174

7.5.6效率分析178

7.6最大團問題178

7.6.1問題描述178

7.6.2問題分析179

7.6.3問題求解179

7.6.4算法實現180

7.7裝載問題182

7.7.1問題描述182

7.7.2問題分析182

7.7.3問題求解183

7.7.4算法實現185

7.8佈線問題187

7.8.1問題描述187

7.8.2問題分析187

7.8.3問題求解188

7.8.4算法實現188

第8章概率分析和隨機算法/193

8.1概念193

8.2隨機數產生方法193

8.2.1隨機數的概念193

8.2.2隨機數的應用194

8.2.3隨機數的產生方法194

8.2.4隨機數生成195

8.2.5常見分佈函數的隨機數的產生196

8.3數值概率算法196

8.3.1用隨機投點法計算π值197

8.3.2計算定積分197

8.3.3解非線性方程組198

8.4蒙特卡羅算法199

8.4.1蒙特卡羅算法思想199

8.4.2蒙特卡羅算法實現步驟199

8.4.3主元素問題200

8.4.4素數測試問題201

8.5拉斯維加斯算法203

8.5.1n皇后問題203

8.5.2隨機排序205

8.5.3求解整數因子分解206

8.6舍伍德算法207

8.6.1元素選擇問題208

8.6.2搜索有序表210

8.6.3跳躍表211

8.7生日悖論215

參考文獻/217

第1章管理信息系統概述/1

1.1信息、管理、管理信息與系統1

1.1.1信息與數據1

1.1.2管理與管理信息3

1.1.3系統3

1.2信息系統4

1.2.1信息系統的概念4

1.2.2信息系統的類型4

1.2.3信息系統與管理5

1.3管理信息系統5

1.3.1管理信息系統的概念5

1.3.2管理信息系統的功能5

1.3.3管理信息系統的特徵6

1.3.4管理信息系統的類型6

1.4管理信息系統的技術基礎7

1.4.1數據處理技術7

1.4.2數據庫技術8

1.4.3計算機網絡技術8

1.5管理信息系統的開發原則、策略和方法8

1.5.1管理信息系統的開發原則8

1.5.2管理信息系統的開發策略9

1.5.3管理信息系統的開發方法9

1.6管理信息系統的典型案例11

1.6.1MIS支持沃爾瑪創造商業奇蹟11

1.6.2海爾集團: 信息化助力創造世界名牌公司12

小結12

習題13

第2章數據庫高級編程/14

2.1SQL Server相關配置14

2.2使用ADO.NET訪問數據庫192.2.1連接數據庫19

2.2.2對數據庫進行添加、修改及刪除操作20

2.2.3查詢數據庫中的數據22

2.2.4數據綁定控件25

2.3Entity Framework基礎知識49

2.3.1從委託到Lambda49

2.3.2Entity Framework架構56

2.4使用Entity Framework訪問數據庫57

2.4.1Entity Framework的安裝57

2.4.2創建數據庫及實體對象模型57

2.4.3數據庫增、刪、改、查操作61

小結66

習題66

第3章系統架構/67

3.1三層架構簡介67

3.2簡單三層架構69

3.2.1數據訪問層69

3.2.2數據訪問通用類庫77

3.2.3實體類庫80

3.2.4業務邏輯層84

3.2.5表示層86

3.3工廠模式三層架構99

3.3.1接口類庫設計100

3.3.2工廠類庫設計102

3.3.3其他層的代碼修改103

小結104

習題105

第4章ASP.NET MVC模式/106

4.1MVC模式簡介106

4.2ASP.NET MVC工作原理108

4.3ASP.NET MVC控制器112

4.4ASP.NET MVC視圖115

4.5ASP.NET MVC模型119

小結124

習題124

第5章前端框架Bootstrap/125

5.1Bootstrap簡介125

5.1.1安裝Bootstrap125

5.1.2Bootstrap的主要特性127

5.1.3Bootstrap在Visual Studio 2019中的應用128

5.2Bootstrap樣式131

5.2.1網格系統131

5.2.2排版141

5.2.3表格143

5.2.4表單146

5.2.5按鈕153

5.2.6圖片156

5.3佈局組件157

5.3.1字體圖標157

5.3.2下拉菜單158

5.3.3輸入框組159

5.3.4導航162

5.3.5其他組件164

5.4JavaScript164

5.4.1標籤頁內容165

5.4.2模態對話框168

5.4.3工具提示和彈出對話框171

小結173

習題173

第6章圖書管理系統案例開發/174

6.1項目描述174

6.1.1項目背景174

6.1.2業務描述174

6.1.3用户描述175

6.2系統需求175

6.2.1需求描述175

6.2.2模塊設計175

6.2.3數據庫設計177

6.3系統實現180

6.3.1技術要點180

6.3.2主要功能模塊及界面設計180

6.4程序打包193

小結199

習題199

第7章超市商品進銷存管理系統案例開發/200

7.1系統需求200

7.2系統設計201

7.2.1模塊設計201

7.2.2數據庫設計201

7.3系統實現202

7.3.1實體數據模型202

7.3.2主界面模塊203

7.3.3商品管理模塊206

7.3.4進貨管理模塊211

7.3.5銷售管理模塊213

7.3.6庫存統計模塊215

7.4技術經驗總結217

7.4.1技術總結217

7.4.2經驗總結217

第8章在線考試系統案例開發/218

8.1項目概述218

8.2系統需求218

8.2.1業務描述218

8.2.2用户描述218

8.2.3功能分析219

8.3系統分析設計220

8.3.1模塊設計220

8.3.2數據庫設計220

8.4技術準備224

8.4.1Excel組件使用224

8.4.2數據庫的隨機排序方法226

8.4.3API的使用226

8.4.4註冊表的使用227

8.4.5控件的代碼生成法228

8.5實體類庫實現228

8.5.1Student類229

8.5.2TestQuestion類230

8.5.3CreatePaperScheme類232

8.5.4TestPaper類233

8.5.5QuestionTypeScore類233

8.5.6Questions類234

8.5.7StudentAnswer類235

8.6數據訪問層實現237

8.6.1DALStudent類237

8.6.2DALTestQuestion類238

8.6.3DALCreatePaperScheme類240

8.6.4DALTestPaper類241

8.6.5DALQuestionTypeScore類241

8.6.6DALQuestions類242

8.6.7DALStudentAnswer類243

8.7業務邏輯層實現246

8.7.1BLLStudent類246

8.7.2BLLTestQuestion類247

8.7.3BLLCreatePaperScheme類248

8.7.4BLLTestPaper類249

8.7.5BLLQuestionTypeScore類249

8.7.6BLLQuestions類250

8.7.7BLLStudentAnswer類251

8.8表示層實現253

8.8.1學生信息管理模塊——“學生信息管理”窗體254

8.8.2學生信息管理模塊——“學生信息編輯”窗體261

8.8.3題庫管理模塊——“題庫管理”窗體263

8.8.4題庫管理模塊——“題庫編輯”窗體269

8.8.5組卷模塊274

8.8.6學生端主界面285

8.8.7學生考試模塊288

8.9技術經驗總結298

8.9.1技術總結298

8.9.2經驗總結298

第9章高校實踐課題管理系統案例開發/299

9.1項目描述299

9.2系統需求分析300

9.2.1總體需求300

9.2.2需求描述301

9.3系統設計308

9.3.1總體設計308

9.3.2業務流程建模309

9.4數據庫設計與實現313

9.4.1數據庫設計313

9.4.2數據庫實現314

9.5系統實現318

9.5.1項目總體實現318

9.5.2實體及數據訪問層實現320

9.5.3管理員模塊實現324

9.5.4教師模塊實現349

9.5.5學生模塊實現370

9.6系統測試379

9.6.1學生管理測試用例379

9.6.2題庫管理測試用例381

9.6.3課題選報測試用例385

9.7技術經驗總結389

9.7.1技術總結389

9.7.2經驗總結389

參考文獻/390 ^[2]