高中程序設計中的算法優化

摘 要：信息學奧賽以培養學生的學習興趣為主，讓學生的核心素養得以提高。本文通過“百錢買百雞”問題的教學設計案例分析，在學生已有的數學知識的基礎之上，逐步引導學生進行算法優化，有效提高學生的計算思維這一核心素養，培養他們發現問題、分析問題和解決問題的能力。

關鍵詞：百錢買百雞；計算思維；時間復雜度；算法優化

筆者從事高中信息學奧賽多年，有一點感觸——開始學習這門課的學生和動力都很大（因為覺得很好玩，也很簡單）沒有涉及算法，就是簡單輸入輸出和一些簡單的語法，學生可以很輕松地解決一個問題，很有成就感。但是自從接觸了循環之后，有些學生已經堅持不了了，我仔細分析了原因：①學生缺少興趣；②學生沒有學習算法的主動性；③學生對算法設計比較厭煩（覺得很枯燥，就是部分學生說的有的算法很燒腦）；④學生的數學知識可能與程序設計的要求不一致（數學知識要滯后）；⑤很有可能是我們的教法過于簡單陳舊。所以我們今后要做好這項工作就必須根據具體的情況制定出可行的措施對學生進行施教。為該課程打下較好興趣基礎。

“百錢買百雞”是一個古老的問題，具體解決的方法可以根據學生自己在初中學到的知識完成程序設計，然后可以在程序運行的時間復雜度上提出相應的要求，讓學生不斷地修改程序來進行算法的優化，最終達到從1000000次運算優化到4次運算。在這個過程中老師要不斷地加以引導，還要不時地與學生進行交流，找到學生理解困難的地方，并及時加以講解，一步一步地讓學生進入自己所預設的操作當中。要對我們預設的效果進行合理合法的算法設計與分析，讓學生不斷地了解優化算法的重要性（為什么我們同樣的程序雖然大家都可以得出正確的答案，但是有的同學寫的程序運行效率很高，有些同學編寫的程序運行時間很長），從而進一步激發學生學習這門課的興趣。為信息學奧賽打下良好的基礎。

百錢買百雞的問題描述：公元前五世紀，我國古代數學家張丘建在《算經》一書中提出了“百雞問題”：雞翁一值錢五，雞母一值錢三，雞雛三值錢一。百錢買百雞，問雞翁、雞母、雞雛各幾何？翻譯為現代漢語的意思是：一只公雞賣5文錢，一只母雞賣3文錢，三只小雞賣1文錢，問100文錢

買100只雞，可以買多少只公雞？多少只母雞？多少只小雞？

教師在引導學生理解了題目意思之后，可以讓學生獨立完成程序設計，學生的一般寫法一般都會用到三重循環和二重循環。當然他們幾乎都沒有對程序算法進行優化或者說進行了簡單的、粗暴的優化。三重循環就沒有優化，就是用暴力的循環完成。公雞、母雞和小雞都是從0到100之間，讓計算機用窮舉法列出符合的結果。簡單的初步優化可以考慮100文全買公雞應該是20，全買母雞應該是34，最多買100只小雞。這樣對公雞、母雞和小雞進行了初步的模糊范圍進行修改優化。三重循環的偽代碼如下：

//算法1 三重循環不優化

Void bqmbj1（ ）

{ int x，y，z； //x公雞數y母雞數z小雞數

For（x=0；x<=100；x++）

For（y=0；y<=100；y++）

For（z=0；z<=100；z++）

If（x+y+z==100&&5*x+3*y+z/3==100&&z;%3==0）

Cout<

}

//算法2 三重循環初步優化

Void bqmbj2（ ）

{ int x，y，z； //x公雞數y母雞數z小雞數

For（x=0；x<=20；x++）

For（y=0；y<=34；y++）

For（z=0；z<=100；z++）

If（x+y+z==100&&5*x+3*y+z/3==100&& z%3==0）

Cout<

}

在三重循環基礎之上我們進一步分析三個變量之間的關系，第三個變量只要通過前面的兩個變量就可以得出，即z=100-x-y；由于減少了變量的個數，所以我們可以寫出下面兩個算法，算法3就是不優化的二重循環，而算法4就是考慮了公雞最多買20只，母雞最多34只。二重循環的偽代碼如下：

//算法3 二重循環不優化

Void bqmbj3（ ）

{ intx，y，z； //x公雞數y母雞數z小雞數

For（x=0；x<=100；x++）

For（y=0；y<=100；y++）{

z=100-x-y；

If（x+y+z==100&&5*x+3*y+z/3==100&&z;%3==0）

Cout<

}

//算法4 二重循環初步優化

Void bqmbj3（ ）

{ int x，y，z； //x公雞數y母雞數z小雞數

For（x=0；x<=20；x++）

For（y=0；y<=34；y++）{

z=100-x-y；

If（x+y+z==100&&5*x+3*y+z/3==100&& z%3==0）

Cout<

}

從上面列舉的四個算法，雖然偽代碼差不多，但是優化之后的程序在時間復雜度上有了質的變化。

我們看IF語句的執行頻度，運算量1030301次降到714次，體會到算法優化的優越性，也就告誡我們既要能算法設計，也要有算法優化的理念。盡可能寫出最優的算法。

對這個程序我們還可以進一步進行優化，最終實現一重循環。我們在施教程序優化的過程中要注意循序漸進，一步一步把學生引入最優算法。當然這里必須要以學生的數學知識作為基礎。否則算法優化只能說一個空中樓閣。大家在平時的施教中灌輸算法優化的思想，加強計算思維的訓練，為學生的終身發展奠定必要的基礎。

參考文獻：

[1]胡峰，王國胤.算法分析與設計[J].當代教育理論與實踐，2011（12）：72-74.

[2]鄧春燕，張長海等.如何有效培養和提高高級語言程序設計學習興趣[J].計算機教育，2011（8）.

作者簡介：凌忠寶，江蘇省泰州市，泰州市姜堰區張甸中學。