第六天 分治
其实仍然是递归，分治特殊之处在于，它每次将问题分开来求解，并不断如此解析知道问题得到一个直接的子答案。当时读到此处，我便在思考树的遍历，这不就是一种树的遍历么？是的。
分治的优势在于，计算机一次吃不消的东西，他将给与一个合适的方法，大大的减少了程序的复杂度。
下面的程序计算一个数组的最大值。它不能显示出分治的优势所在，抬低门槛方便我们入了门。为了方便大家理解可以将item改成大家习惯的数据类型。
Item max(Item a[], int l, int r)
{ Item u, v; int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u; else return v;
}
他的调用过程如下：
Max(0,10)
Max(0,5)
Max(0,2)
Max(0,1)
Max(0,0)
Max(1,1)
Max(2,2)
Max(3,5)
Max(3,4)
Max(3,3)
Max(4,4)
Max(5,5)
Max(6,10)
Max(6,8)
Max(6,7)
Max(6,6)
Max(7,7)
Max(8,8)
Max(9,10)
Max(9,9)
Max(10,10)
我们就不去研究在内存层面它是如何实现的，当然如果您感兴趣，可以去参考我在第一天中提到的参考书，我最近搞到了Knuth先生被叫做业界圣经的那三卷书--《计算机编程艺术》，我会在下面尽量多得消化一些更清晰的知识和大家共享。
那么后面的版面就留给那个古老的汉诺问题tower of hanoi：
汉诺塔游戏是一个古老的亚洲游戏，目标是将所有的碟子从第一根针上通过第二根针移到第三根针上。不能把大的碟子放到小的碟子上面。
/*将塔座a上的编号从1到n、直径从小到大的圆盘一倒塔座c上，b用作辅助塔座*/
/*参数n为盘子数量，a,b,c为盘子的塔名*/
/* write by：大连理工大学 孙先生*/
void hanoi(int n,char a,char b,char c)
{
if(n>0)
{
hanoi(n-1,a,c,b); /*将1至n-1个盘子从a座移动到b座上，c为辅助塔*/
printf("%d from %c to %c\n",n,a,c); /*输出移动步骤*/
hanoi(n-1,b,a,c); /*将1至n-1个盘子从b座移动到b座上，c为辅助塔*/
}
}
main()
{
int n;
printf("\nPlease enter the number of tower:");
scanf("%d",&n);
printf("\n");
hanoi(n,'a','b','c'); /*字符'a','b','c'为3个塔座的名称 */
}
哈，Robert Sedgewick讲了这么个典故，说要是寺庙里的几个和尚完成了这个任务，将40个金盘子按要求放到钻石桩上，则世界末日就会来临。放好这40个盘子，需要移动2^40-1次移动。每秒移动一次，需要348个世纪。长舒一口气，和尚命没那么长。
最后我们来写一个二分排序，想起来惭愧，一次去面试，人家让我随便拿那种语言写一个二分法，我写了很长时间，满头大汗，代码乱的要命。人家鄙视我 : ( 。我现在只是少半个程序员，自豪的是我已经可以很快写出一个二分法了 J。
// arden write binary search 2005-2-25
int bsearch(int a[], int pnumber , int begin ,int end)
{
while(begin<=end)
{
int position=(end+begin)/2;
if(a[position]==pnumber) return position;
if(a[position]<pnumber) bsearch(a, pnumber , begin , position-1);
else bsearch(a,pnumber,position+1,end);
}
return -1;
}
我为同事写过一些奥赛的初中试题，里面有一个使用分治法来解决的问题：
麦森数Mason：
形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数。2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：从文件中输入P (1000<P<3100000)
计算2P-1的值（用十进制高精度数表示），最后在文本文件上输出：
（1） 第1行：十进制高精度数2P-1的位数。
（2） 第2-11行：十进制高精度数2P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）
不必验证2P-1与 P是否为素数。
//write by arden 2005-01
//mason.c
#include <stdio.h>
#include <math.h>
//#include <string>
#include <stdlib.h>
#define Maxn 500
void main()
{
char fi[20],fo[20];
FILE * pOFile,* pIFile;
char N[Maxn];
long i,j,k,s,m;
long p,p0;
char num[8];
char c[8];
printf("input file name : \n");
scanf("%s",fi);
printf("Output file name :\n");
scanf("%s",fo);
pIFile=fopen(fi,"r");
pOFile=fopen(fo,"w");
p=atoi(fgets(num,8,pIFile));
fputs(itoa(ceil(p*log(2)/log(10)),c,10 ),pOFile);
fputc("\n",pOFile);
for(i=1;i<=Maxn;i++)
{
N[i]=1;
m=1;
}
for(i=1;i<=26;i++) m*=2;
p0=p%26;
p/=26;
for(i=1;i<=p;i++)
{
k=0;
for(j=1;j<=Maxn;j++)
{
s=N[j]*m+k;
k=s/10;
N[j]=s%10;
}
}
for(i=1;i<=p0;i++)
{
k=0;
for(j=1;j<=Maxn;j++)
{
s=N[j]*2+k;
k=s/10;
N[j]=s%10;
}
}
N[i]=N[i-1];
for(i=0;i<=9;i--)
{
for(j=1;j<=50;j--)
fputc(N[i*50+j],pOFile);
}
fclose(pIFile);
fclose(pOFile);
}
