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

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

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

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

圖1

1.縝密思考，精準分析

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

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

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

2.模擬驗證，形象呈現(xiàn)

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

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

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

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

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

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

●一題多解，培養(yǎng)學生求同存異、探索最優(yōu)的習慣

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

方法一：搜索法

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

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

圖2

方法二：記憶化搜索

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

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

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

綜上得到遞推關系式：

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

●結語

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