「循环赛日程表」分治法之循环赛日程表的理解和解题思路

循环赛日程表

一、问题：

设有n=2^k个运动员，要进行网球循环赛。现在要设计一个满足以下要求的比赛日程表

（1）每个选手必须与其他n-1个选手各赛一场

（2）每个选手一天只能赛一次

（3）循环赛一共进行n-1天

将比赛日程表设计成n行n列，表中除了第一列，其他n-1列才是我们要的，数组下标行列都从0开始，第i行j列代表第（i+1）位选手在第j天的对手：

以8个选手为例子，下面是填表的步骤：

①我们先初始化第一行各个数为1~8；

②因为是递归，那么要填8x8的左下角和右下角，分别需要知道它的右上角和左上角

③而8x8的盒子它的左上角是一个4x4的盒子，要填4x4的左下角和右下角，也分别需要知道它的右上角和左上角

④现在递归到4x4的盒子的左上角，是一个2x2的盒子，它不需要递归了，直接沿对角线填左下角和右下角的数字，也就是上面的图②

⑤可以看到，经过上面的②③步，我们左上角4x4的盒子，它的·右上角和左上角已经知道了，那就可以沿对角线填它的左下角和右下角了，所以出现了图④

⑥其他的依次类推

通俗易懂地讲，就是如果你想填一个大的，你得先得出它左上角和右上角两个盒子，再沿对角线分别抄到右下角和左下角。而为了得出它左上角和右上角，就需要递归了。

下面是我源码(如有问题，欢迎各位大牛指出哈~~)：

#include <iOStream>
using namespace std;
#define N 50

//打印盒子 
        void print(int n,int game[][N]){
     
        for(int i=0;i<n;i++){
              for(int j=0;j<n;j++){
                               cout << game[i][j] << " ";
                               }
                               
                               cout << endl;
              }
     
        }


//递归函数 
  void arrange(int p,int q,int t,int arr[][N]){
           
           
           //规格为4及以上，它的左上角和右上角要递归
           if(t>=4){
                         arrange(p,q,t/2,arr);
                         arrange(p,q+t/2,t/2,arr);
                    } 
           
            //填左下角
            for(int i=p+t/2;i<p+t;i++){
                    for(int j=q;j<q+t/2;j++){
                          arr[i][j]=arr[i-t/2][j+t/2];
                          }
                    }
            //填右下角 
            for(int i=p+t/2;i<p+t;i++){
                    for(int j=q+t/2;j<q+t;j++){
                          arr[i][j]=arr[i-t/2][j-t/2];
                          }
                    }
                                  
            
      }

  //主函数
       int main(){
       int n;
       int game[N][N];
                          
       cout << "请输入选手人数:" << endl;
       cin >> n;

       //初始化第一行,其他全为0 
       for(int i=0;i<n;i++){
               for(int j=0;j<n;j++){ 
               if(i==0)         
               game[i][j]=j+1;
               else
               game[i][j]=0;
               }
             }
             
      
      //递归 
      arrange(0,0,n,game);
           
      //打印输出循环赛日程表 
      print(n,game);
        
                       
      system("pause");      
      return 0;
      }

分治法之循环赛日程表的理解和解题思路

循环赛日程表

相关阅读

栏目导航

推荐阅读

热门阅读