信息學課程教學中如何開展科學探究教育

宋新波　陳智敏　黃細光

全國青少年信息學奧林匹克競賽（簡稱信息學競賽）是培養高質量人才的重要途徑，但目前絕大多數教師在帶領學生準備參賽的過程中只關注知識、解題方法技巧的傳授，忽視了學生思維及探究能力的培養與拓展。因此，本研究以數論函數中莫比烏斯反演問題的教學實施為例，探討如何在信息學課程中通過引導學生分析問題、發現問題、猜想假設、探究驗證、歸納運用，進而改進算法和程序以解決問題這一教學模式，開展科學探究教育，深化學生計算思維等科學思維，同時形成科學穩定的知識邏輯結構。

本次專題課的學生為高一年級的信息學競賽生，他們從小學五年級開始學習信息學，對編寫程序解決具體問題表現出濃厚的興趣，具有相當強的邏輯推理思維能力，能夠擺脫具體事物的限制，運用概念，提出假設，并檢驗假設來進行抽象邏輯思維。主要教學目標為：在科學探究的過程中發現并證明莫比烏斯反演定理，進而基于實際問題需求對莫比烏斯反演進行靈活應用，最終確定解題步驟，并獨立編寫程序以解決問題，深化科學思維。

● 呈現題目，引導學生分析發現問題

課前呈現題目的描述、輸入輸出格式要求、輸入輸出樣例及數據范圍如下。

數據范圍：

20%的數據滿足：1≤T≤100，1≤n≤100，1≤m≤100，1≤k≤100

50%的數據滿足：1≤T≤1000，1≤n≤1000，1≤m≤1000，1≤k≤1000

70%的數據滿足：1≤T≤1000，1≤n≤10000，1≤m≤10000，1≤k≤10000

100%的數據滿足：1≤T≤50000，1≤n≤50000，1≤m≤50000，1≤k≤50000

時間限制：1秒。

信息學課程中經常需要學生針對問題尋找數理規律，擺脫思維慣性，嘗試各種組合，創新算法去求解。通過對問題的需求情況及已知條件進行詳細分析，學生們很快都提出了方法1：枚舉1到n中的每一個數x，再枚舉1到m中的每一個數y，判斷x和y的最大公約數是不是等于k。教師引導學生計算出該算法的時間復雜度為，其中lgn是用輾轉相除法計算gcd（x，y）的時間復雜度，方法1可以在1秒時間限制內通過20%的數據。

而部分學生則對方法1進行了優化得出方法2：因為gcd（x，y）=k，則令x=k*x'，y=k*y'，推出1≤k*x'≤n，1≤k*y'≤m，從而得出1≤x'≤n/k，1≤y'≤m/k進而分別枚舉x'和y'，判斷x'和y'的最大公約數是否等于1。方法2的時間復雜度為。當k較大時有明顯的優化效果，但當k=1時跟方法1在效率上沒有任何改進。

怎么改進算法才能在時間限制范圍內通過更多的數據？疑問是激發學生思維的源泉，設立數據范圍這一障礙激發學生疑問，以疑問引發思考。由于學生的基礎較好，教師給予了學生更多自主思考的時間，探討如何解決原有算法超時的問題。最終，有少數學生能夠在上述算法的基礎上進一步優化算法，得到方法3：用f（x）表示1到m/k中與x互質的數的個數，則答案為x取1到n/k范圍內的f（x）之和，利用容斥原理來計算f（x），時間復雜度為O（2g（x））（其中，g（x）為x質因子的個數），方法3能夠通過50%的數據。

● 追問點撥，鼓勵學生大膽猜想假設

如何進一步改進算法才能通過更多的數據？追問可以加快思維節奏，促成學習發生。聚焦于問題的解決，通過進一步的討論與交流，個別學生想出方法4：用f（k）表示1≤x≤n，1≤y≤m且x與y的最大公約數為k的數對（x，y）個數，g（k）表示1≤x≤N，1≤y≤M且k|gcd（x，y）的數對（x，y）個數，其中“|”是整除符號，表示k整除gcd（x，y）。則有，又有g（k）=（n/k）*（m/k），這時，問題轉為如何利用遞推關系反過來計算出f（k）。

方法4相對方法3雖然效率上沒有得到本質的提升，但卻成功地把原問題推導出了莫比烏斯反演的原型一，即已知f（n）和g（n）是定義在正整數集合上的兩個函數，并滿足，且g（k）容易求解，要求利用g函數來計算f（k）的值。

現在要解決的問題是：輸入n，輸出f（1），f（2），...，f（n）用g函數表示的形式。教師鼓勵學生學以致用，用編寫程序來解決。首先，不難發現表示f（k）的g函數的參數都是k的倍數，這個可以用數學歸納法來證明。

證明過程具體如下：

（1）當k=n時，f（n）=g（n）成立。

（2）設當k>X時都成立，則觀察，根據假設可知f（X*d）用g函數表示形式中的每一個g函數的參數都是X*d的倍數，那固然也是X的倍數。因此，f（X）的g函數表示形式中每一個g函數的參數也是X的倍數，即k=X也成立。

（3）綜上，結論得證。

引導學生利用此性質編寫程序。有學生不到二十分鐘編寫出以下程序（具體程序代碼略）。

該程序可以測試較大數據，觀察較大數據時的規律。教師引導學生以輸入n=10為例，程序輸出結果如下：

f（1）=g（1）-g（2）-g（3）-g（5）+g（6）-g（7）+g（10）

f（2）=g（2）-g（4）-g（6）-g（10）

f（3）=g（3）-g（6）-g（9）

f（4）=g（4）-g（8）

f（5）=g（5）-g（10）

f（6）=g（6）

f（7）=g（7）

f（8）=g（8）

f（9）=g（9）

f（10）=g（10）

教師引導學生測試較大數據并對輸出結果進行觀察、討論及分析，鼓勵學生大膽猜想f（k）的計算公式。這種猜想既調動了學生的學習興趣，又培養了學生的邏輯思維、發散思維和創新思維。學生基本都能夠發現，f（k）也是用k在不超過n范圍內的所有倍數作為參數所對應的g的函數值進行計算，而且還發現有的g函數值的系數是1，有的為-1，有的則為0。學生初步作出猜想假設： 。

在學生提出的猜想不完整時，教師適時點撥學生，學生認識到“？”部分不是一個定值，而是一個函數，應該跟這里的k和d有關，對輸出結果進行再次觀察和對比分析，最終學生發現“？”部分與k沒有關系，而是跟d有關的某個函數值。因此對結論進行二次猜想：，其中是跟d有關的函數。

通過測試大數據發現的值只有1、-1、0三種，接下來，教師引導學生編寫程序把取這三種值對應的d列舉出來觀察規律。有學生在此前猜想程序的基礎上稍作改動。

學生在教師的引導下發現了不少關于的規律，現僅歸納跟取值有關的規律：

（1）當d=1的時候，=1;

（2）當d=p1*p2*...pk，其中pi（1≤i≤k）為互異素數，則=（-1）k;

（3）其余情況則=0。

至此，猜想完成。即根據，猜想出，其中定義如上。

● 基于猜想，要求學生嚴謹探究驗證

編程教育需要引導學生經歷探求真理、發現奧秘的過程。通過分析、抽象、概括、猜想出f（k）的計算公式后，接下來需要進一步證明猜想的正確性，這才是完整的科學探究過程。

已知，證明成立。

教師引導學生注意等式右邊的g（k*d）可以根據已知表示成f的形式，左右兩邊就都是f的形式，以此為突破口進行證明。

把已知的結論帶入等式右邊得：

上面式子的寫法可以看出是以為主體的，如n=6，k=1時，上面的式子展開后如圖1所示。

這樣的寫法很難跟左邊f（k）去進行比較，需要進行更換f（）為主體，把上式等價轉換為如圖2所示的樣子。

這樣，就可以很方便地去比較左右兩邊對于f（）的系數是否相等。接下來教師引導學生對右式進行主體外移的等價變換處理。

令T=d*d1，則有，對于同樣的T，觀察f（k*T）的系數，只要滿足d|T，都要累加進f（k*T）的系數中。有學生在教師的啟發下，寫出如圖3所示的等價形式。

要證明就轉化為證明：

當T=1時，，成立。

當T>1時，設，因為，另外，不需要考慮=0的情況，所以只需要考慮yi=0或1的情況。設d的質因子分解中含有r個質因子，T共有t個質因子，則這樣的d有個，，含r個質因子的d的之和等于，r可以從0取到k，累積即可。所以T>1時，，利用二項式定理，則有。得證！

以上結論就是著名的莫比烏斯反演。整個過程各環節環環相扣，周密嚴謹，展現了完整的從大膽猜想到嚴謹證明的科學探究全過程。信息學競賽的研究性學習課程階段經常會出現花大量時間解決問題的情況，而讓學生經歷猜想驗證的過程，不僅可以解決他們在學習中所產生的困惑，更有利于他們克服困難的意志以及對新知識點迎難而上，的科學品質的養成，使其樹立學好信息學的信心。

● 歸納運用，引導學生編程解決問題

教師引導學生回到最初所提出的問題：，g（k）=，如何利用g（k）反過來計算出f（k）。基于莫比烏斯反演公式，學生就g（k）進行式子變形，得到。

針對這一結果，部分學生最終利用線性篩法在O（n）時間復雜度內初始化出所有的u（d），再從1到n/k范圍內枚舉d計算f（k），單次詢問的時間復雜度為O（n/k），可以得到70分。少數學生則是進一步對（n/（k*d））*（m/（k*d））進行分塊處理，這樣單次詢問的時間復雜度則降低為，能夠得到100分。

上述過程中，每位學生最終設計出的算法都集中體現了各自特有的思維方式，但是有的學生采用的算法處理效率高、速度快。為了讓每位學生都能夠恰當地利用所學的算法進行程序設計，快速高效地解決實際問題，教師需要組織學生進行討論和交流，讓每位學生都發表自己的看法和建議，讓每位學生在互相討論和交流的過程中學習到別人的長處，發現自己的不足。最終，學生形成了清晰的問題解決思路，經過思考、改進算法和編寫、調試程序，結合相互之間的交流與教師的個別指導，絕大多數學生都能夠編寫出完整的程序以解決課前所提出的問題。

“教”只是實現“學”的一種服務手段，學生的“學”才是教學的出發點和歸宿。整個教學實施的過程，沒有滔滔不絕的教師講解，也沒有氣氛熱烈的小組活動，更多的是教師嚴密理性的引導，以及對學生的思考和實踐的激活，最終幫助學生深化科學思維，培養科學探究能力。