信息學競賽教學中創造性思維培養的實踐研究
——以“運動坐標”問題為例

熊超 廣東省中山市中山紀念中學

拔尖創新人才的培養是建設創新型國家、實現中華民族偉大復興的基礎性、戰略性工程。本文以“運動坐標”問題為例，介紹如何通過具體活動，發展學生的創造性思維，培養信息學拔尖創新人才。

●慎思熱議，發展學生獨立思考、合作交流的能力

具有創造性思維的學生一定具備較強的獨立思考能力，同時創新型人才也需具備合作交流的能力。在任何問題的解決過程中，既要給學生獨立思考、解決問題的時間，又要組織討論交流，形成多元的問題解決思路。以“運動坐標”問題為例，題目的描述為：某動點在平面直角坐標系第一象限的整點上運動（含第一象限x，y軸上的整點），其運動規律為（x，y）（x＋1，y＋1）或（x，y）（x＋1，y-1）。若該動點從原點出發，經過6步運動到（6，2）點，有多少種不同的軌跡。題目如圖1所示。

圖1

1.縝密思考，精準分析

不管是具體的題目，還是生活中的問題，分析過程都體現了學生思維的縝密程度。在“運動坐標”問題中，動點有兩種運動方式，其中每完成一次運動方式①，動點的橫坐標和縱坐標都會增加1，每完成一次運動方式②，動點的橫坐標增加1，而縱坐標減少1。根據起點到終點坐標的變化，設運動方式①完成了a次，運動方式②完成了b次，動點從（0，0）到（6，2），橫坐標增加了6，縱坐標增加了2。得到以下方程：

解得：a=4，b=2。即從（0，0）運動到（6，2），兩種方式分別完成4次和2次。再結合象限約束，思考4次運動方式①和2次運動方式②有多少種可能。

這道題目對學生來說具有挑戰性，可以讓學生將他們分析問題的思維過程用精練的語言表述出來，從而培養學生既“精”又“準”地思考、分析與表述能力。

2.模擬驗證，形象呈現

對于小數據量的問題，用圖、表等形象化的方式啟發學生的觀察與思考，是一種常用的問題解決方法。針對“運動坐標”問題，教師可組織學生用圖去模擬所有的解，并觀察他們的模擬過程是否有序，是否有疏漏，并對模擬驗證過程中邏輯有序的學生進行表揚。

模擬的過程可以由多名學生各繪一圖，求同存異，也可以一人主講，多人補充。通過以上兩個步驟，學生在問題的思考、分析、討論、交流中，學會獨立思考、合作交流，既能將問題抽象概括，又能將抽象問題具象驗證，創造性思維能力得到提升。

●重構問題，發展學生基于已知探索未知的能力

創新創造不是憑空想象，很多時候是基于已有的知識、現象，去提出新的問題，探索不確定的事物與未知。針對“運動坐標”問題，教師可以和學生一起嘗試將其重構成可以用程序解決、更大數據規模、有時間與空間限制的問題，并進行問題的辨析與解決。

下面是改編問題，時間限制為1秒，空間限制為256M。具體如下：某動點在平面直角坐標系第一象限的整點上運動（含第一象限x，y軸上的整點），其運動規律為（x，y）（x＋1，y＋1）或（x，y）（x＋1，y-1）。給定終點（n，m），若該動點從原點出發，問動點從原點運動到終點，有多少種不同的軌跡？

引導學生開展發散性思考：問題中的數據規模再大一些怎么解決？問題一般化，沒有具體的數字，而是改成n，m等一般性變量，該如何解決？改變題目的某個條件，解決方案要作何變化？通過一系列的追問，引導學生深入思考題目的特點，從不同角度去尋找已知和未知之間的關系，重新構建問題的數學模型，再重新設計算法解決這個數學模型，最后通過程序來實現算法。這極大地鍛煉了學生的思維能力，拓寬了思維的深度和廣度，有利于形成發散性思維的品質，對學生創造性思維能力的培養有很好的效果。

●一題多解，培養學生求同存異、探索最優的習慣

一題多解的思維習慣有助于激發學生的探究主動性與創新意識，在生生互動、師生互動的過程中，在對題目多樣化解決方法的分享交流中，學生逐漸養成了求同存異又追尋“最優解”的習慣。以新題目的解法為例，通過師生交流，形成了搜索法、記憶化搜索、遞推法、類卡特蘭數等多種解法。下面介紹部分解法的關鍵分析。

方法一：搜索法

改編的問題，終點的取值范圍擴大到107這個數量級，用模擬法顯然不可取，但可以把模擬法運用計算思維程序化，用程序來實現。該問題是給定起點（0，0），給定終點（n，m），給定動點運動規則，要求計算運動軌跡的數量，這類問題可以用深度優先搜索或寬度優先搜索來完成。

同樣，可以先計算出兩種運動方式的次數a和b。根據方程a＋b=n和a-b=m得，顯然，當n和m奇偶性不同時，問題無解（這里是重構問題給定條件時的巧妙之處，可以引導學生思考分析）。為了便于理解搜索的原理，可以畫出樣例（6，2）對應的有別于之前模擬運動軌跡的搜索樹（如下頁圖2），由結點和線條組成，展示了動點在執行某種運動方式后的位置變化。其中結點(a，b)表示當前動點位置的橫坐標為a，縱坐標為b，實線代表執行了運動方式①，虛線代表執行了運動方式②。從（0，0）到（6，2）的9種不同運動軌跡都可以在搜索樹中找到。深度優先搜索的程序由于時間復雜度與運動軌跡數成正比，所以實際測試時只得到第一檔數據的20分，對于第二、三檔的數據測試結果顯示超過時間限制。

圖2

方法二：記憶化搜索

方法一的程序之所以超時，原因在于搜索過程中出現了狀態重復調用。分析得出程序慢的原因，就應引導學生思考如何解決該問題。本題可以定義F[i][j]表示從（i，j）到達終點（n，m）的運動軌跡數，也可以換一個方向，表示從（0，0）出發到達（i，j）的運動軌跡數，兩種表示方法都是可行的，這里采用第二種方法。最終計算出F[n][m]，就是問題的答案。

題目中已經保證了n≥m≥0且n，m奇偶性相同，根據方法一中對兩種運動方式數量x，y的計算可知，問題一定有解。其中，當n=m=0時，F[0][0]=1。

當n＞0時，F[n][m]的計算可以利用加法原理來完成，根據最后一步的運動軌跡分為以下兩種情況：第一種情況，最后一步選擇運動方式①，即從（n-1，m-1）運動到（n，m）。經分析，這種情況存在方案的前提是n＋m≥2且m＞0，由于最后一步已確定，該情況的方案數等價于從（0，0）到（n-1，m-1）的方案數，即F[n-1][m-1]。第二種情況，最后一步選擇運動方式②，即從（n-1，m＋1）運動到（n，m）。這種情況存在的前提是n≥m＋2，方案數等價于從（0，0）到（n-1，m＋1）的方案數，即F[n-1][m＋1]。

綜上得到遞推關系式：

可以采用記憶化搜索來實現。首先把數組F初始化為-1，表示所有位置都未曾計算過，在調用遞歸函數dg(x，y)計算F[x][y]時，首先查看F[x][y]是否已經計算過，若已經計算過則直接返回F[x][y]，若未計算過，則按照上面的遞推關系式去計算，計算的結果再存回到F[x][y]處，以便下次需要計算F[x][y]時可以直接返回數組中的值，無需重復計算。這樣一來，每個點最多只會計算一次，時間復雜度為0（nm），大大提升了程序的效率。經過分析，學生編寫的記憶化搜索程序最終獲得了前兩檔數據的50分，對于第三檔數據程序運行超時，且數組也開不到那么大，會超過空間限制。

●結語

拔尖創新人才的培養非一朝一夕之功，創造性思維的培養要落實到每一次的教學實踐中去，讓學生在不斷的分析討論、重構問題、一題多解的迭代中發展創造性思維與創新能力。