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 即可（为何自己思考）。
【1程序员的数学[上]】4.数学归纳法在编码中也有很大的用处，特别是在循环语句那里，我们需要使循环达到目的，并且能在合适的地方停止。