1.实验目的
(1)掌握递归与分治法的处理思路与算法框架。
(2)掌握应用递归与分治法解决具体问题的方法。
2.实验内容
(1)问题描述
(2)输入
(3)输出
棋盘覆盖的方案。用数组表示棋盘，骨牌块号用数字表示，并输出颜色。
3.问题实例分析
我们称含“特殊方格”的区域为“特殊区域”。如图所示，1号区域含特殊方格，我们可以称其为“特殊区域”。为了将不含特殊方格的区域转化为特殊区域，可以在这三个区域的交界处放置一个L型骨牌。如图所示。
当大的特殊棋盘被转化成的特殊棋盘时，其中一个方格是特殊方格，剩下三个方格可以直接被L型骨牌覆盖。事实上，在程序实现时，仍然认为剩下三个区域的交界处被放置一个L型骨牌。如图所示。
在将4个小特殊棋盘覆盖完成后，可以看到完整的大特殊棋盘的效果。
4.算法描述及说明
数据结构
5.算法正确性分析
7.运行结果及展示说明
8.心得体会
9.程序源代码
#include<iostream> #include<cmath> #include<iomanip> #include<windows.h> using namespace std; int tile = 1; int board[128][128]; void chessboard(int tr, int tc, int dr, int dc, int size) { //tr:棋盘左上角方格行号 //tc:棋盘左上角方格列号 //dr:特殊方格行号 //dc:特殊方格列号 //size:当前棋盘大小 if (size == 1) return; int t = tile++;//L型骨牌号 int s = size / 2;//子棋盘大小 //(tr+s-1,tc+s-1)代表左上棋盘的右下角 if (dr < tr + s && dc < tc + s) { chessboard(tr, tc, dr, dc, s);//特殊方格落在左上棋盘，则填充该左上棋盘 } else { 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 { 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 { 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 { board[tr + s][tc + s] = t; chessboard(tr + s, tc + s, tr + s, tc + s, s); } } int main() { HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE); //获取缓冲区句柄，在输出颜色时使用 int k; cout << "请输入棋盘大小:"; cin >> k; int size = pow(2, k); int dr, dc; cout << "请输入特殊方格坐标:"; cin >> dr >> dc; chessboard(0, 0, dr, dc, size); for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { SetConsoleTextAttribute(hCon, board[i][j]%6+1); //设置文本及背景色，数字设置了输出颜色 cout <<setw(4)<< board[i][j]; } cout << endl; } return 0; }
