递归与分治策略（3）
有几天没写东西了，下面开始进入分治算法
能使用分治算法解决的问题一般具有如下几个方面的特征：
1.该问题缩小到一定的程度就能很容易的解决
2.该问题可以划分成与原问题具有相同类型的子问题
3.利用子问题得出的解可以合并成原问题的解
4.所划分的子问题之间是相互独立的，涉及包含公共子问题的问题，
通常使用动态规划算法，后续将给出。
基本框架：
Divide_and_conquer(P){ if(|P|<=n0 adhoc(P) Divide P into smaller subinstances P1,P2,...Pk; for(i=1;i<=k;i++) { yi=Divide_and_conquer(Pi); return merger(y1,y2,....yk); }}
【问题 1】二分搜索技术
描述：给定已按升序排好的n个元素a[0:n-1]，现要在这n个元素中找
一个给定的元素x。
分析：很显然此问题分解出的子问题间是相互独立的，即在a[i]前面或
后面查找元素x是独立的子问题，仔细分析，可以看出该问题
满足分治法的条件。
实现：据此很容易就设计出二分搜素算法
时间复杂度分析：
每次执行一次while循环，待搜索数组的大小减少一半，
在最坏的情况下循环执行的次数为O（logn），循环体内
运行时间为O（1），因此整个时间复杂度为O（logn）。
【问题 2】大整数的乘法运算
描述：设X，Y是两个n位二进制数，求XY。
分析：若两个1位数相乘或相加看作1步运算，按传统乘法需要O（n2）次运算。
将每个n（n=2的k次方）位的二进制整数分为2段，每段的长为n/2位
X=A*2(n/2)+B
Y=C*2(n/2)+D
XY=（A*2(n/2)+B）C*2(n/2)+D=AC2(n/2)+(AD+CB)2(n/2)+BD
计算XY需4次n/2位整数的乘法，3次不超过2*n位的整数加法，两次移位
XY满足
T(1)=O(1)
T(n)=4*T(n/2)+O(n)
得T(n)=O(n2)
依然没有得到改进。
改进：XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD
计算XY需要3次n/2位整数的乘法，6次加法，减法和2次移位
计算T(n)
T(1)=O(1)
T(n)=3*T(n/2)+O(n)
解得T(n)=O(n的log3次方)
实现（伪代码）
int main(){ Hanoi(6,'A','B','C'); return 0;}int Multi(X,Y,n){ s=Sign(X)*Sign(Y);//取符号 X=Abs(X);//求绝对值 Y=Abs(Y); if n=1 if(X=1) and (Y=1) return s; else return 0; else A=X的左边n/2位； B=X的右边n/2位； C=Y的左边n/2位； D=Y的右边的n/2位； m1=Multi(A,C,n/2); m2=Multi(A-B,D-C,n/2); m3=Multi(B,D,n/2); s=s*(m1<<n+(m1+m2+m3)<<n/2+m3); return s;}