
本书面向高校学生选讲计算机程序设计经典题解,旨在使学生掌握程序设计的基本方法与技巧,提高通过程序设计解决实际问题的能力。
本书以程序设计求解问题为主线,取材注重典型性与趣味性,题解分类精选,内容新颖丰富。 所选讲的经典题解紧贴程序设计应用实际,紧贴计算机等级考试与程序设计竞赛,包括典型的数值求解,常见的数据处理,有趣的智力游戏,巧妙的模拟探索,新颖的图表创建,实用的近似计算与高精度计算,既有引导入门的基础题、常规题,也有难度较大的综合题、引申题与部分经典名题,难度适宜,深入浅出。
本书选讲程序设计题解,突出算法设计思路与不同程序设计的对照比较,程序设计选用目前各高校使用最广的 C (VC) , VFP (FoxPro)等语言完成,注重程序的结构化与可读性。对其中有些经典问题采用多种算法求解与多个程序实现,以适应计算机基础不同的读者学习与研究。
本书适合高校本专科学生作为计算机程序设计应用课程案例教学,可供各级程序设计选拔赛、计算机等级考试与计算机程序员水平考试复习参考,也可供中学信息学(计算机)奥林匹克指导与IOI, NOI培训选用。
以计算机为核心的信息科学技术的迅猛发展与广泛应用,正在对人类社会的发展进程以至人们的工作方式与思维方式的改变产生深远的影响。进入信息社会,作为人类智慧的结晶与人脑功能的延伸,计算机已经成为人类进行复杂计算与模拟探索的“通用智能工具”,广泛应用于信息社会的各个领域,并发挥着越来越大的不可替代的作用。
从当前高校各专业计算机课程的系统开设,到中小学信息技术(计算机)课的相继开出,说明了计算机作为一种新的文化,正在神州大地广泛普及。顺应信息技术不断创新与计算机教育不断深入的潮流,帮助包括各大、中专在校学生在内的广大青少年逐步掌握计算机的基本理论与基本技能,在程序设计中熟悉基本算法,开拓求解思路,解决实际问题,培养创新意识,不断提高程序设计水平与应用求解能力,是我们计算机教育工作者义不容辞的职责。
继实施全国计算机专业技术资格与水平考试之后,国家教育部考试中心推出了面向社会的全国计算机等级考试(1-4级),各省市也相继实施了面向高校非计算机专业学生的计算机水平等级考试。同时,高等学校组织的各种计算机程序设计竞赛正在逐步推出。大、中专在校学生在学习了计算机基础以及某些计算机高级语言的基础上,面临这一系列的计算机考试与竞赛,其中的一个重点就是程序设计,难点就是通过程序设计解决实际问题。通常程序设计课堂教学以语法为主线,问题求解薄弱,题型表现单调,学生程序设计思路狭窄,设计程序解决实际问题的能力与设计变通能力较低,很多学生难以适应这些程序设计考试,甚至在程序设计竞赛中表现得无所适从。为此,作为程序设计课堂教学的一个案例式改革与补充,笔者在本书中尝试以程序设计求解问题为主线,取材注重典型性与趣味性,题型丰富多彩,内容新颖丰富。分类精选的程序设计中数百个经典题解紧贴程序设计应用实际,紧贴计算机等级考试与程序设计竞赛,包括典型的数值求解,常见的数据处理,有趣的智力游戏,巧妙的模拟探索,新颖的图表创建,实用的近似计算与高精度计算,既有引导入门的基础题、常规题,也有难度较大的综合题、引申题与部分经典名题,难度适宜,深入浅出。部分题解取自各届国际国内信息学(计算机) 奥林匹克与各类程序设计竞赛,同时参考了网上读者集中探讨的程序设计热点问题,有利于高校学生与计算机爱好者在计算机实例求解上开阔视野,在程序设计思路开拓与应用技巧上有一个深层次的练习提高。
为了开拓程序设计思路,本书对每一个题解作了设计思路与应用算法解析。题解所应用的算法为常用的穷举、递推、递归、回溯与动态规划等,一般非计算机专业学生可了解与掌握其中大部分题解。对算法的专业知识要求较高与程序设计技巧较强的部分题解,可作为课后的专题研究或课程设计选用。
题解程序采用目前高校学生使用率最高的 C, VFP (FoxPro)两种语言编写,其中C程序一般可在VC环境下运行。对其中有些典型问题,采用了这两种语言以不同算法与表现形式设计出不同的求解程序,以加深读者对不同算法的理解与不同程序的比较,以适应计算机基础不同的读者学习与探究。在各个题解程序设计之后,尽可能给出问题的输出结果或运行示例,以帮助读者对所求解的问题与设计的程序有更清晰的了解。
为方便读者查阅程序设计,附录中列出了C语言和VFP的语法提要与常用函数。
本书适合高校本专科学生作为计算机程序设计应用课程案例教学,可供各级程序设计选拔赛与国际大学生程序设计竞赛(ACM)、计算机等级考试与计算机程序员水平考试复习参考,也可供中学信息学(计算机)奥林匹克指导与IOI, NOI及各省程序设计竞赛培训选用。
在书稿的编著过程中,湖南理工学院的周持中教授、王岳斌教授与郭华老师审阅了书稿,提出了很好的修改意见,刘志辉与唐球同学阅读了部分书稿并运行了相关程序,笔者在此一并深表感谢。
尽管每一个题解都经反复检查,每一个程序都经多次运行调试,因涉及内容较广,难免存在差错,恳请读者指正。
杨克昌
2007年8月于岳阳南湖
第1章 基本和积计算1
1.1 代数和1
1.1.1 整数求和1
1.1.2 调和级数部分和4
1.1.3 实数求和7
1.2 幂与阶乘8
1.2.1 幂与幂的和8
1.2.2 阶乘与阶乘之和9
1.2.3 阶乘和数11
1.3 和积综合计算13
1.3.1 求常数e13
1.3.2 组合数计算14
1.3.3 分数四则运算16
1.4 解不等式18
1.4.1 立方和不等式18
1.4.2 调和级数不等式19
1.4.3 平方根不等式 20
1.5 和积应用题解22
1.5.1 计算电费22
1.5.2 舍罕王的失算23
1.5.3 等效电阻计算25
1.5.4 产值翻番25
1.5.5 个人所得税27
1.5.6 定积分计算28
第2章 特殊整数探求31
2.1 最大公约数与最小公倍数31
2.2 平方数34
2.2.1 分段和平方34
2.2.2 金蝉平方36
2.2.3 巧妙平方37
2.2.4 3组平方40
2.3 勾股数与长方体数43
2.3.1 勾股数43
2.3.2 倒立的勾股数46
2.3.3 长方体数47
2.4 水仙花数与自方幂数49
2.4.1 水仙花数与玫瑰花数49
2.4.2 自方幂数综合求解50
2.5 完全数与相亲数51
2.5.1 完全数51
2.5.2 相亲数探求54
2.6 素数57
2.6.1 区间素数57
2.6.2 孪生素数60
2.6.3 梅森尼数61
2.6.4 金蝉素数63
2.6.5 可逆素数65
2.6.6 合数世纪66
第3章 数式集锦69
3.1 逆序式69
3.1.1 逆序积式69
3.1.2 倍逆序式71
3.2 优美等式73
3.2.1 优美和式73
3.2.2 优美乘积式76
3.3 分数式78
3.3.1 桥本分数式78
3.3.2 埃及分数式81
3.4 整数拆分83
3.4.1 拆分为若干个正整数可重复之和83
3.4.2 拆分为前若干个正整数不重复之和87
3.4.3 拆分为若干个指定正整数不重复之和89
3.5 分解质因数92
3.6 数制转换94
3.6.1 十进制转换为p进制94
3.6.2 p进制转换为n进制97
第4章 数列与数阵100
4.1 真分数递增序列100
4.2 等差素数列102
4.3 递推数列104
4.3.1 斐波那契数列104
4.3.2 幂序列106
4.3.3 分数数列107
4.3.4 双关系递推数列109
4.3.5 复杂递推数列111
4.4 寻求递推关系解题113
4.4.1 汉诺塔113
4.4.2 猴子爬山116
4.4.3 粒子裂变119
4.4.4 购票排队121
4.5 杨辉三角形122
4.6 矩阵运算125
4.6.1 矩阵的和与转置125
4.6.2 矩阵的积126
4.7 方阵128
4.7.1 折叠方阵128
4.7.2 旋转方阵129
4.8 幻方132
4.8.1 n阶幻方132
4.8.2 三阶素数幻方134
4.8.3 4阶可逆素数方阵 136
第5章 数据处理138
5.1 预测与判断138
5.1.1 身高预测138
5.1.2 体型判断139
5.2 数据转化140
5.2.1 分数化小数 140
5.2.2 金额大写141
5.3 字符串处理142
5.3.1 字符串逆序与纵列显示142
5.3.2 字符串分类统计144
5.3.3 求若干个字符串的最长公共子串145
5.4 分类与统计146
5.4.1 成绩分类统计146
5.4.2 大奖赛现场统分147
5.4.3 二组均分149
5.5 数据表操作152
5.5.1 记录位置交换与字段位置交换152
5.5.2 让数据表自动填上排序名次154
5.6 整数规则转化156
5.6.1 3x+1转化156
5.6.2 黑洞数158
5.6.3 回文数161
5.7 排列组合165
5.7.1 排列实现165
5.7.2 一类复杂排列探索167
5.7.3 组合实现170
5.7.4 允许重复的组合173
5.8 报数处理175
5.8.1 围圈循环报数175
5.8.2 围圈报数中的无忧位与绝望位177
5.8.3 列队顺逆报数181
5.9 搜索计数183
5.9.1 地图扫描183
5.9.2 串正方形与串立方体统计185
第6章 方程求解188
6.1 解一元二次方程188
6.1.1 水槽注水问题188
6.1.2 一般一元二次方程求解189
6.2 解一次方程组190
6.2.1 鸡兔同笼190
6.2.2 羊犬鸡兔问题191
6.3 解一次不定方程(组)192
6.3.1 数字魔术192
6.3.2 百鸡问题193
6.3.3 整币兑零195
6.3.4 韩信点兵198
6.4 解高次方程与超越方程200
6.4.1 牛顿迭代法求解高次方程200
6.4.2 符号判定法求解超越方程201
6.5 水手分椰子203
6.6 解佩尔方程206
6.6.1 试值判别法求解206
6.6.2 应用连分数求解208
第7章 最值求解213
7.1 条件最值213
7.1.1 积最大的整数分解213
7.1.2 平方和最大值214
7.1.3 指数和最小值216
7.2 函数最值218
7.2.1 离散函数最值求解218
7.2.2 连续函数最值求解220
7.3 最优操作221
7.3.1 数列压缩221
7.3.2 删数字222
7.4 几何最值223
7.4.1 圆木漂流223
7.4.2 智能甲虫225
7.4.3 点的覆盖圆227
7.5 背包问题228
7.5.1 可拆背包问题228
7.5.2 0/1背包问题230
7.6 最优路径搜索232
7.6.1 点数值问题的最优路径233
7.6.2 边数值问题的最优路径236
7.7 矩形优化剪切240
第8章 高精度计算244
8.1 斐波那契序列与卢卡斯序列的高精度计算245
8.2 高精度综合计算248
8.2.1 分数的高精度计算248
8.2.2 阶乘与幂的高精度计算249
8.3 尾数前移求解251
8.4 乘数探求252
8.4.1 积为n个1252
8.4.2 积为01串253
8.5 连写数256
8.5.1 增连数257
8.5.2 降连数258
8.6 守形数261
8.7 高精度开方265
8.7.1 高精度开平方265
8.7.2 高精度开立方266
8.8 求圆周率π268
第9章 模拟与探索271
9.1 均数奇观271
9.2 操作模拟272
9.2.1 翻币272
9.2.2 洗牌274
9.2.3 黑白棋子移动276
9.2.4 泊松分酒278
9.3 六六顺280
9.4 RDB刻度分布模型探索285
9.4.1 古尺刻度探秘286
9.4.2 RDB尺刻度线性模型探索288
9.4.3 RDB环刻度线性模型探索290
9.5 猜想验证291
9.5.1 哥德巴赫猜想292
9.5.2 多项式素数猜想293
9.6 模拟取石子游戏294
9.6.1 巴什游戏294
9.6.2 外索夫游戏296
9.7 环数链298
9.7.1 n环相亲数链298
9.7.2 环素数300
9.7.3 德布鲁金环序列301
第10章 图表创建306
10.1 常规数据表306
10.1.1 九九乘法表306
10.1.2 p进制乘法表307
10.1.3 平方根表309
10.2 特定数据表310
10.2.1 万年历310
10.2.2 编制循环赛的“贝格尔”表314
10.3 数字方螺线 316
10.4 模拟发扑克牌320
10.4.1 发升级牌320
10.4.2 发桥牌321
10.5 曲线图案323
10.5.1 人体生理三节律图323
10.5.2 函数y=sin(x)/x图像327
10.6 动态图案328
10.6.1 大小形态变化的金字塔328
10.6.2 转圈的梯形332
10.6.3 上下相对移动的菱形334
10.7 圆形图336
10.7.1 奥运五环旗336
10.7.2 填充相切圆337
10.8 皇后问题图解338
10.8.1 高斯八皇后问题的求解338
10.8.2 m个皇后控制n×n棋盘343
10.9 小孔流水演示348
附录A C语言语法提要351
附录B C常用库函数354
附录C VFP语法提要357
附录D VFP常用函数360
参考文献364