[C++] 分治法之棋盘覆盖、循环赛日程表 |
您所在的位置：网站首页 › 比赛日程表 › [C++] 分治法之棋盘覆盖、循环赛日程表 |
[C++] 分治法之棋盘覆盖、循环赛日程表
|
一、分治的基本思想
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 对于一个规模为 n 的问题，若问题可以容易地解决，则直接解决，否则将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 二、用分治法求解问题的主要步骤1、分解：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题； 2、解决：若子问题规模较小而容易被解决则直接解决，否则，递归地解各个子问题； 3、合并：将各子问题的解合并得到原问题的解。 三、分治法实例1、棋盘覆盖 在一个 2k * 2k 个方格组成的棋盘中，有一个方格与其它的不同，若使用以下四种 L 型骨牌覆盖除这个特殊方格的其它方格，如何覆盖。四个 L 型骨牌如下图：
图1.1 L型骨牌 棋盘中的特殊方格如图： 
图1.2 存在特殊方格的棋盘
覆盖完成后的棋盘：
图1.3 覆盖完成的棋盘
1 #include
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 |
【本文地址】