chap 2-3 分治算法-综合应用
1. 满二叉树的数量
定义满二叉树：所有节点要么有两个子节点，要么无子节点。设$B_n$表示共$n$节点的不同满二叉树的数量，则：
$$
B_{n+2}=\sum_{i=1}^{n+1}B_{i}B_{n+1-i}
$$
假设根节点固定，则$n+2$个节点的满二叉树数量，取决于根节点的左子树和右子树（都为满二叉树）的组合数量。使用数学归纳法可证，复杂度为$\Omega(2^n)$。我们可以使用额外的空间保存下$B_i$的值，这样可以减少重复计算次数。
定义满二叉树：所有节点要么有两个子节点，要么无子节点。设$B_n$表示共$n$节点的不同满二叉树的数量，则：
$$
B_{n+2}=\sum_{i=1}^{n+1}B_{i}B_{n+1-i}
$$
假设根节点固定，则$n+2$个节点的满二叉树数量，取决于根节点的左子树和右子树（都为满二叉树）的组合数量。使用数学归纳法可证，复杂度为$\Omega(2^n)$。我们可以使用额外的空间保存下$B_i$的值，这样可以减少重复计算次数。
在数字信号处理（Digital Signal Processing）领域中，经常使用到多项式乘法。信号通常是一个关于时间或位置的函数，比如捕获到的人的声音等等。数字信号处理要做的事情一般是，先对信号进行采样（sampling），使之变为离散信号；然后将离散信号输入到一个系统中（滤波器等等），最后得到系统的输出，我们称之为系统的响应（response）。
排序算法经常用到分治策略。在现实中，最常用的排序算法当属快速排序。主要过程：首先进行partition操作，从数组中挑选一个元素作为主元pivot，将小于pivot的元素放置到它的左边，将大于pivot的元素放置到它的右边；然后递归地对pivot左右两边的数组进行partition。
分治算法是算法的重要分支之一，主要思想就是：
虽然分治法的核心结构是递归，但也不一定非得用函数递归来实现；递归法便于分析问题，迭代法可能却更为高效 。
$4^{1536}-9^{4824}$是否能被35整除？
$35=5\times 7$，根据费马小定理：$a^{5-1}\equiv 1 (\mod 5)$，$a^{7-1}\equiv 1(\mod 7)$，由于5和7都是素数，易得：$a^{(5-1)(7-1)}\equiv 1(\mod 35)$，即$a^{24}\equiv 1(\mod 35),1\leq a<35$。因此$4^{1536}-9^{4824}\equiv 4^{24\cdot 64}-9^{24\cdot 201}\equiv 1-1(\mod 35)$，故$4^{1536}-9^{4824}$能被35整除。
数论算法在哈希函数的设计方面也有应用。假设在编写网络服务应用时，我们需要维护一个动态变化的客户的IPv4地址的list，如何快速地查询某个IP呢？一个最快的方法是建立大小为$2^{32}$的array，以IP作为index。虽然很快，但是会非常浪费内存，大多数内存可能都是空的。还有一个方法是使用链表，但是查询速度很慢，与客户个数成正比。使用哈希的方法能使占用内存的大小与客户数量成正比，同时获得较快的查询速度。
数论算法应用最广泛的领域之一就是密码学，密码学也是网络安全的重要研究分支。密码学研究的主要问题可以用以下情境描述：Alice和Bob二人想要进行私密通信，但是Eve想要偷听他们的私密通信。Alice和Bob为了保证私密性，他们决定对消息进行加密和解密（编码和译码）：
上一章提到过两数互质的问题，质数（素数）一直以来都是数论中的重点内容。一个基本问题就是：如何判断一个数是否为素数？最容易想到的方法：将这个数做质因数分解，若因数只有1和它本身，则为素数，但是质因数分解效率很低；另一种方法是，依次判断是否有比它小的数整除它，本质上还是质因数分解。下面要介绍的一种高效的素性测试方法，基于一个重要的定理：
有了模运算，我们可以利用它解决不少关于数字的问题。其中，最为著名的问题当属求解两个数的最大公因数(gcd, greatest common divisor)。最容易想到的方法就是，先对两数分别做质因数分解（factoring），然后将它们相同的质因子相乘得到结果。如：$1035=3^3\cdot 5\cdot 23,759=3\cdot 11\cdot 23,gcd(1035,759)=3\cdot 23=69$。不幸的是：
目前还没有足够高效的分解质因数的算法。
我们知道，计算机处理器进行内置的算术运算时，数字大小都是有限制的（32 bits or 64 bits），这已经可以满足绝大多数计算需求了。但如果不断地对一个数做加法或乘法运算，它将变得非常大，最终将会溢出(overflow)。如何解决这个问题？可以从日常生活中得到启发：日复一日，年复一年… 第二天又是新的24小时，第二年又是新的十二个月…