分治与递归
分治法的设计思想是将一个难以直接解决的大问题，分割成一些规模比较小的相同问题，不断地分割直到最终的子问题可以方便直接地求解。由分治法产生的子问题往往是原问题的较小模式，于是使用递归技术便可以逻辑明了地对问题进行求解。
递归与分治算法是常用的有效算法，递归模型结构清晰，可读性强，而且容易使用数学归纳法论证其正确性，容易掌握和调试。
棋盘覆盖问题
问题描述：（略）
使用递归分治算法的C语言实现：
#include <stdio.h>
#include <malloc.h>
#define K 8 //棋盘规模
int naChessBoard[K][K]; //棋盘矩阵
int nCardId=10; //骨牌号
//覆盖棋盘 左上角行坐标 左上角列坐标 特殊方格行坐标 特殊方格列坐标 棋盘规模
void chessBoard(int nTopLeftRow, int nTopLeftCol, int nDestRow, int nDestCol, int nSize)
{
if(nSize == 1)
{
//棋盘规模为1，直接返回
return;
}
int t = nCardId++; //当前骨牌号
int s = nSize/2; //分割棋盘，将棋盘均分为4个子棋盘
//覆盖左上角子棋盘
if ((nDestRow<nTopLeftRow+s) && (nDestCol<nTopLeftCol+s))
{
//特殊方格在此子棋盘中
chessBoard(nTopLeftRow,nTopLeftCol,nDestRow,nDestCol,s);
}
else
{
//特殊方格不在此子棋盘中
//用t号骨牌覆盖该子棋盘的右下角，即合理地将子问题转化为原问题的较小模式
naChessBoard[nTopLeftRow+s-1][nTopLeftCol+s-1] = t;
//覆盖其余方格
chessBoard(nTopLeftRow,nTopLeftCol,nTopLeftRow+s-1,nTopLeftCol+s-1,s);
}
//覆盖右上角子棋盘
if ((nDestRow<nTopLeftRow+s) && (nDestCol>=nTopLeftCol+s))
{
chessBoard(nTopLeftRow,nTopLeftCol+s,nDestRow,nDestCol,s);
}
else
{
naChessBoard[nTopLeftRow+s-1][nTopLeftCol+s] = t;
chessBoard(nTopLeftRow,nTopLeftCol+s,nTopLeftRow+s-1,nTopLeftCol+s,s);
}
//覆盖左下角子棋盘
if ((nDestRow>=nTopLeftRow+s) && (nDestCol<nTopLeftCol+s))
{
chessBoard(nTopLeftRow+s,nTopLeftCol,nDestRow,nDestCol,s);
}
else
{
naChessBoard[nTopLeftRow+s][nTopLeftCol+s-1] = t;
chessBoard(nTopLeftRow+s,nTopLeftCol,nTopLeftRow+s,nTopLeftCol+s-1,s);
}
//覆盖右下角子棋盘
if ((nDestRow>=nTopLeftRow+s) && (nDestCol>=nTopLeftCol+s))
{
chessBoard(nTopLeftRow+s,nTopLeftCol+s,nDestRow,nDestCol,s);
}
else
{
naChessBoard[nTopLeftRow+s][nTopLeftCol+s] = t;
chessBoard(nTopLeftRow+s,nTopLeftCol+s,nTopLeftRow+s,nTopLeftCol+s,s);
}
}
//打印覆盖结果
void display()
{
for (int i=0; i<K; i++)
{
for (int j=0; j<K; j++)
{
printf(" %4d",naChessBoard[i][j]);
}
printf("/n");
}
}
void main()
{
//调用递归函数，覆盖规模为K，特殊方格坐标为（0，1）的棋盘
chessBoard(0,0,0,1,K);
//打印结果
display();
}
有需要的朋友可以下载相关的Win32工程和MFC图像界面程序（多线程同步控制）http://download.csdn.net/source/2884082