基于計(jì)算思維能力培養(yǎng)的算法與程序設(shè)計(jì)教學(xué)策略

基于計(jì)算思維能力培養(yǎng)的算法與程序設(shè)計(jì)教學(xué)策略在當(dāng)今的信息社會中，培養(yǎng)和提高信息素養(yǎng)是對初中生的基本要求，而信息素養(yǎng)表現(xiàn)為個(gè)人對信息工具的應(yīng)用以及處理信息和解決問題的能力，計(jì)算思維則包含了信息工具的使用和解決問題能力，所以計(jì)算思維的培養(yǎng)是初中生信息素養(yǎng)的一種體現(xiàn)?！窭盟惴ê蛨D形，落實(shí)學(xué)生的計(jì)算思維1.借助流程圖，直觀表達(dá)解決問題思路流程圖是使用圖形表示算法思路的一種直觀方法。例如，面對求兩個(gè)正整數(shù)m、n的最大公約數(shù)的問題，學(xué)生可以采用輾轉(zhuǎn)相除法即歐幾里德算法：對于任意兩個(gè)自然數(shù)m和n，用m、n、r分別表示被除數(shù)、除數(shù)、余數(shù)，那么m和n的最大公約數(shù)等于n和r的最大公約數(shù)。即第一步求m除以n的余數(shù)r;第二步若r不等于0，執(zhí)行第三步，若r等于0，則n為最大公約數(shù)，算法結(jié)束;第三步將n的值賦給m，將r的值賦給n，再求m除以n的余數(shù)r;第四步轉(zhuǎn)到第二步。而利用流程圖（如圖1），能減少繁雜的文字，更加明確問題關(guān)鍵，提取問題特征，快速直觀地表達(dá)學(xué)生解決問題的思路，最后借助編寫程序解決問題。2.培養(yǎng)學(xué)生算法思想，高效解決問題計(jì)算思維是人的思維，是人求解問題的一條途徑。針對需要大量計(jì)算的問題，引導(dǎo)學(xué)生在提出解決問題的方法后，理解計(jì)算思維涵蓋的計(jì)算概念和方法，落實(shí)學(xué)生的計(jì)算思維。例如，遞推問題“Fibonacci數(shù)列”：有雌雄一對兔子，假定過兩個(gè)月便可繁殖雌雄各一的一對小兔子，過n個(gè)月后共有多少對兔子？“兔子繁殖問題”看似復(fù)雜，其實(shí)只需要清楚第x-2個(gè)月的所有兔子到第x個(gè)月都有繁殖能力就能解決問題。設(shè)滿x個(gè)月共有兔子F（x）對，其中當(dāng)月新生的兔子數(shù)目為N（x）對。第x-1個(gè)月留下的兔子數(shù)目設(shè)為F（x-1）對，則F（x）=N（x）+F（x-1），N（x）=F（x-2），那么F（x）=F（x-1）+F（x-2）。所以，由上面的遞推關(guān)系可依次得到F（2）=F（1）+F（0）=1，F(xiàn)（3）=F（2）+F（1）=2，……。當(dāng)n=90時(shí)，F(xiàn)（n）已經(jīng)達(dá)到2880067194370816120。這樣的問題如果沒有計(jì)算機(jī)很難得知結(jié)果，所以，在培養(yǎng)學(xué)生算法思想的過程中，借助計(jì)算機(jī)有效落實(shí)計(jì)算思維，能夠解決很多計(jì)算規(guī)模超大的問題。3.使用思維導(dǎo)圖，概括解決問題的算法學(xué)生細(xì)化提出的問題解決方法，通過思維導(dǎo)圖的使用（如下頁圖2），呈現(xiàn)出細(xì)化的方案，這種方法往往應(yīng)用于難度系數(shù)較大的復(fù)雜題目。例如，設(shè)計(jì)五子棋的程序，其功能包括繪制棋盤、交替出現(xiàn)黑白棋、移動棋子、判斷勝負(fù)等。學(xué)生利用思維導(dǎo)圖能概括其學(xué)習(xí)的知識要點(diǎn)，清晰明了地組建知識網(wǎng)絡(luò)，訓(xùn)練計(jì)算思維。●借助多種學(xué)習(xí)技巧，強(qiáng)化學(xué)生的計(jì)算思維1.一題多解，多面思考一題多解是指針對一道習(xí)題，能從不同角度去思考問題，尋找到不同的解題方法，并對這些不同解題方法進(jìn)行總結(jié)和歸納。例題1：觀察下面的數(shù)字金字塔（如圖3）。寫一個(gè)程序查找從最高點(diǎn)到底部任意處結(jié)束的路徑，使路徑經(jīng)過數(shù)字的和最大。每一步都可以從當(dāng)前點(diǎn)走到左下方的點(diǎn)，也可以到達(dá)右下方的點(diǎn)。在上面的樣例中，從13到8到26到15到24的路徑產(chǎn)生了最大的和86。輸入：第一行包含R（1≤R≤1000），表示行的數(shù)目。后面每行為這個(gè)數(shù)字金字塔特定行包含的整數(shù)。所有的被供應(yīng)的整數(shù)是非負(fù)的且不大于100。輸出：單獨(dú)的一行，包含可能得到的最大的和。5//數(shù)塔層數(shù)11

812

7

266

14

15

812

7

13

24

11樣例輸出：86。①方法一：搜索。問題要求從最高點(diǎn)按照規(guī)則走到最低點(diǎn)的路徑的最大權(quán)值和，路徑起點(diǎn)終點(diǎn)固定，走法規(guī)則明確，可以考慮用搜索來解決。定義遞歸函數(shù)voidDfs（intx，inty，intCurr），其中x，y表示當(dāng)前已從（1，1）走到（x，y），目前已走路徑上的權(quán)值和為Curr。當(dāng)x=N時(shí)，如果Curr比Ans大，則把Ans更新為Curr;否則向下一行兩個(gè)位置行走，即遞歸執(zhí)行Dfs（x+1，y，Curr+A[x+1][y]）和Dfs（x+1，y+1，Curr+A[x+1][y+1]）（如下頁圖4）。該方法實(shí)際上是把所有路徑都走了一遍，由于每一條路徑都是由N-1步組成，每一步有“左”“右”兩種選擇，因此路徑總數(shù)為2N-1，所以該方法的時(shí)間復(fù)雜度為O（2N-1），超時(shí)。②方法二：記憶化搜索。方法一之所以會超時(shí)，是因?yàn)檫M(jìn)行了重復(fù)搜索。記憶化搜索需要對方法一中的搜索進(jìn)行改裝，需要記錄從一個(gè)點(diǎn)開始到終點(diǎn)的路徑的最大權(quán)值和，因此重新定義遞歸函數(shù)Dfs。定義Dfs（x，y）表示從（x，y）出發(fā)到終點(diǎn)的路徑的最大權(quán)值和，答案就是Dfs（1，1）。在計(jì)算Dfs（x，y）時(shí)考慮第一步是向左還是向右，筆者把所有路徑分成兩大類：第一步向左、第一步向右。為避免重復(fù)搜索，筆者開設(shè)全局?jǐn)?shù)組F[x][y]記錄從（x，y）出發(fā)到終點(diǎn)路徑的最大權(quán)值和，一開始全部初始化為-1，表示未被計(jì)算過。在計(jì)算Dfs（x，y）時(shí)，首先查詢F[x][y]，如果F[x][y]不等于-1，說明Dfs（x，y）之前已經(jīng)被計(jì)算過，直接返回F[x][y]即可，否則計(jì)算出Dfs（x，y）的值并存儲在F[x][y]中（如下頁圖5）。由于F[x][y]對每個(gè)合法的（x，y）都只計(jì)算過一次，而且計(jì)算是在O（1）內(nèi)完成的，因此時(shí)間復(fù)雜度為O（N2），可以通過本題。③方法三：動態(tài)規(guī)劃（逆推法）。動態(tài)規(guī)劃求解問題的過程歸納為：自頂向下的分析，自底向上計(jì)算。其基本方法是：劃分階段——按三角形的行劃分階段，若有n行，則有n-1個(gè)階段。圖形轉(zhuǎn)化：直角三角形，便于搜索——向下、向右。用三維數(shù)組表示數(shù)塔：a[x][y][1]表示行、列及結(jié)點(diǎn)本身數(shù)據(jù)，a[x][y][2]能夠取得最大值，a[x][y][3]表示前進(jìn)的方向——0向下，1向右（如下頁圖6）。2.一題多變，發(fā)散思維一題多變，是指通過對一道習(xí)題，改變題目中的數(shù)據(jù)、所求的問題或題目中的條件，從而得到新的題目。一題多變的解題思路有利于學(xué)生思維的發(fā)散，并且能夠使學(xué)生更加熟練地掌握多種解題思路和方法。例題2：利用for循環(huán)，計(jì)算輸出1+2+…+100的和。例題3：利用for循環(huán)，分別計(jì)算1～100中奇數(shù)的和、偶數(shù)的和。例題4：利用for循環(huán)計(jì)算n！=1*2*3…*n的值。通過上述例題，可以讓學(xué)生更好地理解和掌握這一題型。在學(xué)習(xí)過程中，學(xué)生運(yùn)用一題多變的解題思路進(jìn)行學(xué)習(xí)，從簡單的題目入手，進(jìn)行深入分析和研究。3.一題多思，把握本質(zhì)一題多思，是指在“一題多變和一題多解”的基礎(chǔ)上，面對同一種類型的題目，把握題目本質(zhì)，從而快速解決問題。一題多思有利于學(xué)生思維的高度概括，并且能夠更加有效地強(qiáng)化學(xué)生的計(jì)算思維。例題5：成績排序。給出班里某門課程的成績單，請你按成績從高到低對成績單排序輸出，如果有相同的分?jǐn)?shù)，則名字字典序小的在前。通過上述例題，可以讓學(xué)生將算法思想從書本問題應(yīng)用到實(shí)際生活問題的解決。●依托翻轉(zhuǎn)課堂教學(xué)實(shí)踐，滲透學(xué)生的計(jì)算思維算法與程序設(shè)計(jì)教學(xué)的目的是培養(yǎng)學(xué)生的解決問題和計(jì)算思維能力。根據(jù)此教學(xué)目標(biāo)，依托翻轉(zhuǎn)課堂的教學(xué)形式，筆者在輔導(dǎo)學(xué)生的過程中設(shè)計(jì)了翻轉(zhuǎn)課堂教學(xué)的三個(gè)基礎(chǔ)環(huán)節(jié)，滲透計(jì)算思維。下面，以“結(jié)構(gòu)體”教學(xué)為例談?wù)劸唧w過程。1.課前推送信息，自主學(xué)習(xí)教師根據(jù)知識點(diǎn)的難易程度，制作短小精悍的教學(xué)視頻以及設(shè)計(jì)針對性的問題，并將其推送給學(xué)生，讓學(xué)生進(jìn)行提前學(xué)習(xí)，引導(dǎo)學(xué)生結(jié)合教學(xué)視頻進(jìn)行思考和解決，加強(qiáng)學(xué)生的自主學(xué)習(xí)能力。例題7：成績統(tǒng)計(jì)。輸入N個(gè)學(xué)生的姓名和語文、數(shù)學(xué)的得分，按總分從高到低輸出，分?jǐn)?shù)相同的按輸入先后輸出。輸入格式：第一行有一個(gè)整數(shù)N（N≤100），下面有N行，每行一個(gè)姓名，兩個(gè)整數(shù)。姓名由不超過10個(gè)的小寫字母組成，整數(shù)范圍為0～100。輸出格式：總分排序后的名單，共N行，每行格式——姓名

語文

數(shù)學(xué)

總分。針對習(xí)題樣例，設(shè)計(jì)了層層遞進(jìn)的針對性的問題（如表1）。2.課堂內(nèi)化知識，深度學(xué)習(xí)在課堂中，教師需要結(jié)合課前的問題，通過講授和演示、問題驅(qū)動教學(xué)方法促使學(xué)生深度學(xué)習(xí)，內(nèi)化知識，完成教師的課堂教學(xué)目標(biāo)和任務(wù)。通過小組討論的教學(xué)方法，學(xué)生碰撞出對知識點(diǎn)更多的疑難問題，然后教師在課堂中進(jìn)行解答和梳理，加強(qiáng)學(xué)生的深度