導(dǎo)語(yǔ)：算法演示課件制作研究論文一文來(lái)源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要為了更加清楚了解遞歸和分治算法的執(zhí)行情況，使用該算法具體分析了棋盤覆蓋問(wèn)題，然后利用VisualC++制作演示課件直觀顯示算法的執(zhí)行步驟，在實(shí)際教學(xué)中取得了很好的效果。

關(guān)鍵詞遞歸，分治，VisualC++，課件

0引言

算法與計(jì)算理論是計(jì)算機(jī)程序設(shè)計(jì)領(lǐng)域的靈魂，是發(fā)揮程序設(shè)計(jì)者嚴(yán)謹(jǐn)，敏銳思維的有效工具。任何的程序設(shè)計(jì)語(yǔ)言都試圖將之發(fā)揮得淋漓盡致，它無(wú)可厚非的作為計(jì)算機(jī)專業(yè)最重要基礎(chǔ)類核心課程。但對(duì)于初次接觸算法設(shè)計(jì)的學(xué)習(xí)者而言，他們往往不清楚算法的具體執(zhí)行情況，進(jìn)而自己設(shè)計(jì)算法也變得相當(dāng)困難。如：在學(xué)習(xí)遞歸和分治算法的時(shí)候，一些人只知道遞歸算法的執(zhí)行有壓棧和出棧的兩個(gè)過(guò)程，對(duì)于程序究竟怎么執(zhí)行，到最后還是一頭霧水，而其他的動(dòng)態(tài)規(guī)劃算法、回溯算法、分支限界算法等則更難掌握。針對(duì)這一情況，本人在教學(xué)中設(shè)計(jì)了一些演示程序來(lái)直觀反應(yīng)程序的執(zhí)行順序，并取得了較好的效果。以下就棋盤覆蓋算法演示程序?yàn)槔榻B算法課件的制作。

1棋盤覆蓋問(wèn)題分析

圖1一種特殊棋盤

如果規(guī)模已經(jīng)足夠小，則覆蓋完畢；分割棋盤為4部分；

在一個(gè)2k×2k個(gè)方格組成的棋盤中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤，如圖1所示。在棋盤覆蓋問(wèn)題中，要用圖2所示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。該問(wèn)題可以采用分治法來(lái)求解，分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。

當(dāng)k>0時(shí)，將2k×2k棋盤分割為4個(gè)2k-1×2k-1子棋盤，特殊方格必位于4個(gè)較小子棋盤之一中，其余3個(gè)子棋盤中無(wú)特殊方格。為了將這3個(gè)無(wú)特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處，從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問(wèn)題。遞歸地使用這種分割，直至棋盤簡(jiǎn)化為棋盤1×1。算法框架如下：

圖24種不同形態(tài)的L型骨牌覆蓋算法（問(wèn)題規(guī)模）

如果規(guī)模已經(jīng)足夠小，則覆蓋完畢，分割棋盤為4部分。對(duì)于每一部分，先看該部分有無(wú)特殊方格，如果沒有特殊方格，則先在該部分與其他三部分的交匯處覆蓋一特殊方格，然后對(duì)該部分遞歸調(diào)用覆蓋算法，否則該部分有特殊方格，則直接遞歸調(diào)用覆蓋算法。

2演示程序設(shè)計(jì)

采用C/C++語(yǔ)言來(lái)描述算法，所以本文課件采用VisualC++6.0進(jìn)行開發(fā)，一方面能在課件源代碼中體現(xiàn)算法本身，另一方面能直接演示算法的執(zhí)行情況，使學(xué)生在掌握算法本身之外，學(xué)習(xí)一種程序?qū)崿F(xiàn)方法，提高學(xué)生的學(xué)習(xí)興趣，增進(jìn)學(xué)習(xí)效果。在VisualC++中建立一對(duì)話框應(yīng)用程序Demo，在CdemoDlg類中添加以下成員變量和函數(shù)。

voidDrawTable();//根據(jù)輸入的k值畫棋盤

voidDrawBack();//清空棋盤上原有的圖像

voidDrawBoard(intx，inty，intw，intc);//畫棋盤的x行，y列一個(gè)方格，w是寬度，c是顏色

inttile;//當(dāng)前所用的方塊

int**board;//指向棋盤的指針

intdw;//棋盤每一格的寬度

voidchessBoard(inttr，inttc，intdr，intdc，intsize);//棋盤覆蓋算法

在對(duì)話框中添加EditBox控件，并關(guān)聯(lián)一int型變量m_k用于接收輸入的k值，在演示程序中根據(jù)輸入的k值計(jì)算棋盤中每一個(gè)方格的大小。在一般情況下，窗體的大小不變，當(dāng)k越大時(shí)，棋盤的方格越多，這時(shí)每個(gè)方格的尺寸越小，反之越大。如整個(gè)棋盤的尺寸為512，則方格尺寸dw=512/2k。在算法演示中采用圖形表示，給每個(gè)L型骨牌填充不同的顏色，在程序中把tile變量轉(zhuǎn)換成顏色，畫一個(gè)方格的函數(shù)定義如下：

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

{

CClientDCdc(this);

COLORREFcolor;

color=RGB(c*c%256，c*c*c%256，c*c*c*c%256);//把c值轉(zhuǎn)換成顏色

CBrushbr(color);//定義一繪圖畫刷

CRectr;//定義一矩形區(qū)域，用來(lái)表示棋盤的一個(gè)方格

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);//填充繪圖區(qū)域

}

在棋盤覆蓋程序中，每次覆蓋一個(gè)方格，為了便于清楚看到程序覆蓋棋盤的順序，每次覆蓋后延遲0.5秒，并繪制出當(dāng)前覆蓋的方格，具體參見以下源程序。

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

{

if(size==1)//如果問(wèn)題的規(guī)模足夠小，則返回

{

return;

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

intt=tile++，//L型骨牌號(hào)

s=size/2;//分割棋盤

//覆蓋左上角子棋盤

if(dr<tr+s&&dc<tc+s)

chessBoard(tr，tc，dr，dc，s);

else

{//此棋盤中無(wú)特殊方格

//用t號(hào)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

{//此棋盤中無(wú)特殊方格

//用t號(hào)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號(hào)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號(hào)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棋盤覆蓋結(jié)果

執(zhí)行以上程序得到棋盤的動(dòng)態(tài)覆蓋次序，該次序就是遞歸函數(shù)的執(zhí)行情況，圖3是當(dāng)k=3，特殊方格位于第三行第二列時(shí)，程序運(yùn)行的最后結(jié)果，由于該課件能產(chǎn)生動(dòng)態(tài)繪制效果，增加了學(xué)生的學(xué)習(xí)興趣，使學(xué)生更加清楚的了解分治法的具體執(zhí)行情況。

3結(jié)束語(yǔ)

本文利用VisualC++制作了棋盤覆蓋算法的演示課件，相對(duì)于其他的工具實(shí)現(xiàn)的課件而言，該課件不僅包含了算法本身，而且采用動(dòng)態(tài)繪制圖案的方式說(shuō)明算法的執(zhí)行情況，增進(jìn)了教學(xué)效果。該課件的制作過(guò)程實(shí)際上也是算法的實(shí)際運(yùn)用過(guò)程，在算法課程教學(xué)中，制作這類課件不僅會(huì)使學(xué)生了解算法的執(zhí)行情況，而且課件本身就是對(duì)算法的一種深化和運(yùn)用，課件的制作過(guò)程也同樣具有很好的學(xué)習(xí)價(jià)值。

參考文獻(xiàn)

[1]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京:電子工業(yè)出版社，2004

[2]求是科技.VisualC++6.0程序設(shè)計(jì)與開發(fā)技術(shù)大全[M].北京:人民郵電出版社，2004