课件的制作研究论文

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

关键词递归，分治，VisualC++，课件

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。算法框架如下：

图24种不同形态的L型骨牌覆盖算法（问题规模）

如果规模已经足够小，则覆盖完毕，分割棋盘为4部分。对于每一部分，先看该部分有无特殊方格，如果没有特殊方格，则先在该部分与其他三部分的交汇处覆盖一特殊方格，然后对该部分递归调用覆盖算法，否则该部分有特殊方格，则直接递归调用覆盖算法。

2演示程序设计

采用C/C++语言来描述算法，所以本文课件采用VisualC++6.0进行开发，一方面能在课件源代码中体现算法本身，另一方面能直接演示算法的执行情况，使学生在掌握算法本身之外，学习一种程序实现方法，提高学生的学习兴趣，增进学习效果。在VisualC++中建立一对话框应用程序Demo，在CdemoDlg类中添加以下成员变量和函数。

voidDrawTable();//根据输入的k值画棋盘

voidDrawBack();//清空棋盘上原有的图像

voidDrawBoard(intx，inty，intw，intc);//画棋盘的x行，y列一个方格，w是宽度，c是颜色

inttile;//当前所用的方块

int**board;//指向棋盘的指针

intdw;//棋盘每一格的宽度

voidchessBoard(inttr，inttc，intdr，intdc，intsize);//棋盘覆盖算法

在对话框中添加EditBox控件，并关联一int型变量m_k用于接收输入的k值，在演示程序中根据输入的k值计算棋盘中每一个方格的大小。在一般情况下，窗体的大小不变，当k越大时，棋盘的方格越多，这时每个方格的尺寸越小，反之越大。如整个棋盘的尺寸为512，则方格尺寸dw=512/2k。在算法演示中采用图形表示，给每个L型骨牌填充不同的颜色，在程序中把tile变量转换成颜色，画一个方格的函数定义如下：

voidCDemoDlg::DrawBoard(intx，inty，intw，intc)

{

CClientDCdc(this);

COLORREFcolor;

color=RGB(c*c%256，c*c*c%256，c*c*c*c%256);//把c值转换成颜色

CBrushbr(color);//定义一绘图画刷

CRectr;//定义一矩形区域，用来表示棋盘的一个方格

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秒，并绘制出当前覆盖的方格，具体参见以下源程序。

voidCDemoDlg::chessBoard(inttr，inttc，intdr，intdc，intsize)

{

if(size==1)//如果问题的规模足够小，则返回

{

return;

Sleep(500);//延迟500毫秒

intt=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结束语

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

参考文献

[1]王晓东.计算机算法设计与分析[M].北京:电子工业出版社，2004

[2]求是科技.VisualC++6.0程序设计与开发技术大全[M].北京:人民邮电出版社，2004