[C++] 分治法之棋盘覆盖、循环赛日程表

不念不忘少年蓝@ 2023-10-06 09:41 1阅读 0赞

### 一、分治的基本思想 ###

将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

对于一个规模为 n 的问题，若问题可以容易地解决，则直接解决，否则将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

### 二、用分治法求解问题的主要步骤 ###

1、分解：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题；

2、解决：若子问题规模较小而容易被解决则直接解决，否则，递归地解各个子问题；

3、合并：将各子问题的解合并得到原问题的解。

### 三、分治法实例 ###

1、棋盘覆盖

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

![format_png][]

图1.1 L型骨牌

棋盘中的特殊方格如图：

![format_png 1][]

图1.2 存在特殊方格的棋盘

覆盖完成后的棋盘：

![format_png 2][]

图1.3 覆盖完成的棋盘

1 #include<iostream>
     2 using namespace std;
     3 
     4 int tile = 0;
     5 int Board[4][4];    //棋盘 
     6 
     7 /*
     8 tr:棋盘左上角方格的行号 
     9 tc:棋盘左上角方格的列号
    10 dr:特殊方格所在的行号 
    11 dc:特殊方格所在的列号
    12 size:棋盘的规格（size * size)
    13 */
    14 void ChessBoard(int tr,int tc , int dr, int  dc, int size)
    15 {
    16     if(size == 1) return;
    17     int t =tile++,        //L型骨牌号 
    18         s = size/2;        //分割棋盘 
    19     //覆盖左上角子棋盘 
    20     if(dr < tr+s && dc < tc+s)
    21         //特殊方格在此棋盘中 
    22         ChessBoard(tr,tc,dr,dc,s);
    23     else
    24     {    //此棋盘中无特殊方格
    25         //用t号L型骨牌覆盖右下角 
    26         Board[tr+s-1][tc+s-1] = t;
    27         //覆盖其余方格 
    28         ChessBoard(tr,tc,dr,dc,s);
    29     }
    30     
    31     //覆盖右上角子棋盘
    32     if(dr < tr+s && dc >= tc+s)
    33         //特殊方格在此棋盘中
    34         ChessBoard(tr,tc+s,dr,dc,s);
    35     else
    36     {    //此棋盘中无特殊方格
    37         //用t号L型骨牌覆盖左下角
    38         Board[tr+s-1][tc+s] = t;
    39         //覆盖其余方格 
    40         ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
    41     }
    42     
    43     //覆盖左下角子棋盘
    44     if(dr >= tr+s && dc < tc+s)
    45         //特殊方格在此棋盘中
    46         ChessBoard(tr+s,tc,dr,dc,s);
    47     else
    48     {    //此棋盘中无特殊方格
    49         //用t号L型骨牌覆盖右上角
    50         Board[tr+s][tc+s-1] = t;
    51         //覆盖其余方格 
    52         ChessBoard(tr+s,tc,tr+s,tc+s-1,s);
    53     }
    54     
    55     //覆盖右下角子棋盘
    56     if(dr >= tr+s && dc >= tc+s)
    57         //特殊方格在此棋盘中
    58         ChessBoard(tr+s,tc+s,dr,dc,s);
    59     else
    60     {    //此棋盘中无特殊方格
    61         //用t号L型骨牌覆盖左上角
    62         Board[tr+s][tc+s] = t;
    63         //覆盖其余方格 
    64         ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
    65     }
    66 
    67 }
    68 
    69 int main()
    70 {
    71     ChessBoard(0 , 0 , 1 , 3 , 4);
    72     //输出覆盖完成后的棋盘
    73     for(int i = 0 ; i < 4; i++)
    74     {
    75         for(int j = 0 ; j < 4; j++)
    76         {
    77             cout<<Board[i][j];
    78         }
    79         cout<<endl;
    80     }
    81     return 0;
    82 }

2、循环赛日程表

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

(1)每个选手必须与其他n-1个选手各赛一次；

(2)每个选手一天只能参赛一次；

(3)循环赛在n-1天内结束*。*

请按此要求将比赛日程表设计成有 n 行和 n-1 列的一个表。在表中的第 i 行，第 j 列处填入第 i 个选手在第 j 天所遇到的选手。其中 1 ≤ i ≤ n，1 ≤ j ≤ n-1。8 个选手的比赛日程表如下图：

![format_png 3][]

1 #include<iostream>
     2 using namespace std;
     3 
     4 int a[100][100];
     5 int n;    //选手的个数
     6 
     7 /*
     8 tox:目标数组的行号 
     9 toy:目标数组的列号 
    10 fromx:源数组的行号 
    11 fromy:源数组的列号 
    12 r:数组的大小为 r*r 
    13 */
    14 void Copy(int tox, int toy, int fromx, int fromy, int r)
    15 {
    16     for(int i = 0; i < r; i++)
    17         for(int j = 0; j < r; j++)  
    18             a[tox+i][toy+j] = a[fromx+i][fromy+j];
    19 }
    20 
    21 void Table(int k)
    22 {    
    23     n = 1 << k;    
    24     //构造正方形表格的第一行数据
    25     for(int i = 0; i < n; i++)
    26         a[0][i] = i + 1;
    27     //采用分治算法，构造整个循环赛日程表
    28     for(int r = 1; r < n; r <<= 1)
    29         for(int i = 0; i < n; i += 2*r)
    30         { 
    31             Copy(r, r + i, 0, i, r);        //左上角复制到右下角 
    32             Copy(r, i, 0, r + i, r);        //右上角复制到左下角 
    33         }
    34 }
    35 
    36 
    37 int main()
    38 {
    39     int k;
    40     cout<<"请输入k的值：";
    41     cin>>k; 
    42     
    43     Table(k);
    44     
    45     for(int i = 0; i < n; i++)
    46     {
    47         for(int j = 0; j < n; j++)
    48         {
    49             cout<< a[i][j] << " ";
    50         }
    51         cout<<endl;
    52     } 
    53     return 0;
    54 }

[format_png]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUyMjIxMjc1OTU1NC0xNDg3MDI5MjY2LmpwZw?x-oss-process=image/format,png
[format_png 1]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUyMjIxMjM0ODk3Ni0xMjQyMTQ0ODk5LmpwZw?x-oss-process=image/format,png
[format_png 2]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUyMjIxMjQxNDkxMy0xNzI2MDU4NjY3LmpwZw?x-oss-process=image/format,png
[format_png 3]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUyMjIxNTE0MzcyNi0yMTEyNzI0MTQ5LmpwZw?x-oss-process=image/format,png