本文为《程序员的数学》读书笔记。
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，余06/2=3，余03/2=1，余11/2=0，余1余数逆向排列：1100
又比方99
99/2=49，余149/2=24，余124/2=12，余012/2=6，余06/2=3，余03/2=1，余11/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.右端是王牌
同上，483.两端是王牌
两端的抉择，两张王牌的置换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种。本文简略的探讨了计数法、余数、数学归纳法和排列组合的相干常识，下一篇会来探讨一个乏味的货色：递归，敬请期待。