最近看完了一本很薄的书，关于程序员应该掌握的数学知识，没有枯燥的公式推理和定理证明，只有巧妙和生动的深入浅出的讲解。值得一看。下面是我看这本书时的读书笔记。
程序员的数学
第一章 0的故事——无即是有
1.以简化规则为目标去定义值。
2.0的作用：占位，统一标准简化规则。
3.将大问题分解为“小单元”。
第二章 逻辑——真与假的二元世界
4.逻辑：兼顾完整性和排他性（不遗漏，不重复）。
5.A=>B ，只有A为true并且B为false时，A=>B才为false，若A为false，B为true/false都可以，A=>B 结果都为true。A=>B 等于（非A）V B 。
6.异或的非是相等。
7.德摩根定律-对偶性。
8.卡诺图简化逻辑表达式，它是将所有命题的真假组合以二维表的形式表示的图。1x1，1x2，2x2，1x4，4x4组合框。二灯三灯游戏的卡诺图p50.53。
9.三值逻辑包含真假和未定义的逻辑，带条件的逻辑与＆＆，A为true再看B，A为false结果为false，A为undefined，结果为undefined。
第三章 余数——周期性和分组
10.找到规律，使用余数。
11.利用星期数的周日为7可以推算100天后的星期数，利用1后面的0的个数找出每增加一个0星期数变化的周期为6，即每加6个0星期数又还原的规律（从没有0开始，1天10天100天……，余数为1，3，2，6，4，5的循环）可以推算10^100天后的星期数。
12.乘方1234567^987654321的个位数是多少的问题，影响个位数的只是1234567的个位7，找它的规律，7的0，1，2，3，……次方的个位是1，7，9，3的循环，周期为4，指数除以4余数为0，1，2，3其中之一，分别对应1，7，9，3。
13.运用余数，大数字的问题就能简化为小数字的问题。
14.通过黑白棋通信中魔术师通过检查摆放棋子的奇偶性来判断是否翻转过，在计算机通信中称为奇偶校验。奇偶校验位将数字分为两个集合。
15.要进行有效的奇偶校验，必须找到合适的分类方法，在寻找恋人问题中分为奇数村（奇数次移动到达）和偶数村（偶数次移动到达），铺设草席问题中我们为方格涂上了黑白相间的颜色。我们不需要反复试验，需要的是“灵感”！
16.一笔画问题-哥尼斯堡七桥问题，每经过一个顶点其度数减2，奇点还是奇点，偶点还是偶点，起点和终点相同的一笔画所有顶点都是偶点，起点和终点不同的一笔画只有2个奇点（起点和终点）。欧拉：如果能够一笔画成，必须满足所有顶点都是偶点或者只有2个奇点。
欧拉论断的重点在于：不反复试验也能证明不能一笔画成。不用频繁试走各种路径，只要观察各顶点的度数即可。欧拉的证明中在观察各顶点的边数时，着眼点不在“数的本身”，而在“数的奇偶性”。这又是奇偶校验的一个例子。
17.当我们“想要详细地研究”事物时，往往容易陷入“想正确把握所有细节”的思维，但是像奇偶校验那般，较之“正确地把握”，有时“准确地分类”则更为有效。
第四章 数学归纳法-如何征服无穷数列
18.数学归纳法：步骤一：证明“P(0)成立”（基底），步骤二：证明不论k为0以上的哪个整数，“若P(k)成立，则P(k+1)也成立” （归纳）。
19.通过循环表示数学归纳法，在编写循环时，找到让每次循环都成立的逻辑表达式（循环不变式）很重要，它相当于数学归纳法证明的“断言”。循环不变式用于证明程序的正确性。
第五章 排列组合-解决计数问题的方法
20.植树问题-不要忘记0。内存中的数据编号一般从0开始。
21.容斥原理：考虑了重复元素的加法法则，|AUB|=|A|+|B|-|AB|。
22.乘法法则|AXB|=|A|X|B|。
23.置换：将n个事物按顺序进行排列。结果为阶乘n!。
24.排列：从n个事物中取出一部分k个，结果为nx(n-1)x(n-2)x…x(n-k+1)，即n!/(n-k)!。
25.组合：不考虑顺序的计数。结果为n!/(n-k)!/k!。
26.置换x组合=排列。
27.重复组合问题：药品调剂问题：从3种药品*取100粒的方法数，可以将问题转化为隔板划分，用两块隔板将100粒划分为三部分，分别是三种药品，就是从99个间隔中选2个。
第六章 递归-自己定义自己
28.汉诺塔问题：
再根据递归结构建立递推公式。
29.递归和归纳，只是方向不同。“从一般性前提推出个别性结论”的是递归recursive的思想（从后往前），而“从个别性前提推出一般性结论”的是归纳induction的思想（从前往后）。
深刻理解用递归和归纳两种方式使用prove函数证明数学归纳法的过程，对于求解一般性问题帮助很大。
30.斐波那契数列：0,1,1,2,3,5,8,13,21,34,55,89,…
F(n)=F(n-1)+F(n-2)
摆砖头（1x2砖头，摆宽为2的长方形，左边竖立1块，右边与n-1块摆法相同，左边横叠2块，右边与n-2块摆法相同），创作旋律（先打4分音符，剩余部分为n-1拍时的情况数，先打2分音符，剩余部分为n-2拍时的情况数），鹦鹉螺的内壁间隔，葵花种子的排法，植物枝叶的长法，一次走1阶或2阶爬n层阶梯的方法等问题都能看到斐波那契数列的身影。
31.帕斯卡三角形（杨辉三角）每一个位置对应一个组合数。C(n,k) =C(n-1,k-1)+C(n-1,k)，从n张中选出k张的组合分为两种情况，一种是选择特定的牌，从剩下的n-1张中选择k-1张的组合，另一种是不选特定的牌，从剩下的n-1张中选择k张的组合。
32.为了找出复杂问题中隐含的递归结构，一般首先从n层整体问题中隐去部分问题（相当于关注特定牌），其次判断剩余部分是否和整体问题是同类问题（n-1层的问题）。
33.以递归形式画树
第七章 指数爆炸-如何解决复杂问题
34.二分查找就是利用了指数爆炸来对大量的数据信息进行高速查找的算法。利用对数可以将乘法运算转换为加法运算，也是利用了指数爆炸。
35.指数爆炸的问题可解并不代表能在可接受的时间内解决。解决问题之前要先考虑是否属于指数爆炸问题。
第八章 不可解问题-不可解的数、无法编写的程序
36.集合的元素是有限的，或者集合中的所有元素都与正整数一一对应，这个集合就被定义为可数。
37.为了找出不包含在表中的数而选出表中对角线所在的数字的论证法称为对角论证法。
38.编写程序并不能达到比可数无穷更多的无穷。程序无法解决停机问题那种判断任意程序动作的问题。
第一章 0的故事——无即是有
1.以简化规则为目标去定义值。
2.0的作用：占位，统一标准简化规则。
3.将大问题分解为“小单元”。
第二章 逻辑——真与假的二元世界
4.逻辑：兼顾完整性和排他性（不遗漏，不重复）。
5.A=>B ，只有A为true并且B为false时，A=>B才为false，若A为false，B为true/false都可以，A=>B 结果都为true。A=>B 等于（非A）V B 。
6.异或的非是相等。
7.德摩根定律-对偶性。
8.卡诺图简化逻辑表达式，它是将所有命题的真假组合以二维表的形式表示的图。1x1，1x2，2x2，1x4，4x4组合框。二灯三灯游戏的卡诺图p50.53。
9.三值逻辑包含真假和未定义的逻辑，带条件的逻辑与＆＆，A为true再看B，A为false结果为false，A为undefined，结果为undefined。
第三章 余数——周期性和分组
10.找到规律，使用余数。
11.利用星期数的周日为7可以推算100天后的星期数，利用1后面的0的个数找出每增加一个0星期数变化的周期为6，即每加6个0星期数又还原的规律（从没有0开始，1天10天100天……，余数为1，3，2，6，4，5的循环）可以推算10^100天后的星期数。
12.乘方1234567^987654321的个位数是多少的问题，影响个位数的只是1234567的个位7，找它的规律，7的0，1，2，3，……次方的个位是1，7，9，3的循环，周期为4，指数除以4余数为0，1，2，3其中之一，分别对应1，7，9，3。
13.运用余数，大数字的问题就能简化为小数字的问题。
14.通过黑白棋通信中魔术师通过检查摆放棋子的奇偶性来判断是否翻转过，在计算机通信中称为奇偶校验。奇偶校验位将数字分为两个集合。
15.要进行有效的奇偶校验，必须找到合适的分类方法，在寻找恋人问题中分为奇数村（奇数次移动到达）和偶数村（偶数次移动到达），铺设草席问题中我们为方格涂上了黑白相间的颜色。我们不需要反复试验，需要的是“灵感”！
16.一笔画问题-哥尼斯堡七桥问题，每经过一个顶点其度数减2，奇点还是奇点，偶点还是偶点，起点和终点相同的一笔画所有顶点都是偶点，起点和终点不同的一笔画只有2个奇点（起点和终点）。欧拉：如果能够一笔画成，必须满足所有顶点都是偶点或者只有2个奇点。
欧拉论断的重点在于：不反复试验也能证明不能一笔画成。不用频繁试走各种路径，只要观察各顶点的度数即可。欧拉的证明中在观察各顶点的边数时，着眼点不在“数的本身”，而在“数的奇偶性”。这又是奇偶校验的一个例子。
17.当我们“想要详细地研究”事物时，往往容易陷入“想正确把握所有细节”的思维，但是像奇偶校验那般，较之“正确地把握”，有时“准确地分类”则更为有效。
第四章 数学归纳法-如何征服无穷数列
18.数学归纳法：步骤一：证明“P(0)成立”（基底），步骤二：证明不论k为0以上的哪个整数，“若P(k)成立，则P(k+1)也成立” （归纳）。
19.通过循环表示数学归纳法，在编写循环时，找到让每次循环都成立的逻辑表达式（循环不变式）很重要，它相当于数学归纳法证明的“断言”。循环不变式用于证明程序的正确性。
第五章 排列组合-解决计数问题的方法
20.植树问题-不要忘记0。内存中的数据编号一般从0开始。
21.容斥原理：考虑了重复元素的加法法则，|AUB|=|A|+|B|-|AB|。
22.乘法法则|AXB|=|A|X|B|。
23.置换：将n个事物按顺序进行排列。结果为阶乘n!。
24.排列：从n个事物中取出一部分k个，结果为nx(n-1)x(n-2)x…x(n-k+1)，即n!/(n-k)!。
25.组合：不考虑顺序的计数。结果为n!/(n-k)!/k!。
26.置换x组合=排列。
27.重复组合问题：药品调剂问题：从3种药品*取100粒的方法数，可以将问题转化为隔板划分，用两块隔板将100粒划分为三部分，分别是三种药品，就是从99个间隔中选2个。
第六章 递归-自己定义自己
28.汉诺塔问题：
#include<stdio.h>
#include<stdlib.h>
void
hanoi( int n,char x,char y,char z )
{
if( n>0 )
{
hanoi( n-1,x,z,y );
printf( "%c->%c ",x,y );
hanoi( n-1,z,y,x );
}
}
int
main()
{
hanoi(6,'A','B','C');
return EXIT_SUCCESS;
} 递归的思维方式，对于汉诺塔来说，就是将n层汉诺塔问题转换为n-1层汉诺塔问题，即在问题中找出递归结构。虽然暂未解决给定的问题，但是要找到同类的简单问题，并把它当做“已知条件”来运用。
再根据递归结构建立递推公式。
29.递归和归纳，只是方向不同。“从一般性前提推出个别性结论”的是递归recursive的思想（从后往前），而“从个别性前提推出一般性结论”的是归纳induction的思想（从前往后）。
深刻理解用递归和归纳两种方式使用prove函数证明数学归纳法的过程，对于求解一般性问题帮助很大。
30.斐波那契数列：0,1,1,2,3,5,8,13,21,34,55,89,…
F(n)=F(n-1)+F(n-2)
摆砖头（1x2砖头，摆宽为2的长方形，左边竖立1块，右边与n-1块摆法相同，左边横叠2块，右边与n-2块摆法相同），创作旋律（先打4分音符，剩余部分为n-1拍时的情况数，先打2分音符，剩余部分为n-2拍时的情况数），鹦鹉螺的内壁间隔，葵花种子的排法，植物枝叶的长法，一次走1阶或2阶爬n层阶梯的方法等问题都能看到斐波那契数列的身影。
31.帕斯卡三角形（杨辉三角）每一个位置对应一个组合数。C(n,k) =C(n-1,k-1)+C(n-1,k)，从n张中选出k张的组合分为两种情况，一种是选择特定的牌，从剩下的n-1张中选择k-1张的组合，另一种是不选特定的牌，从剩下的n-1张中选择k张的组合。
32.为了找出复杂问题中隐含的递归结构，一般首先从n层整体问题中隐去部分问题（相当于关注特定牌），其次判断剩余部分是否和整体问题是同类问题（n-1层的问题）。
33.以递归形式画树
void draw(int n)
{
if(n==0){}
else{
left();
forward(n);
drawtree(n-1);
back(n);
right();
right();
forward(n);
drawtree(n-1);
back(n);
left();
}
}
第七章 指数爆炸-如何解决复杂问题
34.二分查找就是利用了指数爆炸来对大量的数据信息进行高速查找的算法。利用对数可以将乘法运算转换为加法运算，也是利用了指数爆炸。
35.指数爆炸的问题可解并不代表能在可接受的时间内解决。解决问题之前要先考虑是否属于指数爆炸问题。
第八章 不可解问题-不可解的数、无法编写的程序
36.集合的元素是有限的，或者集合中的所有元素都与正整数一一对应，这个集合就被定义为可数。
37.为了找出不包含在表中的数而选出表中对角线所在的数字的论证法称为对角论证法。
38.编写程序并不能达到比可数无穷更多的无穷。程序无法解决停机问题那种判断任意程序动作的问题。