簡(jiǎn)單枚舉法在信息學(xué)競(jìng)賽中的應(yīng)用

杜春玲

摘 要： 枚舉法是信息學(xué)競(jìng)賽中一種最基本的算法，是競(jìng)賽中最常見的題型，本文主要介紹信息學(xué)競(jìng)賽中的枚舉法，從枚舉算法的優(yōu)化和判定條件這兩個(gè)方面探討如何用枚舉法解答信息學(xué)競(jìng)賽試題。

關(guān)鍵詞： 枚舉法 信息學(xué)競(jìng)賽 算法優(yōu)化 判定條件

信息學(xué)競(jìng)賽是在具有豐富知識(shí)和一定實(shí)踐能力的基礎(chǔ)上，思維與思維的競(jìng)賽。優(yōu)秀的選手往往具有快速、敏捷的思維。因此，我們?cè)诓粩嗵接懛椒ā⒖偨Y(jié)經(jīng)驗(yàn)的同時(shí)，有必要嘗試探索系統(tǒng)的思維方法，達(dá)到啟迪思路的目的，本文就介紹信息學(xué)競(jìng)賽中的一種思維方法：枚舉法。

枚舉法（也稱窮舉法） ，是基于計(jì)算機(jī)運(yùn)算速度快這一特性，使用的非常普遍的思維方法。根據(jù)問題中可能的情況，一一列舉出分析求解的方法，它指在一個(gè)有窮的可能的解的集合中，枚舉出集合中的每一個(gè)元素，用題目給定的約束條件判斷其是否符合條件，若滿足條件，則該元素即為整個(gè)問題的解；否則就不是問題的解。

下面探討如何用枚舉法解題。

一、縮小枚舉范圍可以優(yōu)化枚舉算法

我們以枚舉算法的經(jīng)典例題：百錢買百雞，探討枚舉算法的優(yōu)化。

有個(gè)人打算用一百塊錢買一百只雞。到市場(chǎng)一看，大雞三塊錢一只，不大不小的雞兩塊錢一只，小雞一塊錢三只。怎樣才能用一百塊錢買一百只雞？

算法分析：我們以三種雞的個(gè)數(shù)為枚舉對(duì)象（分別設(shè)為x，y，z），以三種雞的總數(shù)（x+y+z）和買雞用去的錢的總數(shù)（x*3+y*2+z）為判定條件，窮舉各種雞的個(gè)數(shù)。以下是解百雞問題的程序：

for x∶=0 to 100 do {枚舉大雞所有可能的解}

for y∶=0 to 100 do{枚舉不大不小的雞所有可能的解}

for Z∶=0 to 100 do{枚舉小雞所有可能的解}

if （x+y+z=100）and（x*3+y*2+z div 3=100）and （z mod 3=0） then writeln（x，y，z）；

本題還有優(yōu)化空間，三種雞的總只數(shù)是100，我們只要枚舉兩種雞（x，y），第三種雞就可以根據(jù)約束條件求得（z=100-x-y），這樣就縮小了枚舉范圍，請(qǐng)看下面的程序：

for x：=0 to 100 do

for y：=0 to 100-x do

begin z：=100-x-y；

if （x*3+y*2+z div 3=100）and（z mod 3=0）then writeln（x，y，z）； end；

未經(jīng)優(yōu)化的程序循環(huán)了101■ 次，優(yōu)化后的程序只循環(huán)了（102*101/2）次。因此，對(duì)于枚舉算法，找出約束條件，縮小枚舉范圍，是程序優(yōu)化的主要考慮方向。

二、解題的關(guān)鍵是設(shè)定正確的判定條件

在解題過程中，枚舉法的判定條件也很重要，如果約束條件不正確或不全面，就窮舉不出正確的結(jié)果，請(qǐng)看一元三次方程求解的例子。

ax■+bx■+cx+d=0，該方程各項(xiàng)系數(shù)（a，b，c，d均為實(shí)數(shù)），并設(shè)定該方程有三個(gè)不同實(shí)根（根的范圍在-100至100之間，且根與根之差的絕對(duì)值>=1）。要求在同一行輸出這三個(gè)實(shí)根，并精確到小數(shù)點(diǎn)后兩位。

算法分析：根的范圍在-100到100之間，保留兩位小數(shù)，我們將根的值域擴(kuò)大100倍（-10000<=x<=10000），再以根為枚舉對(duì)象，枚舉范圍是-10000到10000，用原方程式一一驗(yàn)證，找出方程的解。

有的同學(xué)是這樣做的：

for i：=-10000 to 10000 do

begin x：=i/100；

if a*x*x*x+b*x*x+c*x+d=0 then write（x：0：2，）； end；

用這樣的方法把程序編寫出來，將樣例數(shù)據(jù)代入測(cè)試是對(duì)的，但這題不完全對(duì)。

這種解法為什么有問題呢？通過上面的算法，枚舉范圍和枚舉對(duì)象都沒有錯(cuò)，但在驗(yàn)證枚舉結(jié)果時(shí)，判定條件用錯(cuò)了。由于要保留兩位小數(shù)，因此求出來的解不一定是方程的精確根，再代入ax■+bx■+cx+d中，所得的結(jié)果就不一定等于0，因此用原方程ax■+bx■+cx+d作為判斷條件是不準(zhǔn)確的。

我們換一個(gè)思路考慮這個(gè)問題，該方程f（x）=ax■+bx■+cx+d，假設(shè)x為方程的根，一定會(huì)有f（x-0.005）*（x+0.005）<0，如果以此為枚舉算法的判定條件，問題就會(huì)順利解決。而且，如果f（x-0.005）=0，就說明x-0.005是方程的根，這時(shí)四舍五入，方程的根就是x。所以我們用 （f（x-0.005）*f（x+0.005）<0） 和 （f（x-0.005）=0）作為判定條件。

用枚舉法解題的最大缺點(diǎn)是運(yùn)算量比較大，解題效率低，如果枚舉范圍太大（一般以不超過兩百萬次為限），就會(huì)超出競(jìng)賽要求的時(shí)限。但枚舉算法的思路簡(jiǎn)單，比賽時(shí)容易想到，易于程序編寫和調(diào)試，因此，如果題目的枚舉范圍規(guī)模不是很大，在規(guī)定時(shí)限內(nèi)能夠求出正確的解，那么我們最好采用枚舉法，而不需要耗用時(shí)間想那些更快的算法，這樣就可以有更多時(shí)間解答其他難題。