高中程序設(shè)計(jì)中的算法優(yōu)化

摘 要：信息學(xué)奧賽以培養(yǎng)學(xué)生的學(xué)習(xí)興趣為主，讓學(xué)生的核心素養(yǎng)得以提高。本文通過“百錢買百雞”問題的教學(xué)設(shè)計(jì)案例分析，在學(xué)生已有的數(shù)學(xué)知識(shí)的基礎(chǔ)之上，逐步引導(dǎo)學(xué)生進(jìn)行算法優(yōu)化，有效提高學(xué)生的計(jì)算思維這一核心素養(yǎng)，培養(yǎng)他們發(fā)現(xiàn)問題、分析問題和解決問題的能力。

關(guān)鍵詞：百錢買百雞；計(jì)算思維；時(shí)間復(fù)雜度；算法優(yōu)化

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

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

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

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

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

//算法1 三重循環(huán)不優(yōu)化

Void bqmbj1（ ）

{ int x，y，z； //x公雞數(shù)y母雞數(shù)z小雞數(shù)

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 三重循環(huán)初步優(yōu)化

Void bqmbj2（ ）

{ int x，y，z； //x公雞數(shù)y母雞數(shù)z小雞數(shù)

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<

}

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

//算法3 二重循環(huán)不優(yōu)化

Void bqmbj3（ ）

{ intx，y，z； //x公雞數(shù)y母雞數(shù)z小雞數(shù)

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 二重循環(huán)初步優(yōu)化

Void bqmbj3（ ）

{ int x，y，z； //x公雞數(shù)y母雞數(shù)z小雞數(shù)

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<

}

從上面列舉的四個(gè)算法，雖然偽代碼差不多，但是優(yōu)化之后的程序在時(shí)間復(fù)雜度上有了質(zhì)的變化。

我們看IF語句的執(zhí)行頻度，運(yùn)算量1030301次降到714次，體會(huì)到算法優(yōu)化的優(yōu)越性，也就告誡我們既要能算法設(shè)計(jì)，也要有算法優(yōu)化的理念。盡可能寫出最優(yōu)的算法。

對這個(gè)程序我們還可以進(jìn)一步進(jìn)行優(yōu)化，最終實(shí)現(xiàn)一重循環(huán)。我們在施教程序優(yōu)化的過程中要注意循序漸進(jìn)，一步一步把學(xué)生引入最優(yōu)算法。當(dāng)然這里必須要以學(xué)生的數(shù)學(xué)知識(shí)作為基礎(chǔ)。否則算法優(yōu)化只能說一個(gè)空中樓閣。大家在平時(shí)的施教中灌輸算法優(yōu)化的思想，加強(qiáng)計(jì)算思維的訓(xùn)練，為學(xué)生的終身發(fā)展奠定必要的基礎(chǔ)。

參考文獻(xiàn)：

[1]胡峰，王國胤.算法分析與設(shè)計(jì)[J].當(dāng)代教育理論與實(shí)踐，2011（12）：72-74.

[2]鄧春燕，張長海等.如何有效培養(yǎng)和提高高級語言程序設(shè)計(jì)學(xué)習(xí)興趣[J].計(jì)算機(jī)教育，2011（8）.

作者簡介：凌忠寶，江蘇省泰州市，泰州市姜堰區(qū)張甸中學(xué)。