C语言中枚举算法的优化及理解难易程度分析

2014-10-17张朝鑫

中国新通信 2014年5期

关键词：枚举素数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语言者的一个教学难点和重点；其综合性很强，除了要掌握前面所述的算法外，还要对数学方面的知识能够学懂。但只要大家比较其时间复杂度，就会得出很明显的算法优化，就知道其重要性。

五、结束语