第二章 算法效率分析基础
2.5 计算斐波那契数列的O(log n)算法：
利用矩阵， 当 n >= 1时， [F(n-1), F(n); F(n), F(n+1)] = [0,1; 1,1]^n
其中的乘方运算使用霍纳法则
第三章 蛮力法
凸包问题：链接任意两点，检查剩余的点是否都在连线的同侧。效率O(n^3)
分配问题：n个任务分配给n个人，其中将第j个任务分配给第i个人的成本为C[i,j]，找出成本最小的分配方案。蛮力法：穷举n!种可能的方案。高效方法：匈牙利方法。
第四章 分治法
主定理：对于 T(n) = a T(n/b) + f(n), f(n)为 a = b^d, T(n) = Θ(n^d * log n)
如果 a > b^d, T(n) = Θ(n ^ (log a/log b))
大整数乘法：a=a1a0, b=b1b0, 其中a和b都是n位整数，低n/2位为a0,b0, 高位为a1,b1
需要三次n/2位的乘法即可完成 c = a*b = c2*10^2n + c1*10^n + c0
其中 c2=a1*b1, c0=a0*b0, c1=(a1+a0)*(b1+b0) - (c2+c0)
T(n) = n^(log3/log2)
最近点对问题：找到平面上n个点中的最近距离。先画一条竖线，将所有的点分成左右两半，找到两部分的最近距离d1,d2, 然后考察竖线附近的点。
凸包问题的快包算法（类似于快速排序）：首先过最左边的点P1和最右边的点Pn，将平面分成上下两部分。然后考察上半个平面：找到距离直线P1Pn距离最远的点Pmax, 那么Pmax一定是凸包的顶点； 三角形P1PmaxPn内部的点一定不是凸包的顶点。然后只需分别考虑两侧的顶点即可。
平均效率 O(n * log n)。由于三角形内部的点无须考虑，甚至可以达到线性效率。
最差情况O(n^2)：剩下的点全都在同一侧。
三角形面积的计算：三角形(x1,y1),(x2,y2),(x3,y3)的面积等于下面这个行列式的值的1/2
[x1,y1,1; x2,y2,1; x3,y3,1] = x1y2 + x2y3 + x3y1 - x3y2 - x2y1 - x1y3
第五章 减治法
插入排序：最差情况需要做(n-1)*n/2次比较，但是平均只需n^2/2次比较，因此胜过选择排序和冒泡排序。
插入排序有一种扩展算法，叫做Shell排序。
拓扑排序：算法1，通过深度优先搜索，将出栈顺序反过来即得到一个解。算法2，先找到一个只有出度没有入度的点，将这个点以及相关的边删除，重复此过程。
生成排列：依次生成从1到n的所有排列。假设已经得到了n-1的所有排列，那么依次取出n-1的每一个排列，将n插入每一个位置。按这样的顺序插入更好：对于取出的第一个(n-1)排列，从右到左插入；第二个排列从左到右插入；第三个再从右到左...
例子：依次生成1到3的所有排列
开始： 1
从右到左将2插入1：12, 21
从右到左将3插入12：123, 132, 312
从左到右将3插入21：321，231，213
依这种次序生成的排列满足最小变化要求：得到的两个相邻的排列的差别仅在于交换两个相邻的位置。
生成排列：生成n的所有排列。可不可以不通过（n-1）排列，而直接生成n的排列，并满足最小变化要求呢？ 通过Jhonson-Trotter算法：
对每个元素赋予一个向左或向右的箭头。如果元素k指向一个相邻的较小的元素，则称k为移动的
#JhonsonTrotter(n)
#初始序列1...n, 所有箭头均向左
#while 存在一个移动元素 k do
# 求最大的移动元素k
# 把k和它指向的元素互换
# 调转所有大于k的元素的方向
# 输出新的排列
此算法和上面的算法生成的顺序是一样的，且都不是按字典序。
生成子集：利用二进制。可否按这个顺序生成二进制串：使得两个相邻的二进制串只相差一个比特位。（也就是在子集里面要么增加了一个元素，要么删除了一个元素）。答案为“是”，通过二进制反射格雷码。
俄式乘法：
原理如下，如果n是偶数，那么 n * m = (n/2) * (2m), 否则 n*m = (n-1)/2 * 2m + m
代码
#对整数a和b相乘
#result = 0
#while(a > 0) {
# if(a % 2 == 1) { result += b; }
# a /= 2;
# b *= 2;
#}
特点：只涉及折半、加倍和相加操作，效率非常高。
约瑟夫问题：
n个人围成一圈，并且从1到n编上号码，从1号开始，每隔一个杀掉一个，问最后剩下几号？
记幸存者的号码为J(n)，那么当n为偶数时，也就是n=2k，J(2k)=2J(k)-1
当n=2k+1时 J(2k+1) = 2J(k)+1
把n表示为二进制形式，并且做一次向左的循环移位，得到结果就是幸存者编号。
比如n=6时，二进制为110，移位后得到101，也就是5号为幸存者。具体推导过程见《具体数学》
插值查找：对有序数组进行查找。
把数组看成是线性递增的，那么便可以直接定位到目标值附近。一般情况下，比折半查找要快。
拈游戏：
两人轮流取走桌面上的棋子，每次取1到m颗，取到最后一颗的获胜。
升级版：桌面上有I堆棋子，棋子数分别为n1,n2,...ni。玩家每次可以从任意一堆棋子中取走任意数量的棋子。取走最后一颗棋子的人获胜。
对于I＝2的情况非常简单。（略）
解法：将n1,n2,...ni表示为二进制的形式，b1,b2...bi，计算它们的二进制数位和，也就是对每一位分别求和并忽略进位。当且仅当二进制数位和中包含至少一个1时，先手获胜。先走的玩家只需保证剩下的棋子二进制数位和只包含0即可。
《Winning Ways for your Mathematical Plays》这本书包含了各种数学游戏的解法。
