张朝鑫
【摘要】计算机程序设计语言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