关键词 递归，分治，Visual C++，课件
算法与计算理论是计算机程序设计领域的灵魂，是发挥程序设计者严谨，敏锐思维的有效工具。任何的程序设计语言都试图将之发挥得淋漓尽致，它无可厚非的作为计算机专业最重要基础类核心课程。但对于初次接触算法设计的学习者而言，他们往往不清楚算法的具体执行情况，进而自己设计算法也变得相当困难。如：在学习递归和分治算法的时候，一些人只知道递归算法的执行有压栈和出栈的两个过程，对于程序究竟怎么执行，到最后还是一头雾水，而其他的动态规划算法、回溯算法、分支限界算法等则更难掌握。针对这一情况，本人在教学中设计了一些演示程序来直观反应程序的执行顺序，并取得了较好的效果。以下就棋盘覆盖算法演示程序为例介绍算法课件的制作。
1 棋盘覆盖问题分析
图1 一种特殊棋盘
如果规模已经足够小，则覆盖完毕；分割棋盘为4部分；
在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘，如图1所示。在棋盘覆盖问题中，要用图2所示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。该问题可以采用分治法来求解，分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘，特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。算法框架如下：
图2 4种不同形态的L型骨牌覆盖算法（问题规模） 如果规模已经足够小，则覆盖完毕，分割棋盘为4部分。对于每一部分，先看该部分有无特殊方格，如果没有特殊方格，则先在该部分与其他三部分的交汇处覆盖一特殊方格，然后对该部分递归调用覆盖算法，否则该部分有特殊方格，则直接递归调用覆盖算法。
2 演示程序设计
采用C/C++语言来描述算法，所以本文课件采用Visual C++6.0进行开发，一方面能在课件源代码中体现算法本身，另一方面能直接演示算法的执行情况，使学生在掌握算法本身之外，学习一种程序实现方法，提高学生的学习兴趣，增进学习效果。在Visual C++中建立一对话框应用程序Demo，在CdemoDlg类中添加以下成员变量和函数。
void DrawTable();//根据输入的k值画棋盘
void DrawBack(); //清空棋盘上原有的图像
void DrawBoard(int x，int y，int w，int c);//画棋盘的x行，y列一个方格，w是宽度，c是颜色
int tile; //当前所用的方块
int **board; //指向棋盘的指针
int dw; //棋盘每一格的宽度
void chessBoard(int tr， int tc， int dr， int dc， int size);//棋盘覆盖算法
在对话框中添加Edit Box控件，并关联一int型变量m_k用于接收输入的k值，在演示程序中根据输入的k值计算棋盘中每一个方格的大小。在一般情况下，窗体的大小不变，当k越大时，棋盘的方格越多，这时每个方格的尺寸越小，反之越大。如整个棋盘的尺寸为512，则方格尺寸dw=512/2k。在算法演示中采用图形表示，给每个L型骨牌填充不同的颜色，在程序中把tile变量转换成颜色，画一个方格的函数定义如下：
void CDemoDlg::DrawBoard(int x， int y， int w， int c)
{
CClientDC dc(this);
COLORREF color;
color=RGB(c*c%256，c*c*c%256，c*c*c*c%256);//把c值转换成颜色
CBrush br(color); //定义一绘图画刷
CRect r; //定义一矩形区域，用来表示棋盘的一个方格
r.top =10+(x-1)*dw;
r.bottom =r.top +dw;
r.left =10+(y-1)*dw;
r.right =r.left +dw;
dc.FillRect(&r，&br); //填充绘图区域
}
在棋盘覆盖程序中，每次覆盖一个方格，为了便于清楚看到程序覆盖棋盘的顺序，每次覆盖后延迟0.5秒，并绘制出当前覆盖的方格，具体参见以下源程序。
void CDemoDlg::chessBoard(int tr， int tc， int dr， int dc， int size)
{
if (size == 1) //如果问题的规模足够小，则返回
{
return;
}