专栏首页数据魔术师分治法(Divide-and-Conquer Algorithm)经典例子分析

分治法(Divide-and-Conquer Algorithm)经典例子分析

欲下载本文相关代码,请移步留言区

上次给大家带来了分治法的基本介绍和基本思想,今天我们继续来看分治算法的几个经典例子。

01

快速排序

1.1 背景介绍

上一篇文章里给大家介绍了归并排序,今天首先给大家带来同样运用分治法来解决问题的快速排序。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

1.2 思路分析

总体思路: 分而治之。

具体操作:选中一个元素为枢轴,以这个枢轴为参照,和每个元素相比较,通过交换位置,将比该枢轴大的元素放在数组尾部,比该枢轴小的元素放在数组头部。当已这个枢轴重新排序出来之后,数组分为三个部分,小于枢轴数组,枢轴,大于枢轴数据,这时,分而治之,小于枢轴数组,大于枢轴数组分别再递归调用,即可完成排序。

伪代码如下:

  QuickSort(A,p,r)
   if p<r
        q = Partition(A,p,r)    //确定划分位置
        QuickSort(A,p,q-1)     //子数组A[p...q-1]
        QuickSort(Q,q+1,r)     //子数组A[q+1...r]
        快速排序关键过程是对数组进行划分,划分过程需要选择一个枢轴(pivot element)作为参照,围绕着这个枢轴进划分子数组
        Partition(A,p,r) //p、r为数组下标
        x = A[r]   //将最后一个元素作为主元素
        i = p-1 // i指向的是比主元素小的位置,
        for  j = p  to  r-1     //从第一个元素开始到倒数第二个元素结束,比较确定主元素的位置
        do  if  A[j] <= x
                   then  i = i+1 //如果比主元素小,则把i=i+1的位置上的元素和j位置发现小元素互换
                            exchange A[i] <-> A[j]
        exchange A[i+1]<->A[r]   //最终确定主元的位置
        return i+1   //返回主元的位置

1.3 code time

/*参考数据结构p274(清华大学出版社,严蔚敏)*/
#include <iostream>

using namespace std;

void Qsort(int a[], int low, int high)
{
    if(low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = a[first];/*用字表的第一个记录作为枢轴*/

    while(first < last)
    {
        while(first < last && a[last] >= key)
        {
            --last;
        }

        a[first] = a[last];/*将比第一个小的移到低端*/

        while(first < last && a[first] <= key)
        {
            ++first;
        }

        a[last] = a[first];    
/*将比第一个大的移到高端*/
    }
    a[first] = key;/*枢轴记录到位*/
    Qsort(a, low, first-1);
    Qsort(a, first+1, high);
}
int main()
{
    int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};

    Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/

    for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        cout << a[i] << " ";
    }

    return 0;
}

02

大整数乘法

2.1 背景介绍

在计算机中,长整形(long int)变量的范围是-2147483648至2147483647,因此若用长整形变量做乘法运算,乘积最多不能超过10位数。即便用双精度(double)变量,也仅能保证16位有效数字的精度。所以需要用算法来解决大整数相乘的问题。

2.2 思路分析

问题的关键如下:

利用公式可将问题转化为递归的形式并加以解决。

2.3 code time

#include <iostream>
#include <cmath>
using namespace std;

int sign(int x)
{
    return x > 0 ? 1 : -1;
}

int divideConquer(int x, int y, int n)
{
    int s = sign(x) * sign(y);      // 正负号
    x = abs(x);
    y = abs(y);
    if(x == 0 || y == 0)
         return 0;
    else if(n == 1)
        return s * x * y;
    else
    {
        int A = (int) x / pow(10, (int)(n / 2));
        int B = x - A * pow(10, n / 2);
        int C = (int) y / pow(10, (int)(n / 2));
        int D = y - C * pow(10, n / 2);
        int AC = divideConquer(A, C, n / 2);
        int BD = divideConquer(B, D, n / 2);
        int ABDC = divideConquer((A - B), (D - C), n / 2) + AC + BD;
        return s * (AC * pow(10 , n) + ABDC * pow(10, (int)(n / 2)) + BD);  
    }
}

int main()
{
    int a = 1234, b = -9876;
    int result = divideConquer(a,b,4);
    cout<<a<<" * " <<b<<" = "<<result;
}
//1、添加了sign函数的实现
//2、因为当n为1时的计算考虑了正负性,所以x与y应该用abs计算,否则所有有关符号的东西都去掉也是可以的。
//3、这个程序只是表现了分治算法的思想,但是真正的大数还是不能计算(考虑到溢出)

03

Strassen矩阵算法

3.1 背景介绍

矩阵乘法是种极其耗时的运算。

以C = A • B为例,其中A和B都是 n x n 的矩阵。根据矩阵乘法的定义,计算过程如下:

//矩阵乘法,3个for循环搞定   
void Mul(int** matrixA, int** matrixB, int** matrixC)   
{   
    for(int i = 0; i < 2; ++i)    
    {   
        for(int j = 0; j < 2; ++j)    
        {   
            matrixC[i][j] = 0;   
            for(int k = 0; k < 2; ++k)    
            {   
                matrixC[i][j] += matrixA[i][k] * matrixB[k][j];   
            }   
        }   
    }   
} 

由于存在三层循环,它的时间复杂度将达到O(n3)。

下面介绍Strassen算法,该算法将时间复杂度降低到O(nlg7) ≈ O(n2.81)。

3.2 思路分析

Strassen算法是一种基于分治策略的改进算法,我们先来看下简单的分治算法。

经计算可以看到,分治策略改进的矩阵计算并不能降低时间复杂度。要想提高算法效率,由主定理方法可知必须想办法将2中递归式中的系数8减少。Strassen算法就是基于此进行了改进。

如图所示:

Strassen用了更多的步骤,成功的把计算量变成了7个矩阵乘法和18个矩阵加法。虽然矩阵加法增加了好几倍,而矩阵乘法只减小了1个,但在数量级面前,18个加法仍然渐进快于1个乘法。这就是该算法的精妙之处。

3.3 code time

代码如下

#include <bits/stdc++.h>
using namespace std;

//矩阵相乘朴素法函数
void Mul(int** MatrixA, int** MatrixB, int** MatrixResult,int length)
{
    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < length; j++)
        {
            MatrixResult[i][j] = 0;
            for (int k = 0; k < length; k++)
            {
                MatrixResult[i][j] = MatrixResult[i][j] + MatrixA[i][k] * MatrixB[k][j];
            }
        }
    }
}

//矩阵相减函数
void Sub(int** MatrixA, int** MatrixB, int** MatrixResult,int length)
{
    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < length; j++)
        {
            MatrixResult[i][j] = MatrixA[i][j] - MatrixB[i][j];
        }
    }
}

//矩阵相加函数
void Add(int** MatrixA, int** MatrixB, int** MatrixResult, int length)
{
    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < length; j++)
        {
            MatrixResult[i][j] = MatrixA[i][j] + MatrixB[i][j];
        }
    }
}

//Strasssen法
void Strassen(int** matrixA, int** matrixB, int** matrixResult, int length)
{
    int halfLength = length / 2;
    int newlength = length / 2;

    //如果矩阵维度等于2,用一般法求解
    if (length == 2)
    {
        Mul(matrixA, matrixB, matrixResult, length);
    }
    else
    {

        int** a11 = new int*[newlength];
        int** a12 = new int*[newlength];
        int** a21 = new int*[newlength];
        int** a22 = new int*[newlength];

        int** b11 = new int*[newlength];
        int** b12 = new int*[newlength];
        int** b21 = new int*[newlength];
        int** b22 = new int*[newlength];

        int** s1 = new int*[newlength];
        int** s2 = new int*[newlength];
        int** s3 = new int*[newlength];
        int** s4 = new int*[newlength];
        int** s5 = new int*[newlength];
        int** s6 = new int*[newlength];
        int** s7 = new int*[newlength];

        int** matrixResult11 = new int*[newlength];
        int** matrixResult12 = new int*[newlength];
        int** matrixResult21 = new int*[newlength];
        int** matrixResult22 = new int*[newlength];

        int** temp = new int*[newlength];
        int** temp1 = new int*[newlength];
        int newsize = newlength;

        //矩阵分割
        for (int i = 0; i < newlength; i++)
        {
            a11[i] = new int[newsize];
            a12[i] = new int[newsize];
            a21[i] = new int[newsize];
            a22[i] = new int[newsize];

            b11[i] = new int[newsize];
            b12[i] = new int[newsize];
            b21[i] = new int[newsize];
            b22[i] = new int[newsize];

            s1[i] = new int[newsize];
            s2[i] = new int[newsize];
            s3[i] = new int[newsize];
            s4[i] = new int[newsize];
            s5[i] = new int[newsize];
            s6[i] = new int[newsize];
            s7[i] = new int[newsize];

            matrixResult11[i] = new int[newsize];
            matrixResult12[i] = new int[newsize];
            matrixResult21[i] = new int[newsize];
            matrixResult22[i] = new int[newsize];

            temp[i] = new int[newsize];
            temp1[i] = new int[newsize];
        }
        //计算分割矩阵a,b
        for (int i = 0; i < length / 2; i++)
        {
            for (int j = 0; j < length / 2; j++)
            {
                a11[i][j] = matrixA[i][j];
                a12[i][j] = matrixA[i][j + length / 2];
                a21[i][j] = matrixA[i + length / 2][j];
                a22[i][j] = matrixA[i + length / 2][j + length / 2];
                b11[i][j] = matrixB[i][j];
                b12[i][j] = matrixB[i][j + length / 2];
                b21[i][j] = matrixB[i + length / 2][j];
                b22[i][j] = matrixB[i + length / 2][j + length / 2];
            }
        }

        //计算s1
        Add(a11, a22, temp, halfLength);
        Add(b11, b22, temp1, halfLength);
        Strassen(temp, temp1, s1, halfLength);

        //计算s2
        Add(a21, a22, temp, halfLength);
        Strassen(temp, b11, s2, halfLength);

        //计算s3
        Sub(b12, b22, temp1, halfLength);
        Strassen(a11, temp1, s3, halfLength);

        //计算s4
        Sub(b21, b11, temp1, halfLength);
        Strassen(a22, temp1, s4, halfLength);

        //计算s5
        Add(a11, a12, temp, halfLength);
        Strassen(temp, b22, s5, halfLength);

        //计算s6
        Sub(a21, a11, temp, halfLength);
        Add(b11, b12, temp1, halfLength);
        Strassen(temp, temp1, s6, halfLength);

        //计算s7
        Sub(a12, a22, temp, halfLength);
        Add(b21, b22, temp1, halfLength);
        Strassen(temp, temp1, s7, halfLength);

        //计算matrixResult11
        Add(s1, s4, temp, halfLength);
        Sub(s7, s5, temp1, halfLength);
        Add(temp, temp1, matrixResult11, halfLength);

        //计算matrixResult12
        Add(s3, s5, matrixResult12, halfLength);

        //计算matrixResult21
        Add(s2, s4, matrixResult21, halfLength);

        //计算matrixResult22
        Add(s1, s3, temp, halfLength);
        Sub(s6, s2, temp1, halfLength);
        Add(temp, temp1, matrixResult22, halfLength);

        //计算结果矩阵
        for (int i = 0; i < length / 2; i++)
        {
            for (int j = 0; j < length / 2; j++)
            {
                matrixResult[i][j] = matrixResult11[i][j];
                matrixResult[i][j + length / 2] = matrixResult12[i][j];
                matrixResult[i + length / 2][j] = matrixResult21[i][j];
                matrixResult[i + length / 2][j + length / 2] = matrixResult22[i][j];
            }
            //释放内存
            delete(a11[i]);
            delete(a12[i]);
            delete(a21[i]);
            delete(a22[i]);

            delete(b11[i]);
            delete(b12[i]);
            delete(b21[i]);
            delete(b22[i]);

            delete(s1[i]);
            delete(s2[i]);
            delete(s3[i]);
            delete(s4[i]);
            delete(s5[i]);
            delete(s6[i]);
            delete(s7[i]);

            delete(matrixResult11[i]);
            delete(matrixResult12[i]);
            delete(matrixResult21[i]);
            delete(matrixResult22[i]);

            delete(temp[i]);
            delete(temp1[i]);
        }
        delete(a11);
        delete(a12);
        delete(a21);
        delete(a22);

        delete(b11);
        delete(b12);
        delete(b21);
        delete(b22);

        delete(s1);
        delete(s2);
        delete(s3);
        delete(s4);
        delete(s5);
        delete(s6);
        delete(s7);

        delete(matrixResult11);
        delete(matrixResult12);
        delete(matrixResult21);
        delete(matrixResult22);

        delete(temp);
        delete(temp1);
    }

}

//矩阵A,B初始化赋值函数
void FillMatrix(int** MatrixA, int** MatrixB, int** MatrixResult, int length)
{
    srand(time(0));
    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < length; j++)
        {
            MatrixA[i][j] = rand()%10;
            MatrixB[i][j] = rand()%10;
            MatrixResult[i][j] = 0;
        }
    }
}
    int main()
    {
        int length = 8;  //初始化矩阵维度
        int** MatrixA;    //存放矩阵A
        int** MatrixB;    //存放矩阵B
        int** MatrixResult;    //存放结果矩阵
        MatrixA =new int*[length];
        MatrixB =new int*[length];
        MatrixResult =new int*[length];
        for (int i = 0; i < length; i++)
        {
            MatrixA[i] =new int[length];
            MatrixB[i] =new int[length];
            MatrixResult[i] =new int[length];
        }

        //矩阵赋值
        FillMatrix(MatrixA, MatrixB, MatrixResult,length);  

        cout << "初始化A矩阵为:" << endl;
        for (int i = 0; i < length; i++)
        {
            for (int j = 0; j < length; j++)
                cout << MatrixA[i][j] << " ";
            cout << endl;
        }

        cout << "初始化B矩阵为:" << endl;
        for (int i = 0; i < length; i++)
        {
            for (int j = 0; j < length; j++)
                cout << MatrixB[i][j] << " ";
            cout << endl;
        }

        //利用Strassen法求矩阵A*B
        Strassen( MatrixA, MatrixB, MatrixResult, length);

        //输出矩阵A*B
        cout << "矩阵A*B=" << endl;
        for (int i = 0; i < length; i++)
        {
            for (int j = 0; j < length; j++)
                cout << MatrixResult[i][j] << " ";
            cout << endl;
        }
        return 0;
    }

04

棋盘覆盖问题

4.1 背景介绍

在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖。四个L型骨牌如下图:

特殊的方格位置如下:

4.2 思路分析

可以用数学归纳法证明一定有解。

下面来用分治的思想解决问题。

1.当k>0时,将2k*2k棋盘分隔称为4个2(k-1)*2(k-1)子棋盘。

2.特殊的方格肯定在这4个较小的棋盘中,其余3个子棋盘肯定没有特殊方格。用一个L方格覆盖这3个子棋盘的汇合处。

3.这3个子棋盘被覆盖L形骨牌就成了3个有特殊方格的棋盘,然后递归求解,直至转化2*2棋盘。

4.3 code time

#include <iostream>       
using namespace std;   

int tile = 0;//骨牌编号  
int Board[4][4];//棋盘  
void ChessBoard(int tr,int tc,int dr,int dc,int size);  

int main()  
{  
    for(int i=0; i<4; i++)  
    {  
        for(int j=0; j<4; j++)  
        {  
            Board[i][j] = 0;  
        }  
    }  

    ChessBoard(0,0,1,2,4);  

    for(int i=0; i<4; i++)  
    {  
        for(int j=0; j<4; j++)  
        {  
            cout<<Board[i][j]<<" ";  
        }  
        cout<<endl;  
    }  
}  

/** 
 * tr : 棋盘左上角的行号,tc棋盘左上角的列号 
 * dr : 特殊方格左上角的行号,dc特殊方格左上角的列号 
 * size :size = 2^k 棋盘规格为2^k*2^k 
 */  
void ChessBoard(int tr,int tc,int dr,int dc,int size)  
{  
    if(size == 1)  
    {  
        return;  
    }  
    int t = tile++;//L型骨牌编号  
    int s = size/2;//分割棋盘  

    //覆盖左上角子棋盘  
    if(dr<tr+s && dc<tc+s)//特殊方格在此棋盘中  
    {  
        ChessBoard(tr,tc,dr,dc,s);  
    }  
    else//特殊方格不在此棋盘中  
    {  
        //用编号为t的骨牌覆盖右下角  
        Board[tr+s-1][tc+s-1] = t;  
        //覆盖其余方格  
        ChessBoard(tr,tc,tr+s-1,tc+s-1,s);  
    }  

    //覆盖右上角子棋盘  
    if(dr<tr+s && dc>=tc+s)//特殊方格在此棋盘中  
    {  
        ChessBoard(tr,tc+s,dr,dc,s);  
    }  
    else//特殊方格不在此棋盘中  
    {  
        //用编号为t的骨牌覆盖左下角  
        Board[tr+s-1][tc+s] = t;  
        //覆盖其余方格  
        ChessBoard(tr,tc+s,tr+s-1,tc+s,s);  
    }  

    //覆盖左下角子棋盘  
    if(dr>=tr+s && dc<tc+s)//特殊方格在此棋盘中  
    {  
        ChessBoard(tr+s,tc,dr,dc,s);  
    }  
    else//特殊方格不在此棋盘中  
    {  
        //用编号为t的骨牌覆盖右上角  
        Board[tr+s][tc+s-1] = t;  
        //覆盖其余方格  
        ChessBoard(tr+s,tc,tr+s,tc+s-1,s);  
    }  

    //覆盖右下角子棋盘  
    if(dr>=tr+s && dc>=tc+s)//特殊方格在此棋盘中  
    {  
        ChessBoard(tr+s,tc+s,dr,dc,s);  
    }  
    else//特殊方格不在此棋盘中  
    {  
        //用编号为t的骨牌覆盖左上角  
        Board[tr+s][tc+s] = t;  
        //覆盖其余方格  
        ChessBoard(tr+s,tc+s,tr+s,tc+s,s);  
    }  

}  

05

线性时间选择问题

5.1 背景介绍

从数组中选择第i小的数,并且要求问题的渐近时间复杂度为O(n)。

5.2 思路分析

线性时间选择随机划分法可以模仿随机化快速排序算法设计。对输入数组进行递归划分,与快速排序不同的是,它只对划分出的子数组之一进行递归处理,用一个随机的序列中的数作为枢纽,用快速排序算法,进行一次快排,然后将枢纽值和k值进行比较,以此来确定k值。

性能:平均O(n) 最坏O(n^2) 伪代码如下:

RANDOMIZED-SELECT ( A, p, r, i )
if  p = r           // 临界问题处理
       then  return A[p]
q ← RANDOMIZED-PARTITION( A, p, r )   //进行划分,返回划分元下标
k ← q – p + 1
if  i = k
       then return A[q];
else if i < k
        then return RANDOMIZED-SELECT ( A, p, q - 1, i )
else 
         return RANDOMIZED-SELECT( A, q+1, r, i – k )

5.3 code time

#include <iostream>
#include <ctime>
#define N 10
using namespace std;

//交换两个变量的值
void exchange(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

// 求分割点的位置
int partition(int * array, int low, int high)
{
    int i = low - 1;
    //默认将划分段的最后一个元素为主元
    int x = array[high];

    for (int j = low; j < high; j++)
    {
        if (array[j] <= x)//在array[i]左边都是小于x即array[high]的数,右边均是大于它的数
        {
            i += 1;
            exchange(array[i], array[j]);
        }
    }
    exchange(array[i + 1], array[high]);
    return i + 1;       // 循环完毕后,i+1就是该数组的分割点
}

// 以low ~ high 之间的一个随机元素作为主元,返回分割点的位置
int RandomPartition(int *array, int low, int high)
{
    //找到low ~ high 之间的一个随机位置
    int i = rand() % (high - low + 1) + low;

    //交换该随机主元至尾部,
    exchange(array[i], array[high]);

    return partition(array, low, high);
}

// 从无序序列中选择第i个大小的元素
int RandomizedSelect(int *data, int l, int h, int i)
{
    //如果输入序列中仅有一个元素
    if (l == h)
        return data[l];

    //求分割点pos,该位置左边元素均小于data[pos] , 右边元素均大于data[pos]
    int pos = RandomPartition(data, l, h);

    //求该分割点是第几小元素
    int k = pos - l + 1;

    //如果就是当前第i小元素,则返回data[pos]
    if (k == i)
        return data[pos];
    else if (k < i)
        return RandomizedSelect(data, pos + 1, h, i - k);
    else
        return RandomizedSelect(data, l, pos - 1, i);
}

int main()
{
    //声明一个待排序数组   
    int array[N];
    //设置随机化种子,避免每次产生相同的随机数    
    srand((unsigned)time(NULL));
    for (int i = 0; i<N; i++)
        array[i] = rand() % 101;    //数组赋值使用随机函数产生1-100之间的随机数
    cout << "原序列:" << endl;
    for (int j = 0; j<N; j++)
        cout << array[j] << "  ";

    cout << endl << "从小到大排在第5位的是: " ;
    cout << RandomizedSelect(array, 0, N - 1 , 5);
    cout << endl;

    return 0;
}

06

最接近点对问题

6.1 背景介绍

给定直线上n个点,找其中的一对点,使得在n个点的所有点对中,该点对的距离最小。

6.2 思路分析

最基本的思路我们只要将每一点与其他n-1个点的距离算出,找出达到最小距离的两个点即可。然而,这样做效率太低,需要O(n^2)的计算时间。

下面分析分治法:

考虑将所给的n个点的集合S分成2个子集S1和S2,每个子集中约有n/2个点,然后在每个子集中递归地求其最接近的点对。

如何实现分治法中的合并步骤,即由S1和S2的最接近点对,如何求得原集合S中的最接近点对,因为S1和S2的最接近点对未必就是S的最接近点对,类似之前的最大子序列问题。

通过观察发现,当合并时,最小的一定是前一个序列的最大和后一个序列的最小点。

可用分治法解决。

6.3 code time

//参考自https://blog.csdn.net/liufeng_king/article/details/8484284
#include<bits/stddc++.h>
using namespace std;
const int maxn=100005;
struct Point{
  double x;
}p[maxn];

int a[maxn];
int cmpx(Point a,Point b){
  return a.x<b.x;
}
inline double dis(Point a,Point b){
   if(a.x>b.x) return a.x-b.x;
   else return b.x-a.x;
}

double closest(int low,int high){
  if(low+1==high)  //只有两个点
    return dis(p[low],p[high]);
  if(low+2==high)  //只有三个点
    return min(dis(p[low],p[high]),min(dis(p[low],p[low+1]),dis(p[low+1],p[high])));
  int mid=(low+high)/2; //求中点即左右子集的分界线
  double d=min(closest(low,mid),closest(mid+1,high));
  d=min(d,dis(p[mid],p[mid+1])); //最后一步,合并
  return d;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++)
            scanf("%lf",&p[i].x);
        sort(p,p+n,cmpx);
        printf("%.2lf\n",closest(0 , n-1));//最近点对间的距离
    }
    return 0;

07

循环赛日程表问题

7.1 背景介绍

设有n(n=2^k)支队伍參加循环赛,循环赛共进行n-1天,每支队伍要与其它n-1支队伍比赛一场,且每支队伍每天必须比赛一场,不能轮空。试按此要求为比赛安排日程。

7.2 思路分析

基本思路是按分治策略,我将所有的选手分为两半,则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分,直到只剩下两个选手。

我们来看具体的实现。

我们先安排奇数下标位置与偶数下标位置之间的比赛,全部奇数号组成一个序列[1,3...n-1],以奇数组[1,3,5,7]为例,接下来,再将队伍一分为二,得到[15],[37],此时已不可再分出子队伍,计算结束。

7.3 code time

// team: 比赛安排结构,team[2k] vs team[2k+1] 
// len: team的总数 
// id: 第id轮的安排,id的范围[1, len-1] 
#include<iostream>
using namespace std;
const int len = 8;

void game(int *team, int len, int id)
{
    int base = 2;
    while (id > len/base)
    {
        id = id - len/base;
        base = base * 2;
    }
    for (int i = 0; i < base/2; i++)
    {
        int start = i + base/2 + (id-1) * base;
        for (int j=0; j<len/base; j++)
        {
            team[i*2*len/base+2*j] = base*j+i;
            team[i*2*len/base+2*j+1] = (start+base*j)%len;
        }
    }
}

void dump(int *arr, int len)
{
    for (int i=0; i<len; i+=2)
        cout<< arr[i] <<" VS "<<arr[i+1]<<" ";
    cout<<endl;
}

int main()
{
    int team[len];
    for (int i=1; i<len; i++)
    {
        game(team, len, i);
        cout<<"DAY "<<i<<" ";
        dump(team, len);
    }
    return 0;

08

总结

可以看到,虽然问题很多种多样,但共同点都是划分子问题,利用计算机的递归求解,最后合并问题。

分治,是一种思想。希望大家不论是在设计程序,或是平常生活中都能利用上这种思想,成为更好的算法master!

— END —

文案 && 代码:李博骁 审核:田彬 && 苏锷

指导老师: 秦时明岳(华中科技大学管理学院)

如对文中内容有疑问,欢迎交流。PS:部分资料来自网络。

如有需求,可以联系:

秦虎老师(professor.qin@qq.com)

李博骁 (华中科技大学管理学院 本科一年级 : 1642940680@qq.com)

田彬 (山东大学 物流工程 研二:2917837684@foxmail.com)

苏锷 (中南大学 信息与计算科学 本科四年级: hexing15@gmail.com)

精彩文章推荐

30行代码搞定简单手写识别!

年薪百万的王宝强和月入三千的吴彦祖,你更愿意pick谁?

"最萌身高差"究竟有多萌?

机器学习|模型选择之划分数据集及Sklearn实现

本文分享自微信公众号 - 数据魔术师(data-magician),作者:李博骁

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 干货|十分钟快速get蚁群算法(附代码)

    之前分享了TSP的动态规划解法,本期来介绍它的另一种解法——蚁群算法。 什么?不知道?次元壁?高大上? 小编接下来这套 素质三连 攻略三连...

    用户1621951
  • 干货 | 人工鱼群算法 超详细解析附JAVA代码

    说到这个人工鱼群算法,又想起了小编的卢浮宫……在今年年初的美赛中,小编用的就是这个算法,只不过……参加今年美赛的同学都懂的。

    用户1621951
  • 经典优化算法之分治法(Divide-and-Conque Algorithm)

    分治分治,即分而治之。分治,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即...

    用户1621951
  • 04:垂直直方图

    4:垂直直方图 总时间限制: 1000ms 内存限制: 65536kB描述 输入4行全部由大写字母组成的文本,输出一个垂直直方图,给出每个字符出现的次数。注...

    attack
  • 洛谷P1043 数字游戏

    题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前...

    attack
  • LeetCode 第 28 场双周赛(505/2144,前23.6%)

    全国排名: 505 / 2144,23.6%;全球排名: 1944 / 8571,22.7%

    Michael阿明
  • LeetCode 347. 前 K 个高频元素(哈希/优先队列)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/top-k-frequent-elements 著作...

    Michael阿明
  • LeetCode 223. 矩形面积

    Michael阿明
  • 【hihocoder 1424】 Asa's Chess Problem(有源汇上下界网络流)

    饶文津
  • 【POJ 3321】Apple Tree

    有n个节点以1为根节点的树,给你树的边关系u-v,一开始每个节点都有一个苹果,接下来有两种操作,C x改变节点x的苹果状态,Q x查询x为根的树的所有苹果个数。

    饶文津

扫码关注云+社区

领取腾讯云代金券