国际大学生程序设计竞赛例题解 3 图论·动态规划算法·综合题专集PDF|Epub|txt|kindle电子书版本网盘下载

国际大学生程序设计竞赛例题解 3 图论·动态规划算法·综合题专集PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章　图论相关知识和基本算法1

1.1 图的基本概念1

1.2　图的邻接矩阵表示和邻接表表示2

1.3　拓扑排序4

1.4　连通分量6

1.5　2-连通分量7

1.6　最短路10

1.6.1 非负边权的单源最短路10

1.6.2　任意边权的单源最短路12

1.6.3　任意边权的所有顶点之间的最短路15

1.7　最大流17

1.8　二分图最大匹配20

第2章　图论例题分析23

2.1　删边问题23

2.1.1　题目描述23

2.1.2　题目分析及算法实现23

2.1.3　参考程序及程序分析24

2.1.4　测试数据及输出结果24

2.2　烦人的幻灯片问题25

2.2.1　题目描述25

2.2.2　题目分析及算法实现26

2.2.3　参考程序及程序分析27

2.2.4　测试数据及输出结果29

2.3　字母排序问题29

2.3.1　题目描述29

2.3.2　题目分析及算法实现30

2.3.3　参考程序及程序分析30

2.3.4　测试数据及输出结果32

2.4　投递问题33

2.4.1　题目描述33

2.4.2　题目分析及算法实现34

2.4.3　参考程序及程序分析34

2.4.4　测试数据及输出结果38

2.5　银河贸易问题40

2.5.1　题目描述40

2.5.2　题目分析及算法实现41

2.5.3　参考程序及程序分析42

2.5.4　测试数据及输出结果44

2.6　安全网络问题45

2.6.1　题目描述45

2.6.2　题目分析及算法实现46

2.6.3　参考程序及程序分析47

2.6.4　测试数据与输出结果49

2.7　交通问题52

2.7.1　题目描述52

2.7.2　题目分析及算法实现53

2.7.3 参考程序及程序分析54

2.7.4　测试数据及输出结果57

2.8　单行道问题59

2.8.1　题目描述59

2.8.2　题目分析及算法实现60

2.8.3　参考程序及程序分析62

2.8.4测试数据及输出结果65

2.9 UNIX的插头问题65

2.9.1　题目描述65

2.9.2　题目分析及算法实现67

2.9.3　参考程序及程序分析69

2.9.4测试数据及输出结果72

2.10　进化树问题72

2.10.1　题目描述72

2.10.2　题目分析及算法实现74

2.10.3　参考程序及程序分析75

2.10.4　测试数据及输出结果75

2.11　破坏行动问题76

2.11.1　题目描述76

2.11.2　题目分析及算法实现76

2.11.3　参考程序及程序分析77

2.11.4　测试数据及输出结果79

2.12　街道的方向问题80

2.12.1　题目描述80

2.12.2　题目分析及算法实现80

2.12.3　参考程序及程序分析82

2.12.4　测试数据及输出结果84

2.13　邮递员投递问题85

2.13.1　题目描述85

2.13.2　题目分析及算法实现86

2.13.3　参考程序及程序分析87

2.13.4　测试数据及输出结果92

2.14　分队问题93

2.14.1　题目描述93

2.14.2　题目分析及算法实现94

2.14.3　参考程序及程序分析94

2.14.4　测试数据及输出结果96

2.15　有根树的同构问题96

2.15.1　题目描述96

2.15.2　题目分析及算法实现97

2.15.3　参考程序及程序分析98

2.15.4　测试数据及输出结果100

2.16　拦截匪徒问题100

2.16.1　题目描述100

2.16.2　题目分析及算法实现101

2.16.3　参考程序及程序分析101

2.16.4　测试数据及输出结果103

第3章　动态规划104

3.1　递归编程104

3.2　动态规划基本原理108

3.3　动态规划常用技巧110

3.3.1　顺推110

3.3.2 递归实现115

3.3.3　子问题编码117

3.3.4　利用散列表记录子问题119

第4章　动态规划例题分析122

4.1　取数字问题122

4.1.1　题目描述122

4.1.2　题目分析及算法实现122

4.1.3　参考程序及程序分析123

4.1.4　测试数据及输出结果124

4.2　分组游戏124

4.2.1　题目描述124

4.2.2　题目分析及算法实现125

4.2.3　参考程序及程序分析127

4.2.4　测试数据及输出结果131

4.3　查找基因序列问题132

4.3.1　题目描述132

4.3.2　题目分析及算法实现132

4.3.3　参考程序及程序分析133

4.3.4　测试数据及输出结果134

4.4　购物问题135

4.4.1　题目描述135

4.4.2　题目分析及算法实现135

4.4.3　参考程序及程序分析136

4.4.4　测试数据及输出结果137

4.5　物品供应问题138

4.5.1　题目描述138

4.5.2　题目分析及算法实现138

4.5.3　参考程序及程序分析139

4.5.4　测试数据及输出结果140

4.6　可怜的绵羊问题141

4.6.1　题目描述141

4.6.2　题目分析及算法实现142

4.6.3　参考程序及程序分析143

4.6.4　测试数据及输出结果145

4.7　不老的传说问题146

4.7.1　题目描述146

4.7.2　题目分析及算法实现146

4.7.3　参考程序及程序分析147

4.7.4　测试数据及输出结果149

4.8　推箱子游戏149

4.8.1　题目描述149

4.8.2　题目分析及算法实现150

4.8.3　参考程序及程序分析157

4.8.4　测试数据及输出结果161

4.9　数字游戏162

4.9.1　题目描述162

4.9.2　题目分析及算法实现162

4.9.3　参考程序及程序分析163

4.9.4　测试数据及输出结果164

4.10　电子眼问题165

4.10.1　题目描述165

4.10.2　题目分析及算法实现165

4.10.3　参考程序及程序分析166

4.10.4　测试数据及输出结果168

4.11　复制书稿问题169

4.11.1 题目描述169

4.11.2　题目分析及算法实现170

4.11.3　参考程序及程序分析170

4.11.4　测试数据及输出结果172

4.12　多米诺骨牌问题173

4.12.1　题目描述173

4.12.2　题目分析及算法实现174

4.12.3　参考程序及程序分析174

4.12.4　测试数据及输出结果176

4.13　求三角形最大面积问题176

4.13.1　题目描述176

4.13.2　题目分析及算法实现177

4.13.3　参考程序及程序分析178

4.13.4　测试数据及输出结果180

4.14采购计划问题181

4.14.1　题目描述181

4.14.2　题目分析及算法实现181

4.14.3　参考程序及程序分析182

4.14.4　测试数据及输出结果186

4.15　巡回演出问题187

4.15.1　题目描述187

4.15.2　题目分析及算法实现188

4.15.3　参考程序及程序分析189

4.15.4　测试数据及输出结果191

4.16　文本压缩问题191

4.16.1　题目描述191

4.16.2　题目分析及算法实现192

4.16.3　参考程序及程序分析193

4.16.4　测试数据及输出结果194

4.17　过桥问题195

4.17.1　题目描述195

4.17.2　题目分析及算法实现196

4.17.3　参考程序及程序分析196

4.17.4　测试数据及输出结果197

4.18　串联电阻问题198

4.18.1　题目描述198

4.18.2　题目分析及算法实现199

4.18.3　参考程序及程序分析200

4.18.4　测试数据及输出结果202

第5章　综合题例题分析204

5.1　判别S表达式问题204

5.1.1　题目描述204

5.1.2　题目分析及算法实现205

5.1.3　参考程序及程序分析205

5.1.4　测试数据及输出结果206

5.2　识别浮点常量问题207

5.2.1　题目描述207

5.2.2　题目分析及算法实现207

5.2.3　参考程序及程序分析210

5.2.4　测试数据及输出结果212

5.3　直角三角形计数问题212

5.3.1　题目描述212

5.3.2　题目分析及算法实现213

5.3.3　参考程序及程序分析213

5.3.4　测试数据及输出结果216

5.4　区间算术问题216

5.4.1　题目描述216

5.4.2　题目分析及算法实现217

5.4.3　参考程序及程序分析218

5.4.4　测试数据及输出结果223

5.5　排列的编码问题223

5.5.1　题目描述223

5.5.2　题目分析及算法实现224

5.5.3　参考程序及程序分析225

5.5.4　测试数据及输出结果226

5.6　求和问题227

5.6.1　题目描述227

5.6.2　题目分析及算法实现227

5.6.3　参考程序及程序分析228

5.6.4　测试数据及输出结果231

5.7　填字游戏232

5.7.1　题目描述232

5.7.2　题目分析及算法实现233

5.7.3　参考程序及程序分析233

5.7.4　测试数据及输出结果238

5.8　猜牌问题239

5.8.1　题目描述239

5.8.2　题目分析及算法实现240

5.8.3　参考程序及程序分析240

5.8.4　测试数据及输出结果241

5.9　天堂之梯问题241

5.9.1　题目描述241

5.9.2　题目分析及算法实现242

5.9.3　参考程序及程序分析242

5.9.4　测试数据及输出结果246

5.10　最短绳长问题246

5.10.1　题目描述246

5.10.2　题目分析及算法实现246

5.10.3　参考程序及程序分析247

5.10.4　测试数据及输出结果251

5.11　小型Basic编译器问题251

5.11.1　题目描述251

5.11.2　题目分析及算法实现253

5.11.3　参考程序及程序分析254

5.11.4　测试数据及输出结果258

5.12　随机数问题258

5.12.1　题目描述258

5.12.2　题目分析及算法实现260

5.12.3　参考程序及程序分析265

5.12.4　测试数据及输出结果268

5.13　锦标赛问题269

5.13.1　题目描述269

5.13.2　题目分析及算法实现270

5.13.3　参考程序及程序分析271

5.13.4　测试数据及输出结果273

5.14　逻辑岛问题273

5.14.1　题目描述273

5.14.2　题目分析及算法实现274

5.14.3　参考程序及程序分析276

5.14.4　测试数据及输出结果280

参考文献281

作者简介282