算法演示課件制作研究論文

導語：算法演示課件制作研究論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要為了更加清楚了解遞歸和分治算法的執行情況，使用該算法具體分析了棋盤覆蓋問題，然后利用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