算法演示课件制作研究论文

1、算法演示课件制作研究论文 摘要为了更加清楚了解递归和分治算法的执行情况，使用该算法具体分析了棋盘覆盖问题，然后利用VisualC+制作演示课件直观显示算法的执行步骤，在实际教学中取得了很好的效果。 关键词递归，分治，VisualC+，课件 0引言 算法与计算理论是计算机程序设计领域的灵魂，是发挥程序设计者严谨，敏锐思维的有效工具。任何的程序设计语言都试图将之发挥得淋漓尽致，它无可厚非的作为计算机专业最重要基础类核心课程。但对于初次接触算法设计的学习者而言，他们往往不清楚算法的具体执行情况，进而自己设计算法也变得相当困难。如：在学习递归和分治算法的时候，一些人只知道递归算法的执行有压栈和出栈的两

2、个过程，对于程序究竟怎么执行，到最后还是一头雾水，而其他的动态规划算法、回溯算法、分支限界算法等则更难掌握。针对这一情况，本人在教学中设计了一些演示程序来直观反应程序的执行顺序，并取得了较好的效果。以下就棋盘覆盖算法演示程序为例介绍算法课件的制作。 1棋盘覆盖问题分析 图1一种特殊棋盘 如果规模已经足够小，则覆盖完毕；分割棋盘为4部分； 在一个2k2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘，如图1所示。在棋盘覆盖问题中，要用图2所示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。该问题可

3、以采用分治法来求解，分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 当k0时，将2k2k棋盘分割为4个2k-12k-1子棋盘，特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。算法框架如下： 图24种不同形态的L型骨牌覆盖算法（问题规模） 如果规模已经足够小，则覆

4、盖完毕，分割棋盘为4部分。对于每一部分，先看该部分有无特殊方格，如果没有特殊方格，则先在该部分与其他三部分的交汇处覆盖一特殊方格，然后对该部分递归调用覆盖算法，否则该部分有特殊方格，则直接递归调用覆盖算法。 2演示程序设计 采用C/C+语言来描述算法，所以本文课件采用VisualC+6.0进行开发，一方面能在课件源代码中体现算法本身，另一方面能直接演示算法的执行情况，使学生在掌握算法本身之外，学习一种程序实现方法，提高学生的学习兴趣，增进学习效果。在VisualC+中建立一对话框应用程序Demo，在CdemoDlg类中添加以下成员变量和函数。 voidDrawTable();/根据输入的k值画

5、棋盘 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越大时，棋盘的方格越多，这时每个方格

6、的尺寸越小，反之越大。如整个棋盘的尺寸为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

7、.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;/分割棋盘

8、/覆盖左上角子棋盘 if(dr chessBoard(tr，tc，dr，dc，s); else /此棋盘中无特殊方格 /用t号L型骨牌覆盖右下角 boardtr+s-1tc+s-1=t; /覆盖其余方格 chessBoard(tr，tc，tr+s-1，tc+s-1，s); DrawBoard(tr+s-1，tc+s-1，dw，t); /覆盖右上角子棋盘 if(dr=tc+s) /特殊方格在此棋盘中 chessBoard(tr，tc+s，dr，dc，s); else /此棋盘中无特殊方格 /用t号L型骨牌覆盖左下角 boardtr+s-1tc+s=t; /覆盖其余方格 chessBoard(tr

9、，tc+s，tr+s-1，tc+s，s); DrawBoard(tr+s-1，tc+s，dw，t); /覆盖左下角子棋盘 if(dr=tr+s&dc /特殊方格在此棋盘中 chessBoard(tr+s，tc，dr，dc，s); else /用t号L型骨牌覆盖右上角 boardtr+stc+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); els

10、e /用t号L型骨牌覆盖左上角 boardtr+stc+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+制作了棋盘覆盖算法的演示课件，相对于其他的工具实现的课件而言，该课件不仅包含了算法本身，而且采用动态绘制图案的方式说明算法的执行情况，增进了教学效果。该课件的制作过程实际上也是算法的实际运用过程，在算法课程教学中，制作这类课件不仅会使学生了解算法的执行情况，而且课件本身就是对算法的一种深化和运用，课件的制作过程也同样具有很好的