算法的概念〔第一课时〕.ppt

汉诺塔问题 甲柱子上从小到大放置三个圆环，现在要将这三个圆环移至乙柱，也要求从小到大的放置 , 一次必须移动一个，移动的过程中，大圆环不能放于小圆环上,如何移动？ * * 、一个农夫带着一条狼、一头山羊和一篮蔬菜要过河,但只有一条小船.乘船时,农夫只能带一样东西.当农夫在场的时候,这三样东西相安无事.一旦农夫不在,狼会吃羊,羊会吃菜.请设计一个算法,使农夫能安全地将这三样东西带过河. 第一步:农夫带羊过河; 第二步:农夫独自回来; 第三步:农夫带狼过河; 第四步:农夫带羊回来; 第五步:农夫带蔬菜过河; 第六步:农夫独自回来; 第七步:农夫带羊过河. 算法: “算法”通常是指可以用计算机来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成. 算法的特征： １.确定性 2.程序性 3.有穷性 ① ② 第一步:①+②×2得: 5x=1 ③ 第三步: 将②- ① ×2 得 5y=3 . ④ 第二步: 解③得: 第四步: 解④得: 对于一般的二元一次方程组 其中 能否找到一个程序化的求解步骤. 第五步: 得到方程组的解为 第一步：（2）×a1 － ( 1 ) ×a2 得到 (a1 b2－a2 b1) y ＝ a1 c2 －a2 c1 第二步:若 a1 b2 － a2 b1 ＝0，则原方程组无解或者有无穷组 解；否则 y＝（a1 c2 － a2 c1）/ (a1 b2 － a2 b1) 第三步：将 y 代入（1）得 x ＝ （b2 c1－b1 c2）/ (a1 b2－a2 b1) 第四步：得到 x , y 或者 无法求解信息 a1 x ＋b1 y ＝ c1 （1） a2 x ＋b2 y ＝ c2（2） 二元一次方程组 这些步骤就构成了解二元一次方程组的算法,我们可以根据这一算法编制计算机程序,让计算机来解二元一次方程组. 第一步：计算 D ＝ a1b2－a2b1 ； 第二步：如果 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和它本身两个约数。这就是质数的定义。 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,得到余数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除53,得到余数1.因为余数不为0,所以4不能整除53 第五十二步,用52除53,得到余数1.因为余数为1,所以52不能整除35. 因此53是质数 … … 以上不能表示一个算法 设计一个算法,判断整数n(n2)是否为质数