摘  要 为了更加清楚了解递归和分治算法的执行情况，使用该算法具体分析了棋盘覆盖问题，然后利用Visual C++制作演示课件直观显示算法的执行步骤，在实际教学中取得了很好的效果。     关键词 递归，分治，Visual C++，课件 

    0  引言

     算法与理论是计算机程序设计领域的灵魂，是发挥程序设计者严谨，敏锐思维的有效工具。任何的程序设计语言都试图将之发挥得淋漓尽致，它无可厚非的作为计算机专业最重要基础类核心课程。但对于初次接触算法设计的学习者而言，他们往往不清楚算法的具体执行情况，进而自己设计算法也变得相当困难。如：在学习递归和分治算法的时候，一些人只知道递归算法的执行有压栈和出栈的两个过程，对于程序究竟怎么执行，到最后还是一头雾水，而其他的动态规划算法、回溯算法、分支限界算法等则更难掌握。针对这一情况，本人在教学中设计了一些演示程序来直观反应程序的执行顺序，并取得了较好的效果。以下就棋盘覆盖算法演示程序为例介绍算法课件的制作。

    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;         }         Sleep(500); //延迟500毫秒       int t = tile++，  // L型骨牌号        s = size/2;  // 分割棋盘      // 覆盖左上角子棋盘      if (dr < tr + s && dc < tc + s)            chessBoard(tr， tc， dr， dc， s);      else           {// 此棋盘中无特殊方格         // 用 t 号L型骨牌覆盖右下角         board[tr + s - 1][tc + s - 1] = t;         // 覆盖其余方格         chessBoard(tr， tc， tr+s-1， tc+s-1， s);                    DrawBoard(tr + s - 1，tc + s - 1，dw，t);           }      // 覆盖右上角子棋盘      if (dr < tr + s && dc >= tc + s)         // 特殊方格在此棋盘中         chessBoard(tr， tc+s， dr， dc， s);      else           {// 此棋盘中无特殊方格       // 用 t 号L型骨牌覆盖左下角                   board[tr + s - 1][tc + s] = t;         // 覆盖其余方格        chessBoard(tr， tc+s， tr+s-1， tc+s， s);              DrawBoard(tr + s - 1，tc + s ，dw，t);           }        // 覆盖左下角子棋盘      if (dr >= tr + s && dc < tc + s)         // 特殊方格在此棋盘中         chessBoard(tr+s， tc， dr， dc， s);      else            {// 用 t 号L型骨牌覆盖右上角         board[tr + s][tc + s - 1] = t;         // 覆盖其余方格         chessBoard(tr+s， tc， tr+s， tc+s-1， s);                    DrawBoard(tr + s，tc + s - 1，dw，t);           }      // 覆盖右下角子棋盘      if (dr >= tr + s && dc >= tc + s)         // 特殊方格在此棋盘中         chessBoard(tr+s， tc+s， dr， dc， s);      else            {// 用 t 号L型骨牌覆盖左上角         board[tr + s][tc + s] = t;         // 覆盖其余方格         chessBoard(tr+s， tc+s， tr+s， tc+s， s);                    DrawBoard(tr + s ，tc + s，dw，t);           }}图3 棋盘覆盖结果    执行以上程序得到棋盘的动态覆盖次序，该次序就是递归函数的执行情况，图3是当k=3，特殊方格位于第三行第二列时，程序运行的最后结果，由于该课件能产生动态绘制效果，增加了学生的学习兴趣，使学生更加清楚的了解分治法的具体执行情况。

     3  结束语

    本文利用Visual C++制作了棋盘覆盖算法的演示课件，相对于其他的工具实现的课件而言，该课件不仅包含了算法本身，而且采用动态绘制图案的方式说明算法的执行情况，增进了教学效果。该课件的制作过程实际上也是算法的实际运用过程，在算法课程教学中，制作这类课件不仅会使学生了解算法的执行情况，而且课件本身就是对算法的一种深化和运用，课件的制作过程也同样具有很好的学习价值。

   

[1]王晓东.机算法设计与分析[M].北京:出版社，2004[2]求是科技.Visual C++ 6.0程序设计与开发技术大全[M].北京:人民邮电出版社，2004