本文为《程序员的数学》读书笔记。

0

计数简略来说就是数数，计数法就是数数的办法，谨严一点来说就是拿一种货色和要数的货色一一对应，只有不漏掉和不反复，那么数量就是精确的。

在咱们很小的时候，个别都是拿手指头来数数，从 1 数到 10，而后就懵了，聪慧一点的还会加上脚指头，还不够怎么办呢，这也是困扰咱们先人的问题，手指头不够用，能够用其余比拟多的货色，比方石头，石头总比手指头多，然而再多的话石头也不够用了怎么办。

于是平凡的十进制就被创造进去了，咱们每天都在应用的数字 1,2,3,999,10000 等等其实都是十进制计数法，不过个别不这么叫，当和二进制、八进制等放在一起才这么说。

十进制就是逢 10 进 1，每计满 10 个数就向高位进 1，应用 0 到 9 十个数字，从右往左别离示意个位、十位、百位、千位 …… 各个地位上的数字代表有多少个该数位的值，整体示意的数就是把各个数位的值乘这个数位的数量，最初累加起来，比方 2503 代表的是 2 个 1000、5 个 100、0 个 10、3 个 1 累加的后果，即 2503=21000+5100+010+31，1000、100、10、1 又别离能够应用 10^3（10 的 3 次方）、10^2、10^1、10^0 来示意，所以十进制计数法的数位都是 10^n 的模式，n 从右往左别离为 0、1、2、3、4…..，10 称作十进制计数法的基数或底，n 称作指数。

了解了十进制计数法，二进制计数法也很简略，计算机应用的就是二进制计数法，计算机为什么应用二进制，是因为 2 进制计数法数字品种少，计算机构造能更简略，示意起来比拟容易，比方电路的断开电平的高下等等。二进制只应用 0 和 1 两种数字，从右往左别离示意 1 位、2 位、4 位、8 位 …… 比方 1100，代表 1 个 8、1 个 4、0 个 2、0 个 1 累加的后果，加起来就是对应的十进制数 12，数位 8、4、2、1 别离能够应用 2^3、2^2、2^1、2^0 来示意，则二进制计数法的数位都是 2^n 模式，n 从右往左别离为 0、1、2、3、4….。

以上两种计数法也称作按位计数法，此外，罕用的还有 8 进制、16 进制。8 进制应用 0 - 7 八个数字，从右往左数位别离是 8^0、8^1…。16 进制比拟特地，因为数字只有 0 - 9 不够 16 个，怎么办，补字母：A、B、C、D、E、F，A 代表 10、B 代表 11…..F 代表 16，从右往左数位别离是 16^0、16^1…，平时应用的色彩值 #FFFFFF、#F5F5F5 等就是十六进制。

不同的计数法之间是能够相互转换的，二进制转十进制后面曾经说了，十进制转二进制就是把十进制数字不停的除以 2，察看每次除完的余数是 1 还是 0，而后把剩下的持续除以 2，最初把余数逆向排列就是对应的二进制，说起来比拟形象，看例子：

比方 12

12/2=6，余 0
6/2=3，余 0
3/2=1，余 1
1/2=0，余 1

余数逆向排列：1100

又比方 99

99/2=49，余 1
49/2=24，余 1
24/2=12，余 0
12/2=6，余 0
6/2=3，余 0
3/2=1，余 1
1/2=0，余 1

余数逆向排列：1100011

是不是很简略。

后面数位的示意都是通过指数的模式，指数个别状况还是比拟容易了解的，比方 10^2 就是两个 10 相乘，10^3 就是三个 10 相乘，那么 10^0 呢，0 个 10 相乘，那不应该是 0 吗，但实际上是 1，所以须要换种形式来了解，当你不晓得的状况下能够先写一些进去，而后，找法则，能够先疏忽 0 的状况。

10^3=1000、10^2=100、10^1=10、10^0=?
5^3=125、5^2=25、5^1=5、5^0=?
2^3=8、2^2=4、2^1=2、2^0=?

有没有找出法则，其实就是 k^n，当 n 每减 1，数值就变成原来的 k 分之一，所以 10^0 就是 10^1 的十分之一，也就是 1，5^0 是 5^1 的五分之一，也就是 1，2^0 是 2^1 的二分之一，也是 1，所以 k^0=1。

这样就很好了解 k^-n，比方 10^- 1 就是 10^0 的十分之一，也就是 1 /10，10^- 1 是 10^- 1 的十分之一，也就是 1 /100。

以前咱们总是去刻意记住比方 10^0 和 2^0 是 1，负次方是几分之一，然而其实咱们应该记住这套规定，这样就能触类旁通。

看到这里你是不是会好奇题目为什么是 0，其实下面这些的根底都是 0，如果没有 0，就不会有按位计数法，0 在其中起的是占位的作用。在指数里 0 的作用是统一标准，简化规定，否则就得非凡解决 1 这个数字，不能应用 10^n 或 2^n 来示意。

余数

余数就是做除法运算后剩下的数，也叫剩数，开个玩笑。余数是很有用的，它能帮忙解决周期性的问题，即便数值很宏大，然而通过余数能够简化问题，将大数值问题转化为小数值问题；余数也用来给事物分组，比方表格中常见的隔行变色性能，通过将 n%2= 0 的行加上色彩，就能够把偶数行和奇数行分成两组。

来看一个经典问题，明天是星期天，那么一百天后是星期几？

100 天数值不大，能够间接通过数数的形式来计算，然而如果 1000、10000 天当前呢、10^100 天当前呢？不要说人数了，电脑数都得死机。

通过余数就能够轻松解决这个问题，一周是 7 天，所以 100 天内能凑满七天的都能够疏忽掉，所以 100%7=2，剩下 2 天，明天是星期天，那么两天后是星期二。

10^100 因为数值太大，电脑计算起来也很费劲，所以无妨也先看看能不能找找法则。

10^0=1           1%7=1         星期一
10^1=10          10%7=3      星期三
10^2=100        100%7=2    星期二
10^3=1000      1000%7=6  星期六
.....

有趣味的本人能够持续写下去，最初会发现随着指数 n 的减少，余数的法则是 1、3、2、6、4、5 这个 6 个数字的循环，n 是从 0 开始到 100，所以总共是 101，所以 101%6=5，第五个对应的数字是 4，所以 10^100 天后是星期四。

数学归纳法

数学归纳法是一种证实无关整数的断言对于 0 以上的所有整数（0、1、2、3…..）是否成立时所应用的办法。

演绎，乍一听如同不太靠谱，但其实是十分谨严的。

数学归纳法的证实步骤和多米诺骨牌有点相似，先确保每一张牌倒了前面的一张都会倒，而后确保能推倒第一张牌，那么整个多米诺骨牌就能全副倒下。

假如要证实一个断言 P(n) 对于 0 以上的所有整数 n 都成立，那么应用数学归纳法的步骤如下：

1. 证实当 n = 0 的时候，P(0) 成立
2. 证实不管 n 为 0 以上的哪个整数，P(n) 成立，则 P(n+1) 也成立

步骤 1 称作基底，步骤 2 称作演绎。通过以上两个步骤，就能够证实该断言成立。

来看一个大家已经都做过的题目：从 1 始终加到 100 的和是多少？

最根底的办法当然是从 1 一路加到 100，然而置信大家都晓得还有一个办法，就是 101*50=5050，意思是首尾相加：1+100=101、2+99=101、3+98=101….. 始终加到 50+51=101，一共有 50 个 101，则和为 5050。

当初假如从 0 加到 n，但还是当做从 1 加到 n，则每一项首尾相加的和是 1 +n，一共有 n / 2 项，和为：(1+n)(n/2)=((1+n)n)/2，这个表达式也称为高斯等式，咱们记为 A(n)，那么当初来应用数学归纳法证实 A(n) 对于 n 为 0 以上的所有整数都成立，步骤如下：

1. 证实 A(0) 成立
2. 证实不管 n 为 0 以上的哪个整数，A(n) 成立，则 A(n+1) 也成立

步骤 1：

 0 代进去，表达式的值为 0，从 0 加到 0 也为 0，成立

步骤 2：

 假如 A(n) 成立：即 0 +1+2+...+n = ((1+n)*n)/ 2 成立

证实 A(n+1) 成立：A(n) 的两边同时加上 n +1：0+1+2+....+n+(n+1) = ((n+1)*n)/2 +(n+1)

将 A(n) 的左边代入该等式的右边：((1+n)*n)/2 +(n+1) =  ((n+1)*n)/2 +(n+1)

左边合并：((1+n)*n)/2 +(n+1) = (n^2+3n+2)/2

右边开展合并：(n^2+3n+2)/2 = (n^2+3n+2)/2

左右两边一样，所以 A(n+1) 也成立

步骤 1 和步骤 2 都成立，所以从 0 加到 n 的和 =((1+n)*n)/ 2 是成立的。

排列组合

置换

将 n 个事物按程序进行排列称为置换。

比方 ABC 三张牌共有多少种排法，取第一张有三种抉择，第二张有两种抉择，第三种只有一种抉择，因为每一次的抉择和其余抉择都是能够不同的，所以总的排法就是把这几次的抉择数量相乘，321=6。

ABCD 四张的话就是 4 321=24 种排法，更多的数量也是相似，这种相乘很有法则，逐步递加，这种称为阶乘，用! 示意，比方 3 2 1 示意为 3!，432 1 示意为 4!。

排列

从 n 个事物里选 m(m<=n) 个事物进去进行置换，就叫排列。

比方从 5 张牌里选 3 张进去进行置换：第一张有 5 种抉择，第二张有四种抉择，第三张有三种抉择，总的排法：543=60 种。

形象一下，从 n 张牌中取出 k 张进行排列：

n*(n-1)*(n-2)*....*(n-k+1)

将上式对立成减的模式：(n-0)*(n-1)*(n-2)*....*(n-(k-1))，从 0 始终乘到 k -1，那么一共就是 k 项相乘，排列总数为记为：

因为这个公式不好写，所以以下都用：Pk(上)n(下) 来示意。上述表达式太长了不好书写，能够改成阶乘的模式示意：

因为

n!=(n-0)*(n-1)*(n-2)*...*(n-(k-1))*(n-k)*...*2*1

(n-k)*...*2*1=(n-k)!

所以

Pk(上)n(下)=n!/((n-k)!)。

组合

从 n 个不同元素中取出 k(k<=n) 个元素，不思考程序的排列办法就是组合。

Ck（上）n（下），计算方法是先计算排列总数：Pk（上）n（下），而后除以反复度。

比方 4 个取 3 个的排列总数：432=24，然而取出的三个元素有 3 21= 6 的排列办法，所以每取三个元素就反复了 6 次，须要除掉这个反复度，24/6= 4 种。这个反复度刚好就是 k 的置换数量，所以：

Ck（上）n（下）=
(从 n 个不同元素中取出 k(k<=n) 个元素的排列总数 )/(k 的置换总数) =
(n!/((n-k)!)) / k! =
n!/((n-k)!k!)

来实际一下：将大王、小王、J、Q、K 五张牌排成一排，求左端或右端至多有一张是王牌的排法有几种，不辨别大小王。

能够分三种状况来看：

1. 左端是王牌的状况

 王牌的抉择 2 种，残余四张牌进行置换，总数计算如下：2*P(4/4)=2*4*3*2*1=48。

2. 右端是王牌

 同上，48

3. 两端是王牌

 两端的抉择，两张王牌的置换 P(2/2)* 残余 3 张牌的置换 P(3/3)=2!*3!=2*1*3*2*1=12。1 和 2 两种状况蕴含了 3 的状况，所以辨别大小王的排法总数 = 1 的总数 + 2 的总数 - 3 的总数，而后计算不辨别大小王的状况，除以王牌的反复度 P(2/2)=2*1=2，最初的总排法为：(48+48-12) / 2 = 42 种。

本文简略的探讨了计数法、余数、数学归纳法和排列组合的相干常识，下一篇会来探讨一个乏味的货色：递归，敬请期待。