程序员的数学(1)[上]

自此开始学习程序员的数学，由于是忙里偷闲学习，进度可能不会那么快。

重要思想：问题分解法，将大问题分解为小问题。

第一章：0的意义

1.进制转换：n进制转换为10进制：从右到左各个位乘以 n i n^i ni(i取值为0~+ ∞ \infty ∞)

10进制转换为n进制：除n取余法，将最后的余数从下往上排列，构成新数。

2.二进制：有两个数字0,1。从右往左基数依次为 2 i 2^i 2i,i从0到无穷。

十进制：有十个数字0~9。从右往左基数依次为 1 0 i 10^i 10i,i从0到无穷。

其他进制类推。

3. 1 0 n 10^n 10n解析：按照平常的理解， 1 0 n 10^n 10n就是n个10相乘。但是对于那些 1 0 0 10^0 100,10 -1…等式子就很难理解其意思

0个10相乘很难理解为等于1，-1个10相乘就更难理解其含义了。

于是我们换一种思路，把10n-1理解为 1 0 n 10^n 10n除以10（ 1 0 n 10^n 10n还理解为n个10相乘，n>1），此时对于 1 0 0 10^0 100,10 -1…就很容易理解其意思。

1 0 0 10^0 100等于10除以10结果为1，10 -1等于1除以10，结果为 1 10 \frac{1}{10} 101​

易知，将10换为其他数字也成立。

公式如下：

10+5 = 1 * 10 * 10 * 10 * 10 * 10

10+4 = 1 * 10 * 10 * 10 * 10

10+3 = 1 * 10 *10 * 10

10+2 = 1 * 10 * 10

10+1 = 1 * 10

100 = 1

10-1 = 1 / 10

10-2 = 1 / 10 / 10

10-3 = 1 / 10 / 10 / 10

10-4 = 1 / 10 / 10 / 10 / 10

10-5 = 1/ 10 / 10 / 10 / 10 / 10

4.数字0的重要性：比如说喝药，需要喝三天停一天，这样时间久了很容易忘记自己今天该不该喝药，所以说增加一种无效药，每隔三粒药放一个无效药。这样药的用法就变成了每日服用一次，简单了许多。

第二章：逻辑（离散数学）

如果你也学过离散数学的话，对这章可能会看的速度特别快，基本上不需要理解什么东西。

1.逻辑即真与假，if语句，可以说任何一个有点作用的程序都离不开if语句，因此逻辑对于编码很重要。

2.命题定义：能判断真假的陈述句。

①陈述句，众所周知是以句号结尾的，看见除句号外的其他符号结尾，肯定不是命题。

②能判断真假，即这句话非真即假，不会有第三种情况出现，对于结果的判断不会重复，也不会有遗漏。

下面介绍或与非：（未说明的情况下都是：a逻辑符号b）

3.非( ¬) ：非的意思就是与你相反，你说往东我就往西。

假如说a为真，则¬a为假，屡试不爽。

4.或( ⋁ \ ⋁ ) : 两者只要有一个为真，则表达式为真。

还有一种叫异或（ ⨁ \ ⨁）: 就是说a，b不能同时满足，只能满足一个，或都不满足。

a ⋁ \ ⋁b,为假的情况只有a，b同时为假。

a ⨁ \ ⨁b , 可以从实际角度考虑，a，b最多只能有一个为真。比如说：a：今天晴天。b：今天雨天。很明显a与b最多只能成立一个，或者都不成立。

5.与 ( ⋀ \ ⋀ ): 两者都为真时，表达式才为真。

a ⋀ \ ⋀b , 只要有一个为假，则表达式为假。

6.相等(=)：数上用的是=，我感觉不严谨，我用 ⇔ \ ⇔表示：即a与b相等。

若a ⇔ \ ⇔b,则仅有当a，b同为真或假时，表达式才为真。

7.蕴含( ⇒ \ ⇒):这个刚开始比较难以理解真假

a ⇒ \ ⇒b(简单解析:)

a当作是老师出的题

b当作是你的答案和标准答案相同

(1).当老师的题出错时，无论你选什么答案都得分。

(2).当老师题出对，你写对时才得分。

(3).仅有当老师题出对，你答案写错时，你才不得分。

(4).所以说：只有当a为真，b为假时，表达式才为假。

8.德摩根定律：

¬ (a ⋁ \ ⋁ b) ⇔ \ ⇔ ¬a ⋀ \ ⋀ ¬b

¬ (a ⋀ \ ⋀ b) ⇔ \ ⇔ ¬a ⋁ \ ⋁ ¬b

9.在离散数学上，不仅仅有德摩根律，还有许多其他的如最基础的交换律，结合律，分配率。还有蕴含等值式，等价等值式…有兴趣的可以私下搜索搜索。

10.对于用符号来表示逻辑很难理解，我们可以用真值表，维恩图来表示。此处仅举一个真值表的例子(真为1，假为0)：（前两列刚好是二进制下的0,1,2,3，不仅仅是巧合哦）

pq¬ p¬ qp ⋁ \ ⋁qp ⋀ \ ⋀qp ⇔ \ ⇔qp ⇒ \ ⇒q

11.自己可以试着证明一下：{¬(a ⨁ \ ⨁b)} = {a ⇔ \ ⇔b}

12.卡诺图：对于某些逻辑表达式很难瞬间看出何时正确，何时错误，用卡诺图可以办到（即总结出规律）

附上教程：卡诺图

13.从程序角度考虑：逻辑表达式不一定为真或假，还有可能报错，此时结果既不是真，也不是假。此时我们新增一种情况： 代表未定义。

所以说我们的逻辑结果变为三个：true，false，。

解析一下与前面写的逻辑运算的区别，此时学过c或者Java的话就很容易理解了：

逻辑与（&&）：

当a为真时，则表达式的值等于b的值

当a为假时，表达式为假，程序不判断b(如果b有改变数值功能的话，数值不会改变)

当a为时，表达式为

逻辑或（||）：

当a为真时，表达式为真，程序不判断b（如果b有改变数值功能的话，数值不会改变）

当a为假时，表达式的值等于b的值

当a为时，表达式的值等于

逻辑非(!):

当a为时，!a也为

德摩根律依然适用，没有变化，仅需要换一下逻辑符号即可。

逻辑语句是万能的，可以囊括一切，听说某种智能音响就是用许多if…else…语句写出来的。

第三章：余数(有意思的题)

这一章基本上没有什么新知识，不过锻炼思维还是很有用的

1.利用余数我们可以计算很多，特别是对于那些位数很大的题，利用好余数往往能事半功倍。

2.今天是周日，求100天后是周几：

(1)傻子求法：第一天周一，第二题周二，第三天周三，第四天…第一百天周二。

(2)随便一个正常人来求解，应该都会想到用余数求解(把想查日历的拖出去乱棍打死…)，因为一周有七天，100除以7得到的余数，稍加思考就能得出那一天是周几。

当我们会用余数之后，莫说一百天，一亿天后是周几也能轻易计算出来，只需除7取余就好。

进阶：10100天后是周几？

如此一来，在除7取余的话，对于计算机来说也是一个不小的难题，一定还有其他循环规律我们没有发现

由图我们发现，随着次方数的增加，余数却是有规律的出现(1,3,2,6,4,5)，我们可以依此为规律，求出10100天后是周几，即100与7求余。

用数形结合来思考这个问题：

我们可以将七天围成一个圆，类似于钟表，有一个指针在那里一圈一圈的转，不会到达尽头。

以此来思考取余求周几的问题能更加容易理解。就是一个简单的循环

在数据结构的栈类型中，我们就是以取余来确定栈顶指针，栈底指针的位置的，依次判断栈是否为空或满

3.（）的个位数的数字是什么？

看到这个题目，就知道我们不能直接计算出结果，一定是找规律的题

静下心思考一下：求个位数的元素…能影响个位数的元素值大小的只有个位上的元素，也就是说无论在十位，百位上进行如何操作…并不能影响个位大小，所以说我们就可以忽略高位，仅考虑个位数字的情况了。

由图可知随着次方数的增加，个位数的取值也是出现了循环。

应为有四种取值情况，所以说计算的时候应用次方数与四取余，余数0,1,2,3依次对应数字1,7,9,3.

#从这两个例子可以看出，利用好余数，求解大数值的问题很容易变成小数值。

4，寻找恋人问题：

有八个村子，你的恋人住在其中一个，每一个月之后就会顺着路去往下一个村子，但是去往哪一个是随机的。假果她这一月在G村，那么下一月就在C，F，H村的某一个。

已知12个月前他住在G村，求现在她在A村的概率。

刚看到这道题，由于求的是概率，所以说就和概率论联系在了一起，脑子里胡思乱想了一通，然后拿出笔在纸上画画，你会发现题目是如此简单

解：

第一次在：G
第二次在：C，F，H
第三次在：B,D,E,G
第四次在：A,C,F,H
第五次在：B,D,E,G
...

规律不是出来了吗？我们又看到了熟悉的循环，而且是仅有两种不同情况的循环，因此我们可以根据求余继续求解题目问题。求余方法自想…

5.哥尼斯堡七桥：(经典的图论问题)

新手接触这个题可能会拿起笔，实验几次，结果当然是无功而返，拥吻这个任务不能完成…

在此我们假设每块陆地为一个顶点，每条路为边，与顶点相连的边的个数叫做度。(此处仅讨论无向图)。

(1)当点的度数都为偶数时，能一笔画成这个图，并且还能回到起点。(反之也成立)

(2)当有两个奇数度时，能一笔化成这个图，但是不能回到起点，并且起点必须是从奇数顶点开始，终点是另一个奇数顶点。(反之也成立)

图论中的欧拉定理有很多，比如说握手定理…，不是这里能介绍完的，我仅仅只是将书上写的介绍一下。

6.铺设草席的思考题：

问：能不能用这个草席把房间铺满，草席不能覆盖，不能剪开？

(1):我们看到草席是两个格子，所以说我们可以先数一下地面有几个格子，如果有奇数个那么肯定不行。

(2):然后我们给地面染上颜色，以黑白区分，这样的话就易知，黑色块和白色的数量应该一样，否则不行。

第四章:数学归纳法

1.以前经常听说高斯(可不是奥特曼)小时候计算1+2+3+…+100求和的故事，经常感慨人家的智商多么的聪明，太强了。

2.计算1+2+3+4+…+100我们现在会的方法都是1+100,2+99,3+98…结果为50个101相加，结果为5050。

我们可以放开想象：100+99+…+3+2+1和上面那个式子的结果一样，但是若两式相加，就变成了100个101相加，在除以2，就是等差数列的和。

1+2+3+4+…+100

100+99+98+97+…+1 两式相加得

101+101+101+…+101

数形结合：

由此我们可以推出等差数列的前n项和公式： ( n + 1 ) ∗ n 2 \frac{(n+1)*n}{2} 2(n+1)∗n​(首项加末项乘项数除2)。

3.数学归纳法：是证明有关整数的断言对于0以上的所有整数(0,1,2,3…)是否成立所用的方法。

步骤1：证明P(0)成立

步骤2:证明不论k为0以上何整数，若P(k)成立，则P(k+1)也成立

和多米诺骨牌有点类似。推翻一排多米诺骨牌需要两个条件：(1)需要外力推到一个(2)倒下一个骨牌后最起码能引发另一个骨牌倒下

举例（我的方法不同于书上）:断言Q(n)对于1以上的所有整数n都成立。

断言Q(n):1+3+5+7+…+(2*n-1) = n 2 n^2 n2

解：易知Q(0)成立。

下面证明步骤2：只需证明 k 2 k^2 k2+[2(k+1)-1] = ( k + 1 ) 2 (k+1)^2 (k+1)2 即可（为何自己思考）。

4.数学归纳法在编码中也有很大的用处，特别是在循环语句那里，我们需要使循环达到目的，并且能在合适的地方停止。