C語言中枚舉算法的優化及理解難易程度分析

張朝鑫

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

【關鍵詞】枚舉算法優化C語言

一、引言

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

二、常見枚舉算法

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

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

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

}

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

三、優化枚舉域后的算法

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

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

四、進一步優化枚舉算法4.1時間復雜度縮小優化

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

bool isPrime（int i）

{if（i<2）return false；

fo（rint k=2；k

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

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

4.2數學上的值域優化

數學上有定理：如果i不是素數，則i有滿足1

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

五、結束語

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

參考文獻

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