为了写好程序，要努力学习数学，从基础学起~
第1章 0的故事
十进制逢十进一，二进制逢二进一
将十进制转化为二进制
12/2 = 6..0
6/2 = 3..0
3.2 = 1..1
1/2 = 0..1
所以十进制的12等于二进制的1100
235/2 = 117..1
117/2 = 58..1
58/2 = 29..0
29/2 = 14..1
14/2 = 7..0
7/2 = 3..1
3/2 = 1..1
1/2 = 0..1
计算机采用二进制的原因是，二进制的加法表更简单，容易用计算机实现。
按位计数法如二进制，十进制，八进制等，不按位计数法如罗马数字等。
10的1次方是10的2次方的十分之一，等于10；
10的0次方是10的1次方的十分之一，等于1；
10的-1次方是10的0次方的十分之一，等于1/10。
0的作用：占位符，统一标准，简化规则
日常生活中用0表示没有可以起到简化规则的作用。
第2章 逻辑
逻辑是消除歧义的工具，计算机正确的执行逻辑判断来解决人类的问题。
能够判断对错的陈述句叫做命题，命题正确时为真命题，命题错误时为假命题。命题要么为真，要么为假，同时满足true和false的不能称之为命题。既不为true也不为false的也不能称之为命题。
处理逻辑问题时，需要保证不能有遗漏，不能有重复，小心边界值，兼顾完整性和排他性。
非 ^A (!)
A为true时，A为false
A为false时，A为true
双重否定等于肯定。
与 A ^ B (&& and)
A和B同时为true时，A ^ B才为true
或 A V B (|| or)
A和B有一个为true，A V B就是true
异或 A (+) B
A和B不相等时，A (+) B才为true。
相等 A = B (可以理解为同或)
A和B相等时，A = B为true。
蕴含 A => B
A为true时，仅当B为true时，A => B才为true。
A为false时，A => B恒为true。
逆否命题
若A => B 等于 (B) => (A)
德摩根定律
(A) V (B) => ^(A V B)
(A) ^ (B) => ^(A ^ B)
可以用文氏图来描述命题的真假，用卡诺图来简化复杂逻辑表达式。
第3章 余数
余数就是做除法运算时剩下的数。
今天是星期天，那么100天后是星期几？
今天是星期天，7天后还是星期天，14天后还是星期天，…，98天后还是星期天，所以100天后是星期二。
1234567的987654321次方的个位数是几？
7的0次方的个位 = 1
7的1次方的个位= 7
7的2次方的个位 = 9
7的3次方的个位 = 3
7的4次方的个位 = 1
7的5次方的个位 = 7
。。。
个位在1 7 9 3 之间循环
987654321 % 4 = 1
所以答案为7
运用余数，大数字的问题就可以转化为小数字的问题。
一笔画问题
可以一笔画成 => 所有的顶点都是偶点，或者有2个奇点。
第4章 数学归纳法
n * 2为偶数
n * 2 -1 为奇数
0到n的整数之和为(n*(n+1))/2
数学归纳法步骤
步骤1： 证明p(0)成立
步骤2：证明无论k为0以上的哪个整数，若p(k)成立，则p(k+1)成立
第5章 排列组合
计数需要注意重复和遗漏。
加法法则只在集合中没有重复元素的条件下成立。
乘法法则，将集合A中的所有元素与集合B的所有元素组合起来，组合的总数就是两个集合的元素数相乘。
置换，将n个事物按顺序进行排列称之为置换。
排列 permutation
P(n,k) = n(n-1)(n-2)…(n-k+1)
或者
P(n,k) = (n!)/(n-k)!
组合 combination
C(n,k) = P(n,k)/P(k,k)
C(n,k) = (n!)/((n-k)! * k!)
C(n,k) = C(k-1, n-1) + C(k, n-1)
置换、排列、组合的关系
置换表示3张牌的交替排列方法
组合表示3张牌的取法
排列表示取出3张牌，进行交替排列
3张的置换 * 从5张中取3张的组合 = 从5张中取3张的排列
第6章 递归
GNU是什么意思？
‘GNU is Not UNIX的缩写’。
汉诺塔问题
将n个圆盘，从x柱，经由z柱，转移到y柱的步骤：
当n=0时，什么也不做
当n>0时，
首先，将n-1个圆盘从x柱，经由y柱，转移到z柱(解出n-1层汉诺塔)
然后，将1个圆盘从x柱转移到y柱
最后，将n-1个圆盘从z柱，经由x柱，转移到y柱
H(n) = 2的n次方 - 1
递归和归纳都是将复杂问题简单化，递归(recursive)是从一般性前提推出个别性结论，而归纳(inductive)是从个别性前提推出一般性结论。
第7章 指数爆炸
二分法查找，n次就可以从2的n-1次方减1中找到目标数据
10次可以从2047个目标中查找到目标数据
20次可以从2097151个目标中查找到到目标是数据
30次可以从2147483647个目标中查找到目标数据
求数字10000中0的个数4，就称作求10000的对数。
处理涉及指数爆炸问题的4中方法：
极力求解，转换成简单问题求解，近似求解，概率求解
第8章 不可解问题
反证法：
1. 首先，假设命题的否定形式成立
2. 根据假设进行论证，推导出矛盾的结果。
即 ‘先假设命题的否定形式成立，然后再进行推理，引出矛盾’的论证方法。
集合的元素是有限的，或者集合中的所有元素都与正整数一一对应时，这个集合就被定义为可数(countable)。
可数的意思是’元素可按一定规律既无遗漏，也无重复地数出来’。
有限集合是可数的。
0以上的所有偶数的集合是可数的。
所有整数的集合是可数的。
所有有理数的集合是可数的。
所有整数数列的集合是不可数的。
所有实数的集合是不可数的。
所有函数的集合也是不可数的。
不可解问题：
原则上不能用程序来解决的问题。
停机问题：
判断’某程序在给定的数据下，是否会在有限时间内结束运行’的问题。
via My Octopress Blog by at January 06, 2013 at 10:22PM -> http://lyuehh.github.com/blog/2013/01/06/reading-notes-math-for-programmers/
没有评论:
发表评论