分治算法求解棋盤覆蓋問題互動教學過程

1、分治算法求解棋盤覆蓋問題互動教學過程 摘要：針對算法設計與分析課程難度較大、對學生編程能力要求較高的現(xiàn)狀，通過對棋盤覆蓋問題的分治算法求解過程進行互動教學設計，引導學生進行問題理解、算法設計、算法實現(xiàn)。特別是在算法實現(xiàn)環(huán)節(jié)，一行一行地動態(tài)展示程序的編寫過程，同時充分考慮學生現(xiàn)有的編程基礎，采用程序填空的形式降低學生編程難度，有助于消除學生的畏難心理，有效提高了學生的學習興趣，同時鍛煉了學生的計算思維 關鍵詞：棋盤覆蓋；遞歸；分治；互動教學 中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2016）35-0146-02 Interactive Teaching Proced

2、ure of the “Divide and Conquer” Algorithm with the Problem of “Chess Board” LV Lan-lan， LI Ming （Department of Software Engineering， College of Electronic and Information Engineering， Hunan University of Science and Engineering， Yongzhou 425100， China） Abstract：The course of algorithm design and ana

3、lysis is difficult to those students with poor programming ability. This paper describes the interactive teaching design of the “divide and conquer” algorithm with the problem of “chess board”， which includes directing students to understand the problem， design and implement the algorithm. Especiall

4、y during the phase of algorithm implementation， we show the procedure of programming to students line by line. At the same time， we use “program completion” to make programming easy for students. It is help to eliminate students fear， inspire their interest and train their computational thinking. Ke

5、y words： chess board； recursion； divide and conquer； interactive teaching 1 引言 惴難芯懇丫被公認為是計算機科學的基石，算法設計與分析課程也是我校軟件工程專業(yè)的一門專業(yè)核心課程，學習算法的重要性毋庸置疑。但算法設計與分析課程具有難度大，對學生編程能力要求高的特點，不少學生望而卻步。在教學過程中我們發(fā)現(xiàn)，雖然大部分學生能正確理解算法的思路，但是卻不能以某種高級程序設計語言實現(xiàn)算法。針對學生這種“眼高手低”的現(xiàn)狀，本文提出將“程序填空”這一程序設計類課程考試中常用的題型，應用到算法設計與分析課程日常教學中，通過實施互動教學

6、降低課程難度、激發(fā)學生興趣。我們以分治法求解棋盤覆蓋問題為例，逐步引導學生完成從算法的思路解析到完整實現(xiàn)的全過程，聚焦從算法到程序的“最后一公里” 2 棋盤覆蓋問題 2.1 問題描述 棋盤覆蓋問題是許多國內教材1-2在闡述分治法時使用的一個經(jīng)典案例，具體描述如下： 在一個個方格組成的棋盤中，若恰有一個方格與其它方格不同，則稱該方格為一特殊方格，稱該棋盤為一特殊棋盤。圖1為k=2時的一個特殊棋盤，其中特殊方格的位置是（1，2），用陰影表示 在棋盤覆蓋問題中，要用圖2中4種不同形態(tài)的L型骨牌覆蓋一個給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋 圖棋盤覆蓋問題的已知條件是

7、在一個的棋盤上有一個特殊方格，因此算法的輸入可以用來表示棋盤的大小，用（dr， dc）來表示特殊方格在棋盤中的位置。棋盤覆蓋問題的輸出結果是一個覆蓋了L形骨牌的棋盤，如何表示三個方格被同一個L形骨牌覆蓋稱為關鍵。學生比較容易想到的方法是使用同一種顏色來填充被同一個L形骨牌覆蓋的三個方格，這是一種形象化的思維方式。為了將數(shù)據(jù)抽象成程序設計語言方便處理的形式，可以從顏色在計算機中的存儲形式（整數(shù)）出發(fā)，引導學生直接使用整數(shù)來填充表示被同一個L形骨牌覆蓋的三個方格。這樣就完成了棋盤覆蓋問題中輸入/輸出數(shù)據(jù)的抽象，并且可以得到函數(shù)的原型：void ChessBoard（int size， int dr

8、， int dc， int *board） 3.3.2 C+實現(xiàn) 根據(jù)3.3.1中的數(shù)據(jù)抽象結果得到函數(shù)原型后，進行算法實現(xiàn)時，還有2個待解決的關鍵問題。第一，如何確定遞歸函數(shù)ChessBoard的停止條件。大部分學生認為是最簡單的情況是當?shù)臅r候，即：的棋盤中有一個特殊方格，此時剩余的3個方格剛好可以用一個L形骨牌來覆蓋。但事實上更簡單的情況是當?shù)臅r候，即：的棋盤中有一個特殊方格，此時根本無需任何覆蓋。因此可以通過提問的方式啟發(fā)學生思考當?shù)臅r候是不是最簡單的情況。第二，在函數(shù)原型void ChessBoard（int size， int dr， int dc， int *board）中，僅有s

9、ize這個參數(shù)并不能確定當前正在處理的是哪個子棋盤。雖然教材上給出的函數(shù)原型是void ChessBoard（int size， int tr， int tc， int dr， int dc， int *board），使用了每個子棋盤的左上角方格的位置（tr， tc）來標識當前所處理的子棋盤。但是要想到這一點其實并不容易，這是算法實現(xiàn)時的一個難點。 目前，針對該難點我們在教學中采用的處理步驟是：（1）根據(jù)函數(shù)原型void ChessBoard（int size， int x， int y， int *board）實現(xiàn)算法，經(jīng)測試程序運行結果不正確。（2）通過輸出每一個L形骨牌覆蓋后的棋盤，指導

10、學生使用單步執(zhí)行的調試方式查找出錯原因。然后，根據(jù)出錯原因在函數(shù)ChessBoard的參數(shù)表中增加標識子棋盤位置的參數(shù)tr和tc。（3）使用更新后的函數(shù)原型void ChessBoard（int size， int tr， int tc， int dr， int dc， int *board）重新實現(xiàn)算法，經(jīng)測試程序運行結果正確。上述教學步驟的執(zhí)行難點在于要求學生具有較強的程序調試能力和程序分析能力，但是相對教材中直接給出更新后的函數(shù)原型及源代碼，上述處理步驟方法對學生來說過渡更自然、更符合學生的從易到難的認知規(guī)律 在第（1）、（3）步中實現(xiàn)算法時，在教學中我們采用了“程序填空”這一程序設計類

11、課程期末考試試卷中常見的題型，來提供盡可能多的提示信息幫助學生完成從算法偽碼到C+程序的過程，消除部分基礎較差學生的畏難心理。下面僅給出當特殊方格位于右下角子棋盤時的“程序填空”范例也能降低編程難度，有助于消除學生的畏難心理，讓學生獲得學習的成就感，有效提高了學生的學習興趣，同時鍛煉了學生的計算思維 5 結論 分治算法采用“分而治之”的策略，將問題分解為規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同。分治策略遞歸地求解這些子問題，然后將各子問題的解合并得到原問題的解。其中的難點在于遞歸求解子問題，遞歸函數(shù)原型的設計成為關鍵，學生學習存在一定的困難。以棋盤覆蓋這一較為形象的問題作為實例進行分析，對分治算法求解該問題的教學過程進行互動設