分治算法求解棋盤覆蓋問(wèn)題互動(dòng)教學(xué)過(guò)程

1、分治算法求解棋盤覆蓋問(wèn)題互動(dòng)教學(xué)過(guò)程 摘要：針對(duì)算法設(shè)計(jì)與分析課程難度較大、對(duì)學(xué)生編程能力要求較高的現(xiàn)狀，通過(guò)對(duì)棋盤覆蓋問(wèn)題的分治算法求解過(guò)程進(jìn)行互動(dòng)教學(xué)設(shè)計(jì)，引導(dǎo)學(xué)生進(jìn)行問(wèn)題理解、算法設(shè)計(jì)、算法實(shí)現(xiàn)。特別是在算法實(shí)現(xiàn)環(huán)節(jié)，一行一行地動(dòng)態(tài)展示程序的編寫過(guò)程，同時(shí)充分考慮學(xué)生現(xiàn)有的編程基礎(chǔ)，采用程序填空的形式降低學(xué)生編程難度，有助于消除學(xué)生的畏難心理，有效提高了學(xué)生的學(xué)習(xí)興趣，同時(shí)鍛煉了學(xué)生的計(jì)算思維 關(guān)鍵詞：棋盤覆蓋；遞歸；分治；互動(dòng)教學(xué) 中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言 惴難芯懇丫被公認(rèn)為是計(jì)算機(jī)科學(xué)的基石，算法設(shè)計(jì)與分析課程也是我校軟件工程專業(yè)的一門專業(yè)核心課程，學(xué)習(xí)算法的重要性毋庸置疑。但算法設(shè)計(jì)與分析課程具有難度大，對(duì)學(xué)生編程能力要求高的特點(diǎn)，不少學(xué)生望而卻步。在教學(xué)過(guò)程中我們發(fā)現(xiàn)，雖然大部分學(xué)生能正確理解算法的思路，但是卻不能以某種高級(jí)程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)算法。針對(duì)學(xué)生這種“眼高手低”的現(xiàn)狀，本文提出將“程序填空”這一程序設(shè)計(jì)類課程考試中常用的題型，應(yīng)用到算法設(shè)計(jì)與分析課程日常教學(xué)中，通過(guò)實(shí)施互動(dòng)教學(xué)

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

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

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

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

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

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