一个边长为n（2^k）的棋盘,其中有一个位置缺失，现有如下4中图形用来覆盖棋盘，编程实现棋盘的覆盖。 四个图形：（白色部分为缺陷部分）
覆盖如下一个棋盘（4*4）：（白色部分为缺陷部分）
覆盖后的结果就为：（相同的字母代表一块）
主要思想： 将一个大问题分成若干个小问题来解决，所以很自然就能想到用递归。 具体的分割是以4*4的棋盘为例： 可以将一个4*4的棋盘分成4个2*2的小棋盘这样2*2的就可以快速的解决，同样也可以进一步细分成单个位置的，以下代码试讲棋盘最后分成单个位置来分析的。
C++代码:
#include <iostream> using namespace std; char dcount='A'; typedef struct { char value; int flag; }Signal; int Test(int low,int high,int left,int right,Signal **num) //判断当前分割的四个部分里面那三个部分可以进行填充 { //此时的填充指的是目前来说的一整部分棋盘的中心部分的三个角 int i,j; for(i=low;i<=high;i++) for(j=left;j<=right;j++) if(num[i][j].flag==1) return 0; return 1; } void CboardFill(int low,int high,int left,int right,Signal **num) //此时的填充指的是目前来说的一整部分棋盘的中心部分的三个角 { int mid1,mid2; mid1=(low+high)/2; mid2=(left+right)/2; if(Test(low,mid1,left,mid2,num)==1) { num[mid1][mid2].value=dcount; num[mid1][mid2].flag=1; } if(Test(low,mid1,mid2+1,right,num)==1) { num[mid1][mid2+1].value=dcount; num[mid1][mid2+1].flag=1; } if(Test(mid1+1,high,left,mid2,num)==1) { num[mid1+1][mid2].value=dcount; num[mid1+1][mid2].flag=1; } if(Test(mid1+1,high,mid2+1,right,num)==1) { num[mid1+1][mid2+1].value=dcount; num[mid1+1][mid2+1].flag=1; } dcount++; //标志的改变 } void fun(int low,int high,int left,int right,Signal **num) { int mid1,mid2; if(low==high) return; else { mid1=(low+high)/2; mid2=(left+right)/2; CboardFill(low,high,left,right,num); fun(low,mid1,left,mid2,num); //运用递归算法 fun(low,mid1,mid2+1,right,num); fun(mid1+1,high,left,mid2,num); fun(mid1+1,high,mid2+1,right,num); } } int main() { Signal **checkerBoard; int n,h,l,i,j; cout<<"请输入棋盘大小(2^k):"; cin>>n; cout<<"请输入的位置:"; cin>>h>>l; checkerBoard=new Signal*[n+1]; for(i=0;i<=n;i++) checkerBoard[i]=new Signal[n+1]; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { checkerBoard[i][j].value='*'; //初始化 checkerBoard[i][j].flag=0; } checkerBoard[h][l].value='#'; //#标志这个空为空 checkerBoard[h][l].flag=1; //flag=1表示这个棋盘格已经被覆盖或者缺陷的空格 fun(1,n,1,n,checkerBoard); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) cout<<checkerBoard[i][j].value<<" "; cout<<endl; } return 0; }