宋新波　陳智敏　黃細(xì)光

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

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

● 呈現(xiàn)題目，引導(dǎo)學(xué)生分析發(fā)現(xiàn)問題

課前呈現(xiàn)題目的描述、輸入輸出格式要求、輸入輸出樣例及數(shù)據(jù)范圍如下。

數(shù)據(jù)范圍：

20%的數(shù)據(jù)滿足：1≤T≤100，1≤n≤100，1≤m≤100，1≤k≤100

50%的數(shù)據(jù)滿足：1≤T≤1000，1≤n≤1000，1≤m≤1000，1≤k≤1000

70%的數(shù)據(jù)滿足：1≤T≤1000，1≤n≤10000，1≤m≤10000，1≤k≤10000

100%的數(shù)據(jù)滿足：1≤T≤50000，1≤n≤50000，1≤m≤50000，1≤k≤50000

時(shí)間限制：1秒。

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

而部分學(xué)生則對方法1進(jìn)行了優(yōu)化得出方法2：因?yàn)間cd（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進(jìn)而分別枚舉x'和y'，判斷x'和y'的最大公約數(shù)是否等于1。方法2的時(shí)間復(fù)雜度為。當(dāng)k較大時(shí)有明顯的優(yōu)化效果，但當(dāng)k=1時(shí)跟方法1在效率上沒有任何改進(jìn)。

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

● 追問點(diǎn)撥，鼓勵(lì)學(xué)生大膽猜想假設(shè)

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

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

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

證明過程具體如下：

（1）當(dāng)k=n時(shí)，f（n）=g（n）成立。

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

（3）綜上，結(jié)論得證。

引導(dǎo)學(xué)生利用此性質(zhì)編寫程序。有學(xué)生不到二十分鐘編寫出以下程序（具體程序代碼略）。

該程序可以測試較大數(shù)據(jù)，觀察較大數(shù)據(jù)時(shí)的規(guī)律。教師引導(dǎo)學(xué)生以輸入n=10為例，程序輸出結(jié)果如下：

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）

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

在學(xué)生提出的猜想不完整時(shí)，教師適時(shí)點(diǎn)撥學(xué)生，學(xué)生認(rèn)識到“？”部分不是一個(gè)定值，而是一個(gè)函數(shù)，應(yīng)該跟這里的k和d有關(guān)，對輸出結(jié)果進(jìn)行再次觀察和對比分析，最終學(xué)生發(fā)現(xiàn)“？”部分與k沒有關(guān)系，而是跟d有關(guān)的某個(gè)函數(shù)值。因此對結(jié)論進(jìn)行二次猜想：，其中是跟d有關(guān)的函數(shù)。

通過測試大數(shù)據(jù)發(fā)現(xiàn)的值只有1、-1、0三種，接下來，教師引導(dǎo)學(xué)生編寫程序把取這三種值對應(yīng)的d列舉出來觀察規(guī)律。有學(xué)生在此前猜想程序的基礎(chǔ)上稍作改動(dòng)。

學(xué)生在教師的引導(dǎo)下發(fā)現(xiàn)了不少關(guān)于的規(guī)律，現(xiàn)僅歸納跟取值有關(guān)的規(guī)律：

（1）當(dāng)d=1的時(shí)候，=1;

（2）當(dāng)d=p1*p2*...pk，其中pi（1≤i≤k）為互異素?cái)?shù)，則=（-1）k;

（3）其余情況則=0。

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

● 基于猜想，要求學(xué)生嚴(yán)謹(jǐn)探究驗(yàn)證

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

已知，證明成立。

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

把已知的結(jié)論帶入等式右邊得：

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

這樣的寫法很難跟左邊f(xié)（k）去進(jìn)行比較，需要進(jìn)行更換f（）為主體，把上式等價(jià)轉(zhuǎn)換為如圖2所示的樣子。

這樣，就可以很方便地去比較左右兩邊對于f（）的系數(shù)是否相等。接下來教師引導(dǎo)學(xué)生對右式進(jìn)行主體外移的等價(jià)變換處理。

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

要證明就轉(zhuǎn)化為證明：

當(dāng)T=1時(shí)，，成立。

當(dāng)T>1時(shí)，設(shè)，因?yàn)椋硗?，不需要考慮=0的情況，所以只需要考慮yi=0或1的情況。設(shè)d的質(zhì)因子分解中含有r個(gè)質(zhì)因子，T共有t個(gè)質(zhì)因子，則這樣的d有個(gè)，，含r個(gè)質(zhì)因子的d的之和等于，r可以從0取到k，累積即可。所以T>1時(shí)，，利用二項(xiàng)式定理，則有。得證！

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

● 歸納運(yùn)用，引導(dǎo)學(xué)生編程解決問題

教師引導(dǎo)學(xué)生回到最初所提出的問題：，g（k）=，如何利用g（k）反過來計(jì)算出f（k）?；谀葹跛狗囱莨?，學(xué)生就g（k）進(jìn)行式子變形，得到。

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

上述過程中，每位學(xué)生最終設(shè)計(jì)出的算法都集中體現(xiàn)了各自特有的思維方式，但是有的學(xué)生采用的算法處理效率高、速度快。為了讓每位學(xué)生都能夠恰當(dāng)?shù)乩盟鶎W(xué)的算法進(jìn)行程序設(shè)計(jì)，快速高效地解決實(shí)際問題，教師需要組織學(xué)生進(jìn)行討論和交流，讓每位學(xué)生都發(fā)表自己的看法和建議，讓每位學(xué)生在互相討論和交流的過程中學(xué)習(xí)到別人的長處，發(fā)現(xiàn)自己的不足。最終，學(xué)生形成了清晰的問題解決思路，經(jīng)過思考、改進(jìn)算法和編寫、調(diào)試程序，結(jié)合相互之間的交流與教師的個(gè)別指導(dǎo)，絕大多數(shù)學(xué)生都能夠編寫出完整的程序以解決課前所提出的問題。

“教”只是實(shí)現(xiàn)“學(xué)”的一種服務(wù)手段，學(xué)生的“學(xué)”才是教學(xué)的出發(fā)點(diǎn)和歸宿。整個(gè)教學(xué)實(shí)施的過程，沒有滔滔不絕的教師講解，也沒有氣氛熱烈的小組活動(dòng)，更多的是教師嚴(yán)密理性的引導(dǎo)，以及對學(xué)生的思考和實(shí)踐的激活，最終幫助學(xué)生深化科學(xué)思維，培養(yǎng)科學(xué)探究能力。