一、0的故事 

——无即是有

1、例子

按位计数法：无论是二进制还是十进制，一个数字的每一位代表有几个该位基位值。例如二进制1100

指数法则：对于10^n, n每减一就变成原来的十分之一。这种定义是一种思维方式的运用：以简化规则为目标去定义值。

2、总结0的作用

占位：例如2503中的0，代表这个数字没有十位，0的占位使得高位数字不会错位。

统一标准，简化规则：

生活中的占位应用：如没有计划的计划，某一天没有安排则视为空计划即0，作为计划的一种占位，这样就方便搜索查找。又如没有药效的药，一种药每4天停用一次则可制作假胶囊直接每天服药即可：

问题分解法：数越大越难处理，将大问题分解为小单元。

二、逻辑

——真与假的二元世界

1、基本逻辑表达式

逻辑的基本思路：兼顾完整性和排他性，即无遗漏无重复。要注意边界处。

分析工具：真值表、文氏图、卡诺图

异或的否定即为相等。常用逻辑表达式：

2、德摩根律

对偶性：

3、借助逻辑表达式思考简化问题

例：

第一步：定义基本命题

第二步：根据规则改写命题为逻辑表达式

第三步：用卡诺图化简表达式

4、包含未定义的三值逻辑表达式

即逻辑表达式有true、false、undefined三种可能的取值。

三、余数

——周期性和分组

1、星期数计算

余数就是分组的一种方法，面对难以计算的大数字时，发现它的循环或规律就易于解决。

找规律从小数一点点看起，发现规律：

易看出按0的个数来看每6个循环一次，可以容易地算出10^n的一天星期几。发现没有星期日，说明10^n无法除尽7。按0的个数思考问题是将大数化小的对数化方法。

2、乘方的思考

找出1234567^987654321的个位数。

先通过试算找规律，能影响两个数乘方结果的个位数的只有这两个数的个位数。即只需要找出7的乘方的个位数规律即可。

发现个位数是1、7、3、9的循环，故将987654321 / 4得到余数1，答案7

总结：涉及难以直接计算的大数字时，先用小数试算找到规律，然后用余数将大数化小解决。

3、黑白棋通信——奇偶校验

随机排列7个黑白棋，后加一枚。观众选择翻转某颗棋或不都翻，问观众的选择。

只要事先设定8个棋子如黑棋为总为偶数个，可能情况为：

故最终可以确定是否翻转过棋子。这就是奇偶校验的应用。徒弟是发送方，魔术师是接收方，观众的翻转就是噪音，发送方多放的一枚棋子为奇偶校验位。接收方通过检查奇偶性判断是否发生通信错误。事实上奇偶校验将数字分为两个集合，7枚棋子128种可能，其中一半黑棋为偶数，另一半为奇数，徒弟添加的棋子起到了标识属于哪组的作用。

4、找人

12个月前人在G村，后随机移动12次，问最后在A处的概率。

从较小的的数入手，不要按路线思考，按目的地分类

发现奇数次移动，人在A、C、F、H，偶数次在B、D、E、G，故12个月后不可能在A处。解答过程将8个村分为奇偶两组，奇数村移动一次到偶数，偶数一次回奇数，每次可知人在奇数村还是偶数村。

5、铺设草席

草席不能分两半，问这个房间能否由草席铺满。

首先，若房间格子为奇数则肯定不能铺满。共62个，需进一步分析。整个房间左上角和右下角各缺一块造成不规整，既然是偶数，若草席可以分半则可铺满。故不能铺满的可能是作为整体的草席要么超边界，要么缺的两块不在一起。故考虑涂色分组：

一张草席半黑半白，故两色应该数量相等，所以不能铺满。

要进行有效的奇偶校验必须找到合适的分类方法

6、一笔画证明

哥尼斯堡七桥问题简化为下图，证明小写字母代表的桥不能一次走遍。

反复实验中发现：要通过一点，这点必须至少有“入”、“出”两条边，每过此点一次则减少两条边。随意取起点出发，则起点度数减1，途经点度减2，不管经过几次度数奇偶性不变，终点度减1。假设这个过程完成了一笔画，有以下两种情况：

1、起点也是终点。画成意味着边走边减的结果使所有顶点度数为0（偶），途经点减的过程中奇偶性不变，故为偶点。起终点为同一点，故同一点度数减2变为0，也是偶点。结论：在起点终点相同的一笔画中，图中的顶点都是偶点。

2、起点不是终点。同理可知途经点为偶点，只有起点和终点为奇点。

总结为命题：可以一笔画成——图中所有点为偶点或有2个奇点。反之也成立。

根据命题说明七桥不能一笔画成。解答过程的思考方法是：观察顶点边数时着眼点不在数本身，而在奇偶性。想详细研究事物时往往陷入“想正确把握所有细节”的思维，较之正确的把握有时准确的分类更有效，发现了周期性和奇偶性就能将大问题转化为小问题解决。

四、数学归纳法

——如何征服无穷数列

1、高斯求和

用变量n，将1—100归纳为1—n得出公式：

用数学归纳法证明公式正确性。数学归纳法步骤为：

这种思路类似推到多米诺骨牌，只需2个步骤无论牌多长都会倒：确保第一块牌倒下；确保第k块牌倒下能使k+1块倒下。

2、奇数求和

3、错误实例：黑白棋

证明投掷的黑白棋颜色一定相同。n = 1显然成立，假设n = k时成立, n = k + 1时有：

证明错误之处：当k = 1时两组没有共同棋子

循环不变式：在编写循环时要找到让每次循环都成立的逻辑表达式，即循环不变式。相当于数学归纳法证明的断言。编写循环一要确保达到目的，二要确保适时停止，循环不变式确保一，循环范围确保二。

五、排列组合

——解决计数问题的方法

1、计数

要不重不漏：认清计数对象的性质即抽象化思考，找出一般规律，将计数对象与整数对应起来。

加法法则：集合中没有重复元素时

容斥原理：两集合的并集数量等于两集合的数量和减两集合交集数量。

乘法原理：两集合元素的组合数量等于集合数量乘积。

2、排列/置换/组合

置换：将n个事物按顺序进行排列。即 n！

排列：n个事物取一部分进行排列。n张牌取k张排列：

组合：n个事物取一部分不考虑顺序排列。

即置换与组合相结合就是排列。置换表示3张牌的交替排列方法，组合表示3张牌的取法，结合就是取出3张牌进行交替排列。

3、实例

药品调剂：A、B、C三种药品每种至少取一粒，一共取100粒，不考虑顺序有多少种方法？

从小规模的同问题思考：隔板法。

扑克牌排列：至少一端是王牌的排法，不区分大小王。

方法一：首先按区分大小王，左端为王牌有2 * 4！，右端同样，两端都是王有2！ * 3！。根据容斥原理有：左 + 右 - 两，最后除以重复度2！。

方法二：所有排列数 - 两端都不是王。5！- 3*2 * 3！，最后除以重复度2！。

六、递归

——自己定义自己

1、汉诺塔

从3个圆盘的情况试，找出规律。发现一般步骤为：

总结为递推公式：

求出解析式：发现H(0)—H(6)为0、1、3、7、15、31、63...发现规律H（n）= 2 ^n - 1，用数学归纳法证明其正确性。

写出程序：

总结思路：先从少量圆盘试移，为了找出一般方法，使用n - 1层汉诺塔来表示 n 层汉诺塔的观点考虑问题：

简单问题比复杂问题易解，遇到难题想办法将问题转换为较为简单的同类问题，即递归的思考方式：在问题中找出递归结构，找出同类简单问题当已知条件用。然后根据递归建立递推公式，能进一步总结出解析式最好。

2、递归和归纳

递归和归纳本质相同，都是将复杂问题简单化，只是方向不同。递归是“从一般性前提推出个别性结论”，归纳是“从个别性前提推出一般性结论”。

菲波那切数列：兔子繁殖问题，不要直接想第n天共有几只：n - 1天前存在的兔子第n天还在；n - 2 天前出生的兔子在第n天繁殖1只。由此得出递归式，再补上基底转为递推公式。

摆砖块、填音符、爬楼梯等多种变形问题实质都是菲波那切数列。

3、杨辉三角

说明组合数可以通过反复计算相邻两数的和得出，比算阶乘要高效。每一点的数是从顶点到此点的路径数

可以根据杨辉三角的规律得出组合数的递归表达：

该式数学理论解释：n中选k的组合数 = n - 1 选 k - 1的组合数 + n - 1 选 k 的组合数。即选不选第n个数为第k个。

找出复杂问题隐含的递归结构：

七、指数爆炸

——如何解决复杂问题

1、指数爆炸的特点

指数爆炸会使问题的规模迅速扩大，运用对数思想解决问题则能快速降低问题规模。例如二分查找每次比较能确定的范围，递归结构为：

相反，可以利用指数爆炸的思想设计密码，密码每设多一位可能的密码多一倍。

2、如何处理指数爆炸

1、理解问题空间的大小。任何问题只要具备：判断是否已成功破解的方法；按顺序试解的步骤，就可以用暴力破解法。

2、处理的4种方法

极力求解：增强计算机性能

变相求解：转换成简单问题求解，寻找更好的算法

近似求解：不求完全解答，用估算或模拟器求解，有助于实际应用

概率求解：求解时使用随机数，可能在短时间解决，也可能找不到答案

八、不可解问题

——不可解的数，无法编写的程序

1、反证法

矛盾就是命题P和其否定形式都成立。

例：证明质数是无穷的。

首先假设质数有限，其集合为2、3、5、7...P，将这所有质数相乘后+1得到Q。Q显然比所有质数都大，由假设知Q不是质数。但任何质数都不能整除Q，由定义知Q是质数，故矛盾。所以质数是无穷的。

2、可数

元素可按一定规律不重不漏地数出来，即与正整数一一对应，可一一列出（可以无限）。可数集合的例子：有限集合，0以上的偶数集合，整数、有理数集合，程序集合等

3、对角论证法——不可数集合

无论怎样都会漏元素的集合，例如整数数列集合等，证明可用对角论证法。

如此得出的数列a1、a2...是整数数列，但不包含在这个“所有整数数列表”中。因为它与“所有整数数列表”中任一整数数列相比至少有一处不同。与“所有整数数列表”矛盾，因此不可数。此外，所有实数集合、函数集合都不可数。

4、不可解问题

不包含在“程序可解决问题集合”中的问题。

停机问题：某程序在给定数据下，是否会在有限时间内结束运行。

九、总结

何为解决问题：认清模式，进行抽象化。从小问题着手，找到一般规律。