• 第一章 0 的故事
• 第二章 逻辑
• 第三章 余数
• 第四章 数学归纳法
• 第五章 排列组合
• 第六章 递归
• 第七章 指数爆炸
• 第八章 不可解问题
• 第九章

本书的主要内容是介绍事务规律的数学模型有哪些，事务规律的查找和数学归纳密切相关，先将大问题缩小为较好解决的小问题，逐渐增加数量，归纳出规律的数学公式，再套入实际要解决的问题。

第一章 0 的故事

• 进制：
  • 按位计数法。即每逢多少，将上一位进一。
  • 计算机为什么要用二进制，与电子电路的高低电平有关，初始只能表示两种状态，高电平 1，低电平 0。
  • 进制转换：10进制 转 n 进制：

    function decimal2Any (num, n) {
      // 前略
      let temp = ''
      let q = num
      while (q > 0) {
        temp =  q % n + temp
        q = parseInt(q / n)
      }
      return parseInt(temp)
    }
    

• 非按位计数法 —— 罗马数字:
  • 具体表现为用最少的数字做加减表示结果，大数字左侧写小数字表示减法。
  • 以十进制数字示例，罗马数字只有 1000、500、100、50、10、5、1 这几种“数字”。
  • 即 2018 表示为 1000 1000 10 5 1 1 1，1992 表示为 1000 100 1000 10 100 5 1 1 1
• 0 的意义：
  • n^0 = 1 ? 指数法则

    n^3 * n^0 = n^(3+0) = n^3
    n^0 = 1
    

  • 占位
• 思考：
  • 简化：1000 1000 1000 => 3000 => 10^3

第二章 逻辑

• 完整性和排他性
  • 完整性（覆盖）
  • 排他性（非重）
• 与或非

  • 我们不用逻辑符号，而使用 js 逻辑运算符表示逻辑关系为：与（并且） -> &&、或（合并） ->

    、非 -> !

  • 与或非逻辑有真值表和文氏图等多种表示方式
    • 文氏图以图面积的形式表示
      • 或：两者的占有范围
      • 与：两者共同占有的范围
      • 非：非当前值占有的范围
    • 真值表：true 和 false 逻辑运算结果
  • 摩根定律：逻辑判断转换

    // 更形象的表示方式
    // 以变量头顶的 —— 表示非
    // 展开（合并）相邻的非，对换两部分间的与或，结果全等
    // ______     _  _
    // A && B === A||B
    
    !(x >= 0 && y >= 0)
    
    !(x >= 0)) || !(y >= 0)
    
    x<0 || y <0
    

  • 卡诺图，表达式化简，4 变量的卡诺图如图，0 表示非，1 表示是，方块内的值是 ABCD 按位结果二进制值的十进制表示

    CD AB	00	01	11	10
    00	0	1	3	2
    01	4	5	7	6
    11	12	13	15	14
    10	8	9	11	10

    我们将

    • !A && !B && !C && !D：0000
    • !B && C：**01
    • !A && B：01**
    • A && !B && !C && !D：1000
    • A && B && D：11*1 填入卡诺图，得

    CD AB	00	01	11	10
    00	✅	1	✅	✅
    01	✅	✅	✅	✅
    11	12	✅	✅	14
    10	✅	9	✅	✅

    我们用线将相邻的填入区域围起来，同时满足：

    1. 区域内的方块必须是 2^n
    2. 使用最少的区域

    得简化逻辑：

    • !B && !D
    • B && D
    • !A && B
    • C && D

第三章 余数

余数的运用，周期性规律

第四章 数学归纳法

规律数学模型的证明方式

• 基底成立：迈出第一步 Q(1) 成立
• 归纳证明：由 Q(k) 成立可推出 Q(k+1) 成立
• 图可以简化归纳过程，但是图可能会导致错误的归纳
• Q(k) 推导 Q(k+1) 部分会经常出现在编程循环或递归的循环或递归体部分。如进制转换代码的 temp = q % n + temp

第五章 排列组合

组成的规律，排列组合的公式是可由数学归纳法得来。

几个法则：

• 拆解问题后，使用与或非（文氏图）逻辑拼装结果，在这个过程中要考虑重复（与的多次计算）部分和遗漏部分（起点和终点的遗漏）

排列组合的几个概念：

• 阶乘：小于及等于该数的正整数的积

  n * n -1 * n-2 * … * 1 => n!
  

• 排列：考虑结果中元素顺序，n 中取 k 则结果为 n * n-1 * … * n(n-k+1)，更直观的描述是从 n 开始 k 个递减数的乘积
  • n === k 时，称为全排列，结果为 n的阶乘
• 组合：不考虑结果中元素顺序，n 中取 k 则结果为，n 中取 k 的排列数除以 k 的全排列数，k 的全排列即为顺序引起的重复度

第六章 递归

逻辑结构重复的规律，即 n + k 时是否重复了 n 时的逻辑。

递归结构的查找方式：

• 从整体问题中隐去部分问题
• 判断剩余部分是否和整体问题是同类问题

运用：

• 排序算法的递归实现，再小的数组的排序也是数组排序

问题：

• 注意进入递归的条件（递归条件）和退出递归的条件（基线条件）
• 注意递归层级或使用尾递归优化，防止爆栈。
  • 尾递归：递归函数的最后一步是对自身的调用，且调用不参与其他运算，如：

    return 1 + fn(n-1) ❌
    return fn(1, n-1) ✅
    

第七章 指数爆炸

指数爆炸问题的体现有纸对折、棋盘摆放大米等。

结果指数型变化的问题 f(n) = k^n

• 反向应用：当 k 为分数时，我们可以随着 n 的增大而大幅减少结果数量
  • 二分查找：每层待查找数量为 f(n) = 1/(2^n)
• 正向应用：密码，知道可以破解但是却无法在有限时间内破解
• 处理方式：有时我们获得一个指数爆炸问题的解，如旅行商问题
  • 暴力求解：依赖计算机计算能力，超算、量子计算机
  • 查找规律，大多指数爆炸问题需要列出所有可能结果，很难查找规律
  • 近似求解：如贪婪算法，只计算局部的最优解，如旅行商问题中，只选择距离当前节点最近的节点而不考虑后续影响
  • 概率求解：掷骰子

第八章 不可解问题

数学归纳法只能解决可数无穷

• 反证法
• 不可数集合：
  • 可数是指元素可按照一定规律即无 “遗漏” 也无 “重复” 地数出来
  • 无穷集合可将其元素和其他无穷集合中元素一一对应达到可数，如对应集合 1 以上的整数
  • 不可数集合的不可数证明：对角论证法，即列出“所有”集合，然后对每个集合取出索引不重复的一项，稍作改变，就可得到一个不存在于“所有”中的新的集合（因为其与“所有”中的集合至少有一项不同），得证不可数
• 不可解问题：可能性不可数

第九章

幻想法则：问题的转换

1. 将问题从“现实世界”带到“幻想世界”
2. 然后在“幻想世界”解决问题
3. 最后，将答案带回“现实世界”

编程不也是将现实问题带入计算机世界，得出结果后再展示到现实世界吗。