張朝鑫

【摘要】計算機(jī)程序設(shè)計語言C，在高校中普及開來，其算法教學(xué)的難易程度不同，學(xué)生理解把握不好。本文以常見的的教學(xué)方法，層層深入分析其中較為典型的“枚舉”算法，以基本的形式為支撐、不斷優(yōu)化其算法。

【關(guān)鍵詞】枚舉算法優(yōu)化C語言

一、引言

枚舉算法常常稱之為窮舉法，是計算機(jī)高級語言中很重要的一種算法，從可能出現(xiàn)的集合中一一列舉所有元素，用給定的已知條件來判斷是“有效的”還是“無效的”。所謂有效的就是條件成立，也就是問題的一個解法。

二、常見枚舉算法

枚舉算法在使用計算機(jī)編程求解數(shù)學(xué)問題時，很常見，比如：“百錢百雞”、“求水仙花數(shù)”、“求質(zhì)子數(shù)”、“求素數(shù)”。這些都是根據(jù)已知條件，在一個范圍域里，求符合條件的集合；可以表示為：a∈b。

以“求素數(shù)”為例，以多種方式求解，并比較其算法的優(yōu)缺點和學(xué)生理解的難易程度；使學(xué)生得以全面理解掌控其算法的特點。大家知道素數(shù)的含義：除自然數(shù)1以外只能被1和它自己本身整除的數(shù)即的素數(shù)。從理解的角度，從“素數(shù)”的定義，直接編程求100以內(nèi)的素數(shù)。列舉從2開始的數(shù)，分別用2至100的數(shù)去除，如果余數(shù)為0則說明當(dāng)前的數(shù)不是素數(shù)，反之則是。程序核心代碼如下：

for（i=2；i<100；i++）

{flag=1；for（j=2；j<100；j++）if（i%j==0）{flag=0；break；} if（flag==1）

printf（"i=%d是100以內(nèi)的一個素數(shù)＼n"，i）；

}

顯而易見，這種方法是對最原始的枚舉法的詮釋。對于學(xué)生來說很容易理解，也是對枚舉算法的定義的解釋表現(xiàn)；但是，其算法效率低、無效循環(huán)多。很明顯，如果在枚舉域大的時候，其弊端就會使程序運行困難。

三、優(yōu)化枚舉域后的算法

從上面的算法大家會發(fā)現(xiàn)，雖然最終可以得出結(jié)果，但其改進(jìn)的空間很大。大家可以從其枚舉域過大入手來優(yōu)化，上述程序深入研究后會發(fā)現(xiàn)：變量i在外層循環(huán)控制變量，其作用是列舉2以后所有的數(shù)；變量j在內(nèi)層循環(huán)，其作用是判斷其是否是素數(shù)和判斷的范圍。由此，可得出：例如i值等于78，本來判斷最大范圍應(yīng)該是2至77就足夠了。

所以，上述程序第二行可以優(yōu)化為：“{flag=1；for（j=2；j

四、進(jìn)一步優(yōu)化枚舉算法4.1時間復(fù)雜度縮小優(yōu)化

前面我提出的算法，如果用時間復(fù)雜度來表示的話，應(yīng)該是：O（i）。但是我們知道，除了2是素數(shù)以外；只要是2的整數(shù)倍是數(shù)它就不是素數(shù)，如果我們把它扣除在外那么速度就會提高一倍。表示為：O（i/2），可以在程序中加入以下語句來實現(xiàn)：

bool isPrime（int i）

{if（i<2）return false；

fo（rint k=2；k

if（i%k==0）return false；return true；}

在原有的基礎(chǔ)之上，此程序在開始執(zhí)行前加上了判斷其是否是偶數(shù)的語句；看似程序加長并變復(fù)雜。學(xué)生的第一感覺都是這樣，上述例子就是以函數(shù)的形式來展現(xiàn)，就是要學(xué)生理解；它其實就是完成一個小的功能而已，把這個理解了，就不難理解程序時間復(fù)雜度減小了一半。

4.2數(shù)學(xué)上的值域優(yōu)化

數(shù)學(xué)上有定理：如果i不是素數(shù)，則i有滿足1

在4.1節(jié)例子中程序第3行應(yīng)該改成：“for（int k=2；k<=sqrt（i）；k+=2）”。這種方式，可以認(rèn)為是初學(xué)C語言者的一個教學(xué)難點和重點；其綜合性很強(qiáng)，除了要掌握前面所述的算法外，還要對數(shù)學(xué)方面的知識能夠?qū)W懂。但只要大家比較其時間復(fù)雜度，就會得出很明顯的算法優(yōu)化，就知道其重要性。

五、結(jié)束語

枚舉算法在生活中經(jīng)常使用，在計算機(jī)編程中由為重要。雖然根據(jù)其原理，學(xué)者提出了許多的方法，諸如：篩法求素數(shù)，二分法求素數(shù)，利用數(shù)組等方式；但對于初學(xué)者來說又太難，本文是提高?？茖W(xué)生學(xué)習(xí)能力的有效路徑。

參考文獻(xiàn)

[1]梁潘.基于枚舉算法的優(yōu)化方法研究.阿壩師范高等專科學(xué)校電子信息工程系.重慶三峽學(xué)院學(xué)報. 2010.3