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

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四张的话就是4321=24种排法，更多的数量也是类似，这种相乘很有规律，逐渐递减，这种称为阶乘，用!表示，比如321表示为3!，4321表示为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，但是取出的三个元素有321=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种。

本文简单的探讨了计数法、余数、数学归纳法和排列组合的相关知识，下一篇会来讨论一个有趣的东西：递归，敬请期待。