分治法的应用

分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解就是子问题的解的合并。

一、分治法应用的条件

1．该问题的规模缩小到一定的程度就可以容易地解决

2．该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3．利用该问题分解出的子问题的解可以合并为该问题的解；

4．该问题所分解出的各个子问题是相互的，即子问题之间不包含公共的子问题。

二、分治法应用的一般步骤

1．分解。将原问题分解为若干个相互，规模小，与原问题相识的子问题。 2．求解子问题。容易求出若干个子问题的解，如果不能，则继续分解子问题，直到能够快速求解为止。

3．合并。将已求的各子问题的解，合并为原问题的解。

三、分析分治法在安排循环赛中的应用

1.问题描述:

设有n位选手参加羽毛球循环赛，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天比赛一场，不能轮空，按一下要求为比赛安排日程，

（1） 每位选手必须与其他n-1格选手格赛一场； （2） 每个选手每天只能赛一场； （3） 循环赛一共进行n-1天； 2.算法分析：

此算法设计中，对于n为2的幂次方时，较为简单，可以运用分治法，将参赛选手分成两部分，再继续递归分割，直到只剩下2位选手比赛就可以的。再逐步合并子问题即可求得原问题的解。 算法设计如下：

void arrangement(int n,int N,int k,int a[100][100]) // n为参赛人数，N为天数，k为幂次数 {

for(int i=1;i<=N;i++) a[1][i] = i; int m =1;

for (int s=1;s<=k;s++) {

N/=2;

for(int t=1;t<=N;t++)

{ for(int i=m+1;i<=2*m;i++) for(int j=m+1;j<=2*m;j++)

{ a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m]; //右下角的值等于左上角的值

a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2]; //左下角的值等于右上角的值 } } m *= 2;

} }

在此算法中，先是对一个参赛人员进行安排，然后定义一个初始化值为1的m来控制每一次填充表格时i（i表示行）和j（j表示列）的起始填充位置，用一个for循环将原问题分成几个部分，再用一个for循环对每个部分进行划分。最后根据划分和分治法的思想，进行对角线的填充。

简单的的说就是先对一个人的安排，扩充到2个人，再是4个人等等，由比赛规则，确定的，一人一天只能比赛一场，因此两人的比赛安排在一天中是对角形式的。

分析算法的时间性能，迭代处理的循环体内是2个循环语句，基本的语句是赋值，也就是填写比赛日程表中的元素，基本的语句执行次数为：

T(n)= =O( )

当n为是奇数时,至少举行n 轮比赛,这时每轮必有一支球队轮空。为了统一奇数偶数的不一致性,当n 为奇数时, 可以加入第n+1 支球队( 虚拟球队, 实际上不存在) , 并按n+1 支球队参加比赛的情形安排比赛日程。那么n( n 为奇数) 支球队时的比赛日程安排和n+1 支球队时的比赛日程安排是一样的。只不过每次和n+1 队比赛的球队都轮空。所以,我们只需考虑n 为偶数时情况。将最后得出的结果，对n+1进行赋予0的操作就可以的。并且把对n+1参赛人员的安排进行赋0操作 例如：当n=3

1 2 3 4 1 2 3 0 2 3 4 1 4 3 4 1 2 3 2 1 2 3 0 1 0 0 0 1 0 3 2 0 因此对算法进行改进，把第m号虚的选手去掉（换做0） void replaceVirtual(int m) {

int i,j;

for(i=0;ifor (j=0;j<=m;j++) //列: 比行要多1

a[i][j] = (a[i][j]==m)?0:a [i][j]; }

return; }

但当n为偶数时，而n/2却为奇数时，递归返回的轮空的比赛要作进一步处理。可以在前n/2 轮比赛中让轮空选手与下一个未参赛选手进行比赛。 算法设计：

void copyodd(int m) {

int i,j;

for (j=0;j<=m;j++) //1. 求第2组的安排(前m天) {

for (i=0;iif (a[i][j]!=0) {

a[i+m][j]=a[i][j]+m; }

else //特殊处理：两个队各有一名选手有空，安排他们比赛 {

a[i+m][j] = i+1; a[i][j] = i+m+1; } } }

for(i=0,j=m+1;j<2*m;j++) {

a[i][j] = j+1; //2. 1号选手的后m-1天比赛

a[ (A[i][j] -1) ][j] = i+1; //3. 他的对手后m-1天的安排 }

for (i=1;ifor (j=m+1;j<2*m;j++)

{//2. 观察得到的规则一：向下m+1~2*m循环递增

A[i][j] = ((A[i-1][j]+1)%m==0)?A[i-1][j]+1 :m + (A[i-1][j]+1)%m;

//3. 对应第2组的对手也要做相应的安排 A[ (A[i][j]-1) ][j] = i+1; } }

return; }

3.算法时间复杂度分析：

当n／2为奇数时，迭代处理的循环体内部有2个循环结构，基本语句是循

环体内的赋值语句，即填写比赛日程表中的元素。基本语句的执行次数是： T(n)=

=O( )

此时时间复杂度为0( )。

因此，总体实现的算法复杂度为O( ) 4.整体程序运行结果及其分析： 当n为3时

在上面n为3时就出现了n/2为奇数，因此在分组时，会出现空选选手，因此对其进行加1，使之成为偶数，并在最后对此添加的偶数进行0的替换。 当输入的n为7，8时有：

比较上面两个不同参赛人数的比赛安排，你会发现其实他们没有什么本质的差别，当n为8时符合2的整数次幂，因此刚好安排，不留空选，但当n为7时，为奇数，需要做加1操作，当它做加1操作完后，符合2的整数次幂，因此在最后的赋0操作中将号码为8的赋以0，并且去除8的比赛，因此会发现当n为7或者n为8时，结果是很相似的。

而且从程序的设计，和比较上分析，可以明显的感觉到当n=8比n=7，程序所执行的要少，为此，修改一下，使之能够检测出，从程序运行开始到程序结束所花费的时间。

在相同的环境下运行结果

虽然每次运行的时间不同，但都是n=8运行的时间比n=7运行的时间少。