2.4 分治算法思想
知识点讲解：光盘：视频讲解\第2章\分治算法思想.avi
在本节将要讲解的分治算法也采取了各个击破的方法，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。只要求出子问题的解，就可得到原问题的解。
2.4.1 分治算法基础
在编程过程中，经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，可以采用各个击破的方法。具体做法是：先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治算法的基本思想。
使用分治算法解题的一般步骤如下。
① 分解，将要解决的问题划分成若干个规模较小的同类问题。
② 求解，当子问题划分得足够小时，用较简单的方法解决。
③ 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
2.4.2 实践演练——解决“大数相乘”问题
为了说明分治算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解分治算法思想在编程中的基本应用。
实例2-7 解决“大数相乘”问题
源码路径 光盘\daima\2\fenzhi.c
问题描述：所谓大数相乘，是指计算两个大数的积。
算法分析：假如计算123×456的结果，则分治算法的基本过程如下所示。
第一次拆分为：12和45，具体说明如下所示。
设char *a = "123", *b = "456"，对a实现t = strlen(a), t/2得12(0,1位臵)余3(2位臵)为3和6。
同理，对另一部分b也按照上述方法拆分，即拆分为456。
使用递归求解：12×45，求得12×45的结果左移两位补0右边，因为实际上是120×450;12×6（同上左移一位其实是120×6）;3×45（同上左移一位其实是3×450）;3×6（解的结果不移动）。
第二次拆分：12和45，具体说明如下所示。
1和4：交叉相乘并将结果相加，1×4左移两位为400,1×5左移一位为50,2×4左移一位为80,2×5不移为10。
2和5：相加得400+50+80+10=540。
另外几个不需要拆分得72、135、18，所以：54000+720+1350+18=56088。
由此可见，整个解法的难点是对分治的理解，以及结果的调整和对结果的合并。
具体实现：根据上述分治算法思想，编写实例文件fenzhi.c，具体实现代码如下所示。
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
char *result = '\0';
int pr=1;
void getFill(char *a, char *b, int ia, int ja, int ib, int jb, int tbool, int move){
int r, m, n, s, j, t;
char *stack;
m = a[ia] -48;
if(tbool){// 直接将结果数组的标志位填入，这里用了堆栈思想
r = (jb - ib > ja - ia) ? (jb - ib) : (ja - ia);
stack = (char *)malloc(r + 4);
for(r = j = 0, s = jb; s >= ib; r ++, s --){
n = b[s] -48;
stack[r] = (m * n + j) % 10;
j = (m * n + j) / 10;
}
if( j ){
stack[r] = j;
r ++;
}
for(r --; r >= 0; r --, pr ++)
result[pr] = stack[r];
free(stack);
for(move = move + pr; pr < move; pr ++)
result[pr] = '\0';
}
else{ //与结果的某几位相加，这里不改变标志位pr的值
r = pr - move -1;
for(s = jb, j = 0; s >= ib; r --, s --){
n = b[s] -48;
t = m * n + j + result[r];
result[r] = t % 10;
j = t / 10;
}
for( ; j ; r -- ){
t = j + result[r];
result[r] = t % 10;
j = t / 10;
}
}
}
int get(char*a, char*b, int ia, int ja, int ib, int jb, int t, int move){
int m, n, s, j;
if(ia == ja){
getFill(a, b, ia, ja, ib, jb, t, move);
return 1;
}
else if(ib == jb){
getFill(b, a, ib, jb, ia, ja, t, move);
return 1;
}
else{
m = (ja + ia) / 2;
n = (jb + ib) / 2;
s = ja - m;
j = jb - n;
get(a, b, ia, m, ib, n, t, s + j + move);
get(a, b, ia, m, n + 1, jb,0, s + move);
get(a, b, m + 1, ja, ib, n,0, j + move);
get(a, b, m + 1, ja, n + 1, jb,0,0 + move);
}
return 0;
}
int main(){
char *a, *b;
int n, flag;
a = (char *)malloc(1000);
b = (char *)malloc(1000);
printf("The program will computer a*b\n");
printf("Enter a b:");
scanf("%s %s", a, b);
result = (char *)malloc(strlen(a) + strlen(b) + 2);
flag = pr = 1;
result[0] = '\0';
if(a[0] == '-' && b[0] == '-')
get(a, b,1, strlen(a)-1,1, strlen(b)-1,1,0);
if(a[0] == '-' && b[0] ! = '-'){
flag = 0;
get(a, b,1, strlen(a)-1,0, strlen(b)-1,1,0);
}
if(a[0] ! = '-' && b[0] == '-'){
flag = 0;
get(a, b,0, strlen(a)-1,1, strlen(b)-1,1,0);
}
if(a[0] ! = '-' && b[0] ! = '-')
get(a, b,0, strlen(a)-1,0, strlen(b)-1,1,0);
if(! flag)
printf("-");
if( result[0] )
printf("%d", result[0]);
for(n = 1; n < pr ; n ++)
printf("%d", result[n]);
printf("\n");
free(a);
free(b);
free(result);
system("pause");
return 0;
}
执行后先分别输入两个大数，例如123和456，按下【Enter】键后将输出这两个数相乘的积。执行效果如图2-9所示。
图2-9 “大数相乘”问题的执行效果
2.4.3 实践演练——欧洲冠军杯比赛日程安排
实例2-8 使用分治算法解决“欧洲冠军杯比赛日程安排”问题
源码路径 光盘\daima\2\ouguan.c
问题描述：一年一度的欧洲冠军杯马上就要打响，在初赛阶段采用循环制，设共有n队参加，初赛共进行n-1天，每队要和其他各队进行一场比赛，然后按照最后积分选拔进入决赛的球队。要求每队每天只能进行一场比赛，并且不能轮空。请按照上述需求安排比赛日程，决定每天各队的对手。
算法分析：根据分治算法思路，将所有参赛队伍分为两半，则n队的比赛日程表可以通过n/2个队的比赛日程来决定。然后继续按照上述一分为二的方法对参赛队进行划分，直到只剩余最后2队时为止。
假设n队的编号为1,2,3, …, n，比赛日程表制作为一个二维表格，每行表示每队所对阵队的编号。例如8支球队7天比赛的日程表如表2-2所示。
表2-2 8队比赛日程表
根据表2-2的分析，可以将复杂的问题分治而解，即分解为多个简单的问题。例如有4队的比赛日程如表2-3所示。
表2-3 4队比赛日程表
具体实现：根据上述分治算法思想，编写实例文件ouguan.c，具体实现代码如下所示。
#include <stdio.h>
#define MAXN 64
int a[MAXN+1][MAXN+1]={0};
void gamecal(int k, int n)//处理编号k开始的n个球队的日程
{
int i, j;
if(n==2)
{
a[k][1]=k; //参赛球队编号
a[k][2]=k+1; //对阵球队编号
a[k+1][1]=k+1; //参赛球队编号
a[k+1][2]=k; //对阵球队编号
}else{
gamecal(k, n/2);
gamecal(k+n/2, n/2);
for(i=k; i<k+n/2; i++) //填充右上角
{
for(j=n/2+1; j<=n; j++)
{
a[i][j]=a[i+n/2][j-n/2];
}
}
for(i=k+n/2; i<k+n; i++) //填充左下角
{
for(j=n/2+1; j<=n; j++)
{
a[i][j]=a[i-n/2][j-n/2];
}
}
}
}
int main()
{
int m, i, j;
printf("参赛球队数：");
scanf("%d", &m);
j=2;
for(i=2; i<8; i++)
{
j=j*2;
if(j==m) break;
}
if(i>=8)
{
printf("参赛球队数必须为2的整数次幂，并且不超过64! \n");
getch();
return 0;
}
gamecal(1, m);
printf("\n编号 ");
for(i=2; i<=m; i++)
printf("%2d天 ", i-1);
printf("\n");
for(i=1; i<=m; i++)
{
for(j=1; j<=m; j++)
printf("%4d ", a[i][j]);
printf("\n");
}
getch();
return 0;
}
执行后先输入参赛球队数目，输入完成并按下【Enter】键会显示具体的比赛日程，执行效果如图2-10所示。
图2-10 比赛日程安排的执行效果