算法的概念(第一课时)课件

《算法的概念(第一课时)课件》由会员分享，可在线阅读，更多相关《算法的概念(第一课时)课件（21页珍藏版）》请在装配图网上搜索。

1、算法的概念(第一课时)算法的概念(第一课时)算法的概念(第一课时) 、一个农夫带着一条狼、一头山羊和一篮、一个农夫带着一条狼、一头山羊和一篮蔬菜要过河蔬菜要过河,但只有一条小船但只有一条小船.乘船时乘船时,农夫只能农夫只能带一样东西带一样东西.当农夫在场的时候当农夫在场的时候,这三样东西相安这三样东西相安无事无事.一旦农夫不在一旦农夫不在,狼会吃羊狼会吃羊,羊会吃菜羊会吃菜.请设计请设计一个算法一个算法,使农夫能安全地将这三样东西带过河使农夫能安全地将这三样东西带过河.第一步第一步: :农夫带羊过河农夫带羊过河; ;第二步第二步: :农夫独自回来农夫独自回来; ;第三步第三步: :农夫带狼过河

2、农夫带狼过河; ;第四步第四步: :农夫带羊回来农夫带羊回来; ;第五步第五步: :农夫带蔬菜过河农夫带蔬菜过河; ;第六步第六步: :农夫独自回来农夫独自回来; ;第七步第七步: :农夫带羊过河农夫带羊过河. .算法的概念(第一课时) 汉诺塔问题汉诺塔问题甲柱子上从小到大放置三个圆环，现在要将这三个圆环移至乙柱，也甲柱子上从小到大放置三个圆环，现在要将这三个圆环移至乙柱，也要求从小到大的放置要求从小到大的放置 , , 一次必须移动一个，移动的过程中，大圆一次必须移动一个，移动的过程中，大圆环不能放于小圆环上环不能放于小圆环上, ,如何移动？如何移动？算法的概念(第一课时)算法算法:“算法算法

3、”通常是指可以用计算机来解决的某一类问题的程通常是指可以用计算机来解决的某一类问题的程序或步骤序或步骤,这些程序或步骤必须是明确和有效的这些程序或步骤必须是明确和有效的,而且能够而且能够在有限步之内完成在有限步之内完成.算法的特征：算法的特征：. .确定性确定性2.程序性程序性3.有穷性有穷性算法的概念(第一课时)2121xyxy 第一步第一步:+2得得: 5x=1 第三步第三步: 将将- 2 得得 5y=3 . 第二步第二步: 解解得得:51 x第四步第四步: 解解得得:35y 对于一般的二元一次方程组对于一般的二元一次方程组其中其中 能否找到一个程序化的能否找到一个程序化的求解求解步骤步骤

4、.111222a xb yca xb yc1 22 10aba b第五步第五步: 得到方程组的解为得到方程组的解为 5351yx算法的概念(第一课时)第一步第一步：（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 x , , y y 或者或者 无

5、法求解信息无法求解信息a1 x b1 y c1 （1）a2 x b2 y c2（2）二元一次方程组二元一次方程组算法的概念(第一课时)这些步骤就构成了解二元一次方程组的这些步骤就构成了解二元一次方程组的算法算法,我们可以根据这一算法编制计算机程序我们可以根据这一算法编制计算机程序,让计算机来解二元一次方程组让计算机来解二元一次方程组.算法的概念(第一课时)第一步第一步：计算计算 D a1b2a2b1 ； 第二步：如果第二步：如果 D D 0,0,则原方程组无解或者有无穷多则原方程组无解或者有无穷多解；解； 若是若是 D D 0 0，则有，则有 x （ b2 c1 b1 c2 ） / D y （

6、 a1 c2 a2 c1 ）/ D第三步：输出计算的结果第三步：输出计算的结果 x,x,y y或者无法求解信息。或者无法求解信息。 具体的算法如下：具体的算法如下：算法的概念(第一课时)第一步：给定正实数第一步：给定正实数 r r的值的值 ; ;第二步：计算第二步：计算 s s r r2 2 ; ;第三步：得到第三步：得到 s s 的值的值 . .练习练习1:1:课本课本P P4 4 1 1算法的概念(第一课时)质数质数(又称为素数）就是在所有比又称为素数）就是在所有比1大的整数中，除了大的整数中，除了1和它本身以外，不再有别的约数，这种整数叫做质和它本身以外，不再有别的约数，这种整数叫做质数

7、或素数。还可以说成质数只有数或素数。还可以说成质数只有1和它本身两个约数。和它本身两个约数。这就是质数的定义。这就是质数的定义。 1既不是质数既不是质数(素数素数)也不是合数也不是合数 例例1(1)设计一个算法设计一个算法,判断判断7是否为质数是否为质数基础知识回顾基础知识回顾:算法分析算法分析:1.有可能成为有可能成为7的约数的有哪几个数的约数的有哪几个数?2,3,4,5,62. 如何判断一个数是不是如何判断一个数是不是7的约数的约数?用用7除以这个数除以这个数,余数是否为余数是否为0来判断这个数是来判断这个数是不是不是7的约数的约数算法的概念(第一课时)例例1(1)设计一个算法设计一个算法

8、,判断判断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是质数是质数算法的概念(第

9、一课时)例例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)设计一个算法设计一个算法,

10、判断判断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是质数是质数 以上不能表示一个算法以上不能表示一个算法算法的概念(第一课时)设计一个算法设计一个算法,判断整数

11、判断整数n(n2)是否为质数是否为质数?思考思考:在上面判断在上面判断7和和35是不是质数的算法中是不是质数的算法中,重复做的步骤重复做的步骤是什么是什么?在上面判断在上面判断7和和35是不是质数的算法中是不是质数的算法中,算法结束有哪算法结束有哪几种情况几种情况?在上面判断在上面判断7和和35是不是质数的算法中是不是质数的算法中,从哪个数开始从哪个数开始检验检验?算法的概念(第一课时)设计一个算法设计一个算法,判断整数判断整数n(n2)是否为质数是否为质数?第一步，给定大于第一步，给定大于2的整数的整数n。第二步，令第二步，令i=2第三步，用第三步，用i除除n，得到余数，得到余数r。第四步，

12、判断第四步，判断“r=0”是否成立。是否成立。第五步，判断第五步，判断“i(n-1)”是否成立。是否成立。 若是，则若是，则n不是质不是质数，结束算法数，结束算法; 否则，将否则，将i的值增加的值增加1，仍用，仍用i表示。表示。 若是，则若是，则n不是不是质数，结束算法质数，结束算法; 否则，返回第三步否则，返回第三步算法的概念(第一课时)2、任意给定一个大于、任意给定一个大于 1 的正整数的正整数 n ，设计一个算法求，设计一个算法求出出 n 的所有因数。的所有因数。算法步骤：算法步骤：第一步：给定一个大于第一步：给定一个大于1的正整数的正整数n第二步：令第二步：令i=1第三步：用第三步：用

13、i除除n，得到余数，得到余数r第四步：判断第四步：判断“r=0”是否成立。若是，则是否成立。若是，则i是是n 的的因数；否则，因数；否则，i不是不是n的因数的因数第五步：使第五步：使i的值增加的值增加1，仍用，仍用i表示表示第六步：判断第六步：判断“in”是否成立，若是，则结束算法，是否成立，若是，则结束算法，否则，返回第三步。否则，返回第三步。算法的概念(第一课时)第一步第一步：确定确定 x1, x2 , y1 , y2 的的 值值 ;第二步第二步：计算计算 x2x1 , y2y1 ;第三步第三步：计算计算d(x2 x1)2+(y2 y1)2 ;第四步第四步：得到两点的距离得到两点的距离 d

14、2.确定两点确定两点(x1, y1 ) 和和( x2, y2 )间的距离间的距离算法的概念(第一课时)例题：用二分法设计一个求方程例题：用二分法设计一个求方程 x x 2 2 2 = 02 = 0 的近的近似根的算法似根的算法( (近似值与精确值的绝对值不超过近似值与精确值的绝对值不超过0.0050.005）第二步第二步：令：令m （x1+x2）/ 2，判断判断f （ m）是否为是否为0 0。若是。若是， 则则m m为所求为所求；若否，则继续判断若否，则继续判断f（x1） f（m）大于大于0 0还是小于还是小于0 0。 第三步第三步：若：若f（x1） f（m ） 0，则令，则令x1 m ；否则

15、；否则 令令x2=m。第四步第四步：判断：判断 l x1 x2 l 0.005是否成立是否成立? ?若是若是, ,则则x x1 1,x,x2 2之间的之间的任意取值均为满足条件的近似根任意取值均为满足条件的近似根; ;若否若否, ,则返回第二步则返回第二步第一步：第一步：令令f （x） x 2 2 ，因为因为f（1） 0，所以设所以设 x 1 1，x 2 2,给定精确度给定精确度d=0.005.算法的概念(第一课时)说明说明:(1)事实上算法并没有精确化的定义事实上算法并没有精确化的定义.(2)算法虽然没有一个明确的定义算法虽然没有一个明确的定义,但其特点但其特点是鲜明的是鲜明的,不仅要注意不仅要注意算法的程序性、有限算法的程序性、有限性、明确性的特点，还应该充分理解算法性、明确性的特点，还应该充分理解算法问题的指向性，即算法往往指向解决某一问题的指向性，即算法往往指向解决某一类问题，泛泛地谈算法是没有意义的。类问题，泛泛地谈算法是没有意义的。算法的概念(第一课时)设计好有限加确切的解题步骤设计好有限加确切的解题步骤排列出基本且可行的程序过程排列出基本且可行的程序过程算法思想算法思想