0%

《程序员的数学》读书笔记

简介

本书讲的的是一些程序员必须了解的数学知识,有些知识点挺有意义的,特别是对于非科班出身的程序员来说。
就我的观点来说,一般的程序员需要的数学水平大概是高中就够了,当然要做算法研究大学数学专业水平也不一定够。
下文记录本书一些有用知识点,包括一些算法的数学思路,还有有趣的逻辑问题。

笔记

对于一个问题的分析要注意每种情况的排他性和全体的完整性,也就是不能遗漏也不能重复。

逻辑蕴含(A => B): 若(存在)A,则(判断)B。A为真,整个式子的值由B决定,A为假,整个式子为真。A => B¬A ∨ B 等价。

逆否命题的真值等价与原命题。

摩根定律: (¬A) ∨ (¬B) = ¬(A ∧ B)

余数问题一般存在周期。比如今天是周日,问第10∧2,10∧3,10∧4 … 10**n天是星期几。只要将天数对7取余数,就可得知,余数为3、2、6、4、5、1不断循环。

奇偶校验:就是判断奇数和偶数的个数是否符合一点的比例,比如相等。奇偶校验可以用于解决,草席是否能铺满房间的问题,信息传输过程中的完整性校验。

一笔画问题:其实用到了‘图’的数据结构,有n个点用线段互相连接,一个点有几根线连着,‘度’就为几。一笔画问题,如果终点和起点相同,则每个点的度都应该为偶数;如果终点和起点不同,则除起点和终点之外,每个点的度都应该为偶数;

排列组合中,不区分某些元素,即是除以这些元素的全排列。排列组合应该以有独一性的作为基准。

斐波那契数列: 今天的总数 = 昨天的所有 + 今天生的 = 昨天的所有 + 前天的所有。 鹦鹉螺内壁、葵花种子的摆法、植物叶子的长法、爬楼梯问题都可简化为斐波那契数列。

摆砖头问题: 由于每个砖头没有区别,所以它在哪个位置没有影响。

组合问题: n 取 k = (n-1) 取 (k-1) + (n-1) 取 (k)。即是组合中不包含新元素、组合中包含新元素两种情况。

发现递归结构的要领:

  • 从n层中隐去部分问题。
  • 判断剩余部分是否是n-1层的问题。

不可解问题是原则上不能用程序解决的问题。