簡單枚舉法在信息學競賽中的應用

杜春玲

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

關鍵詞： 枚舉法 信息學競賽 算法優化 判定條件

信息學競賽是在具有豐富知識和一定實踐能力的基礎上，思維與思維的競賽。優秀的選手往往具有快速、敏捷的思維。因此，我們在不斷探討方法、總結經驗的同時，有必要嘗試探索系統的思維方法，達到啟迪思路的目的，本文就介紹信息學競賽中的一種思維方法：枚舉法。

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

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

一、縮小枚舉范圍可以優化枚舉算法

我們以枚舉算法的經典例題：百錢買百雞，探討枚舉算法的優化。

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

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

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）；

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

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；

未經優化的程序循環了101■ 次，優化后的程序只循環了（102*101/2）次。因此，對于枚舉算法，找出約束條件，縮小枚舉范圍，是程序優化的主要考慮方向。

二、解題的關鍵是設定正確的判定條件

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

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

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

有的同學是這樣做的：

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；

用這樣的方法把程序編寫出來，將樣例數據代入測試是對的，但這題不完全對。

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

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

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