《高考数学复习点拨 算法优化问题例析.doc》由会员分享,可在线阅读,更多相关《高考数学复习点拨 算法优化问题例析.doc(3页珍藏版)》请在金锄头文库上搜索。
1、算法优化问题例析我们知道,算法具有不唯一性,但算法具有优劣之分,下面我们通过实例用对比的方法来分析和解决算法的优化问题例1一位商人有9枚银元,其中1枚略轻的是假银元,你能用天平(无砝码)将假银元找出来吗?写出这一问题的算法解法1:算法步骤如下:第一步:任取2枚银元分别放在天平的左右两边,如果天平左右不平衡,则轻的那一边就是假银元;如果天平平衡,则进行第二步;第二步:取下右边的银元,放在一边,然后把剩下的7枚银元依次放在右边进行称量,直到天平不平衡,偏轻的那一边就是假银元解法2:算法(优化的算法)步骤如下:第一步:把9枚银元平均分成3组,每组3枚;法例2数列即按一定次序排列的一列数数列中的每一个
2、数都叫做这个数列的“项”,各项依次叫做这个数列的第1项、第2项、第n项,一般形式可以写成,其中是数列的第项数列为斐波那契数列,其中,画出程序框图,表示输出此数列的前30项的算法解法1:程序框图见图1:解法2:程序框图见图2:评析:算法1的变量较多,所占计算机内存较多;算法2涉及的变量较少,所占计算机内存较少,故算法2是较好的算法例2 给定一个大于1的整数,设计一个算法,判断是否为质数,并画出程序框图解法1:算法如下:第一步:判断是否等于2,若,则是质数,若,则执行第二步;第二步:依次检验是不是的因数,若有这样的数,则不是质数;否则,是质数程序框图见图3解法二:算法如下:第一步:判断是否等于2,
3、若,则是质数,若,则执行第二步第二步:依次检验(表示的因数,若有这样的数,则不是质数;否则,是质数其程序框图见图4解法3:算法如下:第一步:判断是否等于2,若,则是质数,若,则执行第二步;第二步:判断是否为偶数,若为偶数,则不是质数,否则,执行第三步;第三步:依次检验是否为的因数,若有这样的数,则不是质数;否则,是质数请读者画出这一算法的程序框图评析:对于判断一个较大的正整数n是否为质数,算法2和算法3都比算法1优越,因为算法1的计算次数较多,而算法2和算法3减少了运算次数,类似地,课本上四种案例中的计算多项式值的秦九韶算法,是因减少了乘法运算的次数,而成为优化的算法规律总结:优化的算法具有以下显著的特点:1能使运算难度降低或运算次数减少;2使计算机便于运行,提高运算速度;3能使所占计算机内存减少用心 爱心 专心