目录 1
序 1
前言 1
第一部分 问题 1
第1章 序曲 1
问题1.1 最长平台（PLATEAU.C） 1
问题1.2 支配值数目（GT_COUNT.C） 1
问题1.3 等值数目（EQ_COUNT.C） 2
问题1.4 两数组最短距离（MINDIST.C） 2
问题1.5 等值首尾和（HEADTAIL.C） 3
第2章 数字问题 4
问题2.1 Armstrong数（ARMS1.C,ARMS2.C） 4
问题2.2 数字谜（TRENTE.C） 6
问题2.3 求质数（PRIME1.C） 7
问题2.4 筛法（SIEVE.C） 8
问题2.5 线性筛法（L_SIEVE.C） 9
问题2.6 因子分解（FACTOR.C） 10
问题2.7 数值自乘递归解（R_POWER.C） 10
问题2.8 数值自乘非递归解（I_POWER.C） 11
问题2.9 Fibonacci数非递归解（FIB_IT.C） 11
问题2.10 快速Fibonacci数算法（FIB_MT.C） 11
问题2.11 扩充Fibonacci数（EX_FIB.C） 12
问题2.12 二项式系数加法解（CNR_ADD.C） 13
问题2.13 快速二项式系数算法（CNR_LOG.C） 15
问题2.14 快速阶乘运算（FACTLOG2.C） 15
问题2.15 更快的阶乘算法（FACTLOG.C） 17
问题2.16 连续整数的固定和（GIVENSUM.C） 17
问题3.1 列出所有子集（DIRECT.C） 19
问题3.2 列出所有子集——字典顺序（LEXICAL.C） 19
第3章 排列、组合与集合 19
问题3.3 产生Gray码（GRAYCODE.C） 20
问题3.4 产生所有排列——旋转法（PERMUT_R.C） 21
问题3.5 产生所有排列——字典顺序（PERMU_LR.C） 22
问题3.6 所有K个元素的子集（KSUBSET.C） 23
问题3.7 集合的所有分割方式（SETPART.C） 24
问题3.8 整数的所有不同分割数目（INTPART＃.C） 25
问题3.9 整数的分割方式（INTPART.C） 26
问题4.1 寻找脚码（ISEARCH.C） 27
第4章 查找 27
问题4.2 寻找固定的和（FIXSUM.C） 27
问题4.4 寻找极小值（CYCLEMIN.C） 28
问题4.3 无限式查找（INF_SRCH.C） 28
问题4.5 两个数组的中位数（MEDIAN2.C） 29
问题4.7 3个数组的共同元素（SEARCH3.C） 30
问题4.6 寻找中间值（B_SEARCH.C） 30
问题4.9 查找矩阵（M_SEARCH.C） 31
问题4.8 寻找最小与次小元素（1ST 2ND.C） 31
问题4.11 最大方块区域（MAXSQR.C,MAXSQR2.C） 32
问题4.10 表示成两个数平方和（TWOSQUAR.C） 32
问题5.1 二分插入法（BINSERT.C） 34
第5章 排序 34
问题5.2 Shell法（SHELL.C） 36
问题5.3 快速排列法（QSORT.C） 37
问题5.4 保持等值的原来顺序（QSORT_L.C） 37
问题5.5 非递归、无堆栈快速排列法（QSORT_I.C） 38
问题5.6 求中位数（MEDIAN1.C） 39
问题5.7 堆积法（HEAPSORT.C） 39
问题5.8 改良的堆积法（HEAP_NEW.C） 43
问题5.9 合并法（M_SORT.C） 44
问题5.10 桶子法（BUCKET.C） 44
问题5.11 单一重复元素排序（LOT_DUP.C） 45
问题5.12 均匀重复元素排序（LOG_DUP.C） 45
问题5.13 堆积式合并（HEAPMERG.C） 46
问题5.14 检查数组元素是否相异（UNIQUE.C） 47
问题5.15 数组中和为零的段落（ZEROSUM.C） 47
问题5.17 宴会中访问数目的极大值（MAXVISIT.C） 48
问题5.16 平面上的极大点（MAXSET.C） 48
问题5.18 包含在其他区间中的区间（CONTAIN.C） 49
问题6.1 括号匹配问题（PARCOUNT.C） 51
问题6.2 转换成后继式写法（POLISH.C） 51
第6章 字符串 51
问题6.3 计算前置式写法（PREFIX.C） 52
问题6.4 Knuth-Morris-Pratt法寻找字符串（KMP.C） 53
问题6.5 Boyer-Moore法寻找字符串（BM.C） 57
问题6.6 所谓的h-序列（RH_SEQ.C,H_SEQ.C） 58
问题6.7 寻找部分序列（SUBSEQ.C） 59
问题6.8 最长重复部分序列（MAX_REPS.C） 59
问题6.9 最长共同部分序列（LCS.C） 60
问题6.10 字符串编修（STREDIT.C） 61
问题6.11 产生无连续重复部分的字符串（DISTSEQ.C） 62
第7章 其他问题 63
问题7.1 Buffon丢针问题（BUFFON.C） 63
问题7.2 三色旗问题（FLAG.C） 63
问题7.3 字符串列整数的转换（X_ATOI.C） 64
问题7.5 无限位数算术（ARITH.C） 65
问题7.4 整数类型列的极值（LIMITS.C） 65
问题7.6 线性表示的矩阵相乘（MATMUL.C） 66
问题7.7 对称表示的矩阵相乘（MATMUL_S.C） 66
问题7.8 找零钱问题（CHANGE.C） 67
问题7.9 背包问题（KNAPSACK.C） 68
问题7.10 最佳矩阵相乘顺序（PRODSEQ.C） 68
问题7.11 最短路径问题（SHORTEST.C） 69
问题7.12 产生匹配括号的字符串（PAR_GEN.C） 70
问题7.13 稳定伴侣问题（STABLE.C） 71
问题7.14 单调矩阵的极值（MONO_MAX.C） 72
问题7.15 向量分类（CLASSIFY.C） 73
第8章 游戏问题 75
问题8.1 奇数阶魔方阵（MAGIC_O.C） 75
问题8.2 单偶数阶魔方阵（MAGIC_SE.C） 77
问题8.3 双偶数阶魔方阵（MAGIC_DE.C） 78
问题8.4 N后问题公式解（N_QUEEN1.C） 80
问题8.5 N后问题递归解（N_QUEENR.C） 81
问题8.6 武士巡逻（KNIGHT.C） 83
问题8.7 环游世界（HAMILTON.C） 84
问题8.8 一笔画（EULER.C） 85
问题8.9 非递归河内之塔（HANOI_I.C） 86
问题8.10 生命游戏（LIFE.C） 87
问题9.2 寻找长方形（RECT.C） 89
问题9.1 等量正负号段落（BALANCE.C） 89
第9章 终曲 89
问题9.3 多边形的直径（DIAMETER.C） 90
问题9.4 机器人旋转角度（TURNS.C） 91
问题9.5 最大涵盖距离（MAXCOVER.C） 92
问题9.6 最大连续元素和（MAXSUM.C,MAXSUM1.C） 93
问题9.8 寻找名人（SINK.C） 94
问题9.7 最大连续元素积（MAXPROD.C） 94
问题9.10 寻找1对1函数（1TO1.C） 95
问题9.9 投票问题（VOTING.C） 95
问题9.12 最长递增部分序列（LIS.C） 96
问题9.11 寻找支配元素（DOMINATR.C） 96
问题1.1 最长平台（PLATEAU.C） 98
第10章 序曲 98
第二部分 解答 98
问题1.2 支配值数目（GT_COUNT.C） 99
问题1.3 等值数目（EQ_COUNT.C） 101
问题1.4 两数组最短距离（MINDIST.C） 103
问题1.5 等值首尾和（HEADTAIL.C） 104
问题2.1 Armstrong数（ARMS1.C,ARMS2.C） 106
第11章 数字问题 106
问题2.2 数字谜（TRENTE.C） 109
问题2.3 求质数（PRIME1.C） 114
问题2.4 筛法（SIEVE.C） 118
问题2.5 线性筛法（L_SIEVE.C） 120
问题2.6 因子分解（FACTOR.C） 123
问题2.7 数值自乘递归解（R_POWER.C） 125
问题2.8 数值自乘非递归解（I_POWER.C） 127
问题2.9 Fibonacci数非递归解（FIB_IT.C） 129
问题2.10 快速Fibonacci数算法（FIB_MT.C） 130
问题2.11 扩充Fibonacci数（EX_FIB.C） 133
问题2.12 二项式系数加法解（CNR_ADD.C） 136
问题2.13 快速二项式系数算法（CNR_LOG.C） 138
问题2.14 快速阶乘运算（FACTLOG2.C） 141
问题2.15 更快的阶乘算法（FACTLOG.C） 144
问题2.16 连续整数的固定和（GIVENSUM.C） 148
第12章 排列、组合与集合 152
问题3.1 列出所有子集（DIRECT.C） 152
问题3.2 列出所有子集——字典顺序（LEXICAL.C） 154
问题3.3 产生Gray码（GRAYCODE.C） 156
问题3.4 产生所有排列——旋转法（PERMUT_R.C） 161
问题3.5 产生所有排列——字典顺序（PERMU_LR.C） 164
问题3.6 所有K个元素的子集（KSUBSET.C） 166
问题3.7 集合的所有分割方式（SETPARTC） 170
问题3.8 整数的所有不同分割数目（INTPART＃.C） 173
问题3.9 整数的分割方式（INTPART.C） 176
问题4.1 寻找脚码（ISEARCH.C） 180
第13章 查找 180
问题4.2 寻找固定的和（FIXSUM.C） 181
问题4.3 无限式查找（INF_SRCH.C） 183
问题4.4 寻找极小值（CYCLEMIN.C） 186
问题4.5 两个数组的中位数（MEDIAN2.C） 188
问题4.6 寻找中间值（B_SEARCH.C） 191
问题4.7 3个数组的共同元素（SEARCH3.C） 194
问题4.8 寻找最小与次小元素（IST 2ND.C） 196
问题4.9 查找矩阵（M_SEARCH.C） 198
问题4.10 表示成两个数平方和（TWOSQUAR.C） 200
问题4.11 最大方块区域（MAXSQR.C,MAXSQR2.C） 202
第14章 排序 209
问题5.1 二分插入法（BINSERT.C） 209
问题5.2 Shell法（SHELL.C） 212
问题5.3 快速排列法（QSORT.C） 215
问题5.4 保持等值的原来顺序（QSORT_L.C） 219
问题5.5 非递归、无堆栈快速排列法（QSORT_I.C） 224
问题5.6 求中位数（MEDIAN1.C） 228
问题5.7 堆积法（HEAPSORT.C） 231
问题5.8 改良的堆积法（HEAP_NEW.C） 235
问题5.9 合并法（M_SORT.C） 239
问题5.10 桶子法（BUCKET.C） 242
问题5.11 单一重复元素排序（LOT_DUP.C） 250
问题5.12 均匀重复元素排序（LOG_DUP.C） 252
问题5.13 堆积式合并（HEAPMERG.C） 259
问题5.14 检查数组元素是否相异（UNIQUE.C） 266
问题5.15 数组中和为零的段落（ZEROSUM.C） 267
问题5.16 平面上的极大点（MAXSET.C） 269
问题5.17 宴会中访问数目的极大值（MAXVISIT.C） 274
问题5.18 包含在其他区间中的区间（CONTAIN.C） 278
第15章 字符串 284
问题6.1 括号匹配问题（PARCOUNT.C） 284
问题6.2 转换成后继式写法（POLISH.C） 286
问题6.3 计算前置式写法（PREFIX.C） 292
问题6.4 Knuth-Morris-Pratt法寻找字符串（KMP.C） 299
问题6.5 Boyer-Moore法寻找字符串（BM.C） 302
问题6.6 所谓的h-序列（RH_SEQ.C,H_SEQ.C） 306
问题6.7 寻找部分序列（SUBSEQ.C） 309
问题6.8 最长重复部分序列（MAX_REPS.C） 311
问题6.9 最长共同部分序列（LCS.C） 315
问题6.10 字符串编修（STREDIT.C） 320
问题6.11 产生无连续重复部分的字符串（DISTSEQ.C） 325
第16章 其他问题 332
问题7.1 Buffon丢针问题（BUFFON.C） 332
问题7.2 三色旗问题（FLAG.C） 334
问题7.3 字符串列整数的转换（X_ATOI.C） 338
问题7.4 整数类型列的极值（LIMITS.C） 340
问题7.5 无限位数算术（ARITH.C） 343
问题7.6 线性表示的矩阵相乘（MATMUL.C） 349
问题7.7 对称表示的矩阵相乘（MATMUL_S.C） 352
问题7.8 找零钱问题（CHANGE.C） 355
问题7.9 背包问题（KNAPSACK.C） 357
问题7.10 最佳矩阵相乘顺序（PRODSEQ.C） 362
问题7.11 最短路径问题（SHORTEST.C） 367
问题7.12 产生匹配括号的字符串（PAR_GEN.C） 372
问题7.13 稳定伴侣问题（STABLE.C） 375
问题7.14 单调矩阵的极值（MONO_MAX.C） 379
问题7.15 向量分类（CLASSIFY.C） 382
第17章 游戏问题 388
问题8.1 奇数阶魔方阵（MAGIC_O.C） 388
问题8.2 单偶数阶魔方阵（MAGIC.SE.C） 391
问题8.3 双偶数阶魔方阵（MAGIC DE.C） 395
问题8.4 N后问题公式解（N_QUEEN1.C） 397
问题8.5 N后问题递归解（N_QUEENR.C） 402
问题8.6 武士巡逻（KNIGHT.C） 408
问题8.7 环游世界（HAMILTON.C） 415
问题8.8 一笔画（EULER.C） 421
问题8.9 非递归河内之塔（HANOI_I.C） 431
问题8.10 生命游戏（LIFE.C） 438
问题9.1 等量正负号段落（BALANCE.C） 445
第18章 终曲 445
问题9.2 寻找长方形（RECT.C） 448
问题9.3 多边形的直径（DIAMETER.C） 450
问题9.4 机器人旋转角度（TURNS.C） 453
问题9.5 最大涵盖距离（MAXCOVER.C） 457
问题9.6 最大连续元素和（MAXSUM.C,MAXSUM1.C） 460
问题9.7 最大连续元素积（MAXPROD.C） 465
问题9.8 寻找名人（SINK.C） 467
问题9.9 投票问题（VOTING.C） 470
问题9.10 寻找1对1函数（1TO1.C） 474
问题9.11 寻找支配元素（DOMINATR.C） 477
问题9.12 最长递增部分序列（LIS.C） 479
参考文献 483