国际大学生程序设计竞赛例题解 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