程序员的数学

第1章　 　0 的故事
——无即是有
本章学习内容　　 　2
小学一年级的回忆　　 　2
10 进制计数法　　3
什么是10　 　进制计数法　　3
分解2503　　3
2 进制计数法　　4
什么是2　 　进制计数法　　4
分解1100　　5
基数转换　　 　6
计算机中为什么采用2　 　进制计数法　　8
按位计数法　　10
什么是按位计数法　　10
不使用按位计数法的罗马数字　　11
指数法则　　12
10 的0 次方是什么　　12
10-1 是什么　　13
规则的扩展　　14
对20 进行思考　　14
2-1 是什么　　15
0 所起的作用　　16
0 的作用：占位　　16
0 的作用：统一标准，简化规则　　16
日常生活中的0　　17
人类的极限和构造的发现　　18
重温历史进程　　18
为了超越人类的极限　　19
本章小结　　20
第2章　 　逻辑
——真与假的二元世界
本章学习内容　　22
为何逻辑如此重要　　22
逻辑是消除歧义的工具　　22
致对逻辑持否定意见的读者　　23
乘车费用问题——兼顾完整性和排他性　　 　23
车费规则　　23
命题及其真假　　24
有没有“遗漏”　　24
有没有“重复”　　25
画一根数轴辅助思考　　26
注意边界值　　28
兼顾完整性和排他性　　28
使用if　 　语句分解问题　　28
逻辑的基本是两个分支　　29
建立复杂命题　　30
逻辑非——不是A　　30
逻辑与—— A 并且B　　32
逻辑或—— A 或者B　　34
异或—— A 或者B（但不都满足）　　37
相等—— A 和B 等　　39
蕴涵——若A　则　B　　40
囊括所有了吗　　45
德?摩根定律　　46
德?摩根定律是什么　　46
对偶性　　47
卡诺图　　48
二灯游戏　　48
首先借助逻辑表达式进行思考　　49
学习使用卡诺图　　50
三灯游戏　　52
包含未定义的逻辑　　54
带条件的逻辑与（&&）　　55
带条件的逻辑或（||）　　57
三值逻辑中的否定（！）　　58
三值逻辑的德?摩根定律　　58
囊括所有了吗　　59
本章小结　　60
第3　 　章　 　余数
——周期性和分组
本章学习内容　　64
星期数的思考题（1）　　64
思考题(100　天以后是星期几)　　64
思考题答案　　64
运用余数思考　　65
余数的力量——将较大的数字除一次就能分组　　65
星期数的思考题（2）　　66
思考题(10100　 天以后是星期几)　　66
提示：可以直接计算吗　　67
思考题答案　　67
发现规律　　68
直观地把握规律　　68
乘方的思考题　　70
思考题(1234567987654321)　　70
提示：通过试算找出规律　　70
思考题答案　　70
回顾：规律和余数的关系　　71
通过黑白棋通信　　71
思考题　　71
提示　　73
思考题答案　　73
奇偶校验　　73
奇偶校验位将数字分为两个集合　　74
寻找恋人的思考题　　74
思考题(　寻找恋人)　　74
提示：先试算较小的数　　74
思考题答案　　75
回顾　　75
铺设草席的思考题　　77
思考题（在房间里铺设草席）　　77
提示：先计算一下草席数　　77
思考题答案　　78
回顾　　78
一笔画的思考题　　79
思考题（哥尼斯堡七桥问题）　　79
提示：试算一下　　80
提示：考虑简化一下　　81
提示：考虑入口和出口　　82
思考题答案　　82
奇偶校验　　85
本章小结　　86
第4　 　章　 　数学归纳法
——如何征服无穷数列
本章学习内容　　88
高斯求和　　88
思考题（存钱罐里的钱）　　88
思考一下　　89
小高斯的解答　　89
讨论一下小高斯的解答　　89
归纳　　91
数学归纳法——　 　如何征服无穷数列　　91
0　以上的整数的断言　　92
高斯的断言　　93
什么是数学归纳法　　93
试着征服无穷数列　　94
用数学归纳法证明高斯的断言　　95
求出奇数的和　 　——　 　数学归纳法实例　　96
奇数的和　　96
通过数学归纳法证明　　97
图形化说明　　98
黑白棋思考题　 　——　 　错误的数学归纳法　　99
思考题（黑白棋子的颜色）　　99
提示：不要为图所惑　　100
思考题答案　　 　100
编程和数学归纳法　　101
通过循环表示数学归纳法　　101
循环不变式　　 　103
本章小结　　107
第5章　 　排列组合
——解决计数问题的方法
本章学习内容　　110
计数——与整数的对应关系　　110
何谓计数　　110
注意“遗漏”和“重复”　　111
植树问题——不要忘记0　　111
植树问题思考题　　111
加法法则　　115
加法法则　　115
乘法法则　　117
乘法法则　　117
置换　　121
置换　　121
归纳一下　　122
思考题（扑克牌的摆法）　　123
排列　　125
排列　　125
归纳一下　　126
树形图——能够认清本质吗　　128
组合　　130
组合　　130
归纳一下　　131
置换、排列、组合的关系　　132
思考题练习　　 　134
重复组合　　134
也要善于运用逻辑　　136
本章小结　　139
第6章　 　递归
——自己定义自己
本章学习内容　　142
汉诺塔　　142
思考题（汉诺塔）　　142
提示：先从小汉诺塔着手　　143
思考题答案　　 　146
求出解析式　　 　148
解出汉诺塔的程序　　149
找出递归结构　　150
再谈阶乘　　151
阶乘的递归定义　　152
思考题（和的定义）　　153
递归和归纳　　 　153
斐波那契数列　　154
思考题（不断繁殖的动物）　　154
斐波那契数列　　157
帕斯卡三角形　　159
什么是帕斯卡三角形　　159
递归定义组合数　　162
组合的数学理论解释　　163
递归图形　　165
以递归形式画树　　165
实际作图　　166
谢尔平斯基三角形　　167
本章小结　　168
第7章　 　指数爆炸
——如何解决复杂问题
本章学习内容　　172
什么是指数爆炸　　 　172
思考题（折纸问题）　　172
指数爆炸　　175
倍数游戏——指数爆炸引发的难题　　176
程序的设置选项　　176
不能认为是“有限的”就不假思索　　178
二分法查找——利用指数爆炸进行查找　　178
寻找犯人的思考题　　178
提示：先思考人数较少的情况　　179
思考题答案　　 　180
找出递归结构以及递推公式　　181
二分法查找和指数爆炸　　183
对数——掌握指数爆炸的工具　　184
什么是对数　　 　184
对数和乘方的关系　　184
以2　为底的对数　　186
以2　为底的对数练习　　186
对数图表　　187
指数法则和对数　　188
对数和计算尺　　190
密码——利用指数爆炸加密　　193
暴力破解法　　 　193
字长和安全性的关系　　193
如何处理指数爆炸　　195
理解问题空间的大小　　195
四种处理方法　　195
本章小结　　196
第8章　 　不可解问题
——不可解的数、无法编写的程序
本章学习内容　　200
反证法　　200
什么是反证法　　200
质数思考题　　 　202
反证法的注意事项　　203
可数　　203
什么是可数　　 　203
可数集合的例子　　204
有没有不可数的集合　　206
对角论证法　　 　207
所有整数数列的集合是不可数的　　207
所有实数的集合是不可数的　　211
所有函数的集合也是不可数的　　212
不可解问题　　 　213
什么是不可解问题　　213
存在不可解问题　　214
思考题　　 　215
停机问题　　215
停机　　216
处理程序的程序　　217
什么是停机问题　　217
停机问题的证明　　219
写给尚未理解的读者　　222
不可解问题有很多　　223
本章小结　　224
第9章　 　什么是程序员的数学
——总结篇
本章学习内容　　226
何为解决问题　　229
认清模式，进行抽象化　　229
由不擅长催生出的智慧　　229
幻想法则　　230
程序员的数学　　231