《算法的概念(第一课时).ppt》由会员分享，可在线阅读，更多相关《算法的概念(第一课时).ppt（21页珍藏版）》请在三一办公上搜索。
1、算法的概念,、一个农夫带着一条狼、一头山羊和一篮蔬菜要过河,但只有一条小船.乘船时,农夫只能带一样东西.当农夫在场的时候,这三样东西相安无事.一旦农夫不在,狼会吃羊,羊会吃菜.请设计一个算法,使农夫能安全地将这三样东西带过河.,第一步:农夫带羊过河;,第二步:农夫独自回来;,第三步:农夫带狼过河;,第四步:农夫带羊回来;,第五步:农夫带蔬菜过河;,第六步:农夫独自回来;,第七步:农夫带羊过河.,2,汉诺塔问题甲柱子上从小到大放置三个圆环，现在要将这三个圆环移至乙柱，也要求从小到大的放置,一次必须移动一个，移动的过程中，大圆环不能放于小圆环上,如何移动？,算法:,“算法”通常是指可以用计算机来解
2、决的某一类问题的程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成.,算法的特征：,.确定性,2.程序性,3.有穷性,第一步:+2得:5x=1,第三步:将-2 得 5y=3.,第二步:解得:,第四步:解得:,第五步:得到方程组的解为,第一步：（2）a1(1)a2 得到(a1 b2a2 b1)y a1 c2 a2 c1,第二步:若 a1 b2 a2 b1 0，则原方程组无解或者有无穷组 解；否则 y（a1 c2 a2 c1）/(a1 b2 a2 b1),第三步：将 y 代入（1）得 x（b2 c1b1 c2）/(a1 b2a2 b1),第四步：得到 x,y 或者 无法求解信息
3、,这些步骤就构成了解二元一次方程组的算法,我们可以根据这一算法编制计算机程序,让计算机来解二元一次方程组.,第一步：计算 D a1b2a2b1；,第二步：如果 D 0,则原方程组无解或者有无穷多解；若是 D 0，则有 x（b2 c1 b1 c2）/D y（a1 c2 a2 c1）/D,第三步：输出计算的结果 x,y或者无法求解信息。,具体的算法如下：,第一步：给定正实数 r的值;第二步：计算 s r2;第三步：得到 s 的值.,练习1:课本P4 1,质数(又称为素数）就是在所有比1大的整数中，除了1和它本身以外，不再有别的约数，这种整数叫做质数或素数。还可以说成质数只有1和它本身两个约数。这就
4、是质数的定义。,1既不是质数(素数)也不是合数,例1,(1)设计一个算法,判断7是否为质数,基础知识回顾:,算法分析:,1.有可能成为7的约数的有哪几个数?,2,3,4,5,6,2.如何判断一个数是不是7的约数?,用7除以这个数,余数是否为0来判断这个数是不是7的约数,例1,(1)设计一个算法,判断7是否为质数,第一步,用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,得
5、到余数1.因为余数不为0,所以6不能整除7.,因此7是质数,例1,(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不是质数,例,(2)设计一个算法,判断53是否是质数?,第一步,用2除53,得到余数1.因为余数不为0,所以2不能整除53,第二步,用3除53,得到余数2.因为余数不为0,所以3不能整除53,第三步,用4除5
6、3,得到余数1.因为余数不为0,所以4不能整除53,第五十二步,用52除53,得到余数1.因为余数为1,所以52不能整除35.,因此53是质数,以上不能表示一个算法,设计一个算法,判断整数n(n2)是否为质数?,思考:,在上面判断7和35是不是质数的算法中,重复做的步骤是什么?,在上面判断7和35是不是质数的算法中,算法结束有哪几种情况?,在上面判断7和35是不是质数的算法中,从哪个数开始检验?,设计一个算法,判断整数n(n2)是否为质数?,第一步，给定大于2的整数n。,第二步，令i=2,第三步，用i除n，得到余数r。,第四步，判断“r=0”是否成立。,第五步，判断“i(n-1)”是否成立。,
7、若是，则n不是质数，结束算法;,否则，将i的值增加1，仍用i表示。,若是，则n不是质数，结束算法;,否则，返回第三步,2、任意给定一个大于 1 的正整数 n，设计一个算法求出 n 的所有因数。,算法步骤：,第一步：给定一个大于1的正整数n,第二步：令i=1,第三步：用i除n，得到余数r,第四步：判断“r=0”是否成立。若是，则i是n 的因数；否则，i不是n的因数,第五步：使i的值增加1，仍用i表示,第六步：判断“in”是否成立，若是，则结束算法，否则，返回第三步。,2.确定两点(x1,y1)和(x2,y2)间的距离,例题：用二分法设计一个求方程 x 2 2=0 的近似根的算法(近似值与精确值的
8、绝对值不超过0.005）,第二步：令m（x1+x2）/2，判断f（m）是否为0。若是，则m为所求；若否，则继续判断f（x1）f（m）大于0还是小于0。,第三步：若f（x1）f（m）0，则令x1 m；否则 令x2=m。,第四步：判断 l x1 x2 l 0.005是否成立?若是,则x1,x2之间的任意取值均为满足条件的近似根;若否,则返回第二步,第一步：令f（x）x 2 2，因为f（1）0，所以设 x 1 1，x 2 2,给定精确度d=0.005.,说明:(1)事实上算法并没有精确化的定义.(2)算法虽然没有一个明确的定义,但其特点是鲜明的,不仅要注意算法的程序性、有限性、明确性的特点，还应该充分理解算法问题的指向性，即算法往往指向解决某一类问题，泛泛地谈算法是没有意义的。,
