(6)算法的特征:①确定性:算法的每一步都 应当做到准确无误、不重不漏.“不重”是指不是可有可无的,甚至无用的步骤,“不漏” 是指缺少哪一步都无法完成任务.②逻辑性:算法从开始的“第一步”直到“最后一步”之间做到环环相扣,分工明确,“前一步”是“后一步”的前提, “后一步”是“前一步”的继续.③有穷性:算法要有明确的开始和结束,当到达终止步骤时所要解决的问题必须有明确的结果,也就是说必须在有限步内完成任务,不能无限制地持续进行.
(7)在解决某些问题时,需要设计出一系列可操作或可计算的步骤来解决问题,这些步骤称为解决这些问题的算法.也就是说,算法实际上就是解决问题的一种程序性方法.算法一般是机械的,有时需进行大量重复的计算,它的优点是一种通法,只要按部就班地去做,总能得到结果.因此算法是计算科学的重要基础.
应用示例
思路1
例1 (1)设计一个算法,判断7是否为质数.
(2)设计一个算法,判断35是否为质数.
算法分析:(1)根据质数的定义,可以这样判断:依次用2—6除7,如果它们中有一个能整除7,则7不是质数,否则7是质数.
算法如下:(1)第一步,用2除7,得到余数1.因为余数不为0,所以2不能整除7.
第二步,用3除 7,得到余数1.因为余数不为0,所以3不能整除7.
第三步,用4除7,得到余数3.因为余数不为0,所以4不能整除7.
第四步,用5除7,得到余数2.因为余数不为0,所以5不能整除7.
第五步,用6除7,得到余数1.因为余数不为0,所以6不能整除7.因此,7是质数.
(2)类似地,可写出“判断35是否为质数”的算法:第一步,用2除35,得到余数1.因为余数不为0,所以2不能整除35.
第二步,用3除35,得到余数2.因为余数不为0,所以3不能整除35.
第三步,用4除35,得到余数3.因为余数不为0,所以4不能整除35.
第四步,用5除35,得到余数0.因为余数为0,所以5能整除35.因此,35不是质数.
点评:上述算法有很大的局限性,用上述算法判断35是否为质数还可以,如果判断1997是否为质数就麻烦了,因此,我们需要寻找普适性的算法步骤.
变式训练
请写出判断n(n >2)是否为质数的算法.
分析:对于任意的整数n( n>2),若用i表示2—(n-1)中的任意整数,则“判断n是否为质数”的算法包含下面的重复操作:用i除n,得到余数r.判 断余数r是否为0,若是,则不是质数;否则,将i的值增加1,再执行同样的操作.
这个操作一直要进行到i的值等于(n-1)为止.
算法如下:第一步,给定大于2的整数n.
第二步,令i=2.
第三步,用i除n,得到余数r.
第四步,判断“r=0”是否成立.若是,则n不是质数,结束算法;否则,将i的值增加1,仍用i表示.
第五步,判断“i>(n-1)”是否成立.若是,则n是质数,结束算法;否则,返回第三步.
例2 写出用“二分法”求方程x2-2=0 (x>0)的近似解的算法.
分析:令f(x)=x2-2,则方程x2-2=0 (x>0)的解就是函数f(x)的零点.
“二分法”的基本思想是:把函数f(x)的零点所在的区间[a,b](满足f(a)f(b)<0)“一分为二”,得到[a,m]和[m,b].根据“f(a)f(m)<0”是否成立,取出零点所在的区间[a,m]或[m,b],仍记为[a,b].对所得的区间[a,b]重复上述步骤,直到包含零点的区间[a,b]“足够小”,则[a,b]内的数可以作为方程的近似解.[来源:学&科&网Z&X&X&K]
解:第一步,令f(x)=x2-2,给定精确度d.
第二步,确定区间[a,b],满足f(a)f(b)<0.
第三步,取区间中点m= .
第四步,若f(a)f(m)<0,则含零点的区间为[a,m];否则,含零点的区间为[m,b].将新得到的含零点的区间仍记为[a,b].
第五步,判断[a,b]的长度是否小于d或f(m)是否等于0.若是,则m是方程的近似解;否则,返回第三步.
当d=0.005时,按照以上算法,可以得到下表.
a b |a-b|
1 2 1
1 1.5 0.5
1.25 1.5 0.25
1.375 1.5 0.125
1.375 1.437 5 0.062 5
1.406 25 1.437 5 0.031 25
1.406 25 1.421 875 0.015 625
1.414 062 5 1.421 875 0.007 812 5
1.414 062 5 1.417 968 75 0.003 906 25
于是,开区间(1.414 062 5,1.417 968 75)中的实数都是当精确度为0.005时的原方程的近似解.实际上,上述步骤也是求 的近似值的一个算法.
点评:算法一般是机械的,有时需要进行大量的重复计算,只要按部就班地去做,总能算出结果,通常把算法过程称为“数学机械化”.数学机械化的最大优点是它可以借助计算机来完成,实际上处理任何问题都需要算法.如:中国象棋有中国象棋的棋谱、走法、胜负的评判准则;而国际象棋有国际象棋的棋谱、走法、胜负的评判准则;再比如 申请出国有一系列的先后手续,购买物品也有相关的手续……
思路2
例1 一个人带着三只狼和三只羚羊过河,只有一条船,同船可容纳一个人和两只动物,没有人在的时候,如果狼的数量不 少于羚羊的数量就会吃羚羊.该人如何将动物转移过河?请设计算法.
分析:任何动物同船不用考虑动物的争斗但需考虑承载的数量,还应考虑到两岸的动物都得保证狼的数量要小于羚羊的数量,故在算法的构造过程中尽可能保证船里面有狼,这样才能使得两岸的羚羊数量占到优势.
解:具体算法如下:
算法步骤:
第一步:人带两只狼过河,并自己返回.
第二步:人带一只狼过河,自己返回.
第三步:人带两只羚羊过河,并带两只狼返回.
第四步:人带一只羊过河,自己返回.
第五步:人带两只狼过河.
点评:算法是解决某一类问题的精确描述,有些问题使用形式化、程序化的刻画是最恰当的.这就要求我们在写算法时应精练、简练、清晰地表达,要善于分析任何可能出现的情况,体现思维的严密性和完整性.本题型解决问题的算法中某些步骤重复进行多次才能解决,在现实生活中,很多较复杂的情境经常遇到这样的问题,设计算法的时候,如果能够合适地利用某些步骤的重复,不但可以使得问题变得简单,而且可以提高工作效率.