算法与程序框图课件-002.ppt

1、算法自古就有，中国古算法自古就有，中国古代数学在世界数学史上一度代数学在世界数学史上一度占居领先地位她注重实际占居领先地位她注重实际问题的解决，以算法为中心，问题的解决，以算法为中心，寓理于算，其中蕴涵了丰富寓理于算，其中蕴涵了丰富的算法思想。算筹是中国古代的计算工具，在的算法思想。算筹是中国古代的计算工具，在春秋时期已经很普遍，算盘在明代开始盛行。春秋时期已经很普遍，算盘在明代开始盛行。算法的数学史算法的数学史中国古代涌现了许多著名的数学家，如中国古代涌现了许多著名的数学家，如三国、两晋的赵爽、刘徽，南北朝的祖冲之、三国、两晋的赵爽、刘徽，南北朝的祖冲之、祖暅父子，宋、元的秦九韶、杨辉、朱世

2、杰祖暅父子，宋、元的秦九韶、杨辉、朱世杰等。等。著名的数学专著有著名的数学专著有九章算术九章算术、周周髀算经髀算经、黄帝九章算法细草黄帝九章算法细草、和、和杨杨辉算法辉算法等等随着计算科学和信息技术的飞速发展，算随着计算科学和信息技术的飞速发展，算法思想已经渗透到社会的方方面在以前的学法思想已经渗透到社会的方方面在以前的学习中，虽然没有出现算法这个名词，但实际上习中，虽然没有出现算法这个名词，但实际上在数学学习中已经渗透了大量的算法思想，如在数学学习中已经渗透了大量的算法思想，如四则运算的过程、求解方程的步骤等等完成四则运算的过程、求解方程的步骤等等完成这些工作都需要一系列程序化这些工作都需要

3、一系列程序化的步骤，这就是算法的思想的步骤，这就是算法的思想 一、解二元一次方程组一、解二元一次方程组并写出具体求解步骤并写出具体求解步骤 1212yxyx解解，得：，得：51 x第第2步：步：解解，得：，得：53 y第第4步：步：2，得：，得：35 y第第3步：步：2，得：，得：15 x第第1步：步：数学中的算法数学中的算法得到方程组的解为得到方程组的解为 5331yx第第5步：步：二、对于一般的二元一次方程组二、对于一般的二元一次方程组01221 baba您能写出一般的求解步骤么您能写出一般的求解步骤么?,(2)(1)222111 cybxa cybxa解解(4)得：得：12211221b

4、abacacay 第第4步：步：:)1()2(21aa )4()(12211221 cacaybaba 第第3步：步：解解(3)得：得：12212112babacbcbx 第第2步：步：:)2()1(12bb )3()(21121221 cbcbxbaba 第第1步：步：得到方程组的解为：得到方程组的解为：1221122112212112babacacaybabacbcbx第第5步：步：得到方程组的解为：得到方程组的解为：1221122112212112babacacaybabacbcbx第第5步：步：第一步第一步:农夫带羊过河农夫带羊过河;第二步第二步:农夫独自回来农夫独自回来;第三步第三步

5、:农夫带狼过河农夫带狼过河;一个一个 带着一条带着一条 、一头、一头 和一篮和一篮要过河，但只有一条小船。乘船时，农夫只能要过河，但只有一条小船。乘船时，农夫只能带一样东西。当农夫在场的时候，这三样东西相安带一样东西。当农夫在场的时候，这三样东西相安无事。一旦农夫不在，狼会吃羊，羊会吃菜。农夫无事。一旦农夫不在，狼会吃羊，羊会吃菜。农夫如何安全地将这三样东西带过河？如何安全地将这三样东西带过河？生活中的算法生活中的算法第四步：农夫带羊回来；第四步：农夫带羊回来；第五步：农夫带蔬菜过河；第五步：农夫带蔬菜过河；第六步：农夫独自回来；第六步：农夫独自回来；第七步：农夫带羊过河。第七步：农夫带羊过河

6、。一个一个 带着一条带着一条 、一头、一头 和一篮和一篮 要过河要过河,但只有一条小船但只有一条小船.乘船时乘船时,农夫只能带一农夫只能带一样东西样东西.当农夫在场的时候当农夫在场的时候,这三样东西相安无事这三样东西相安无事.一一旦农夫不在旦农夫不在,狼会吃羊狼会吃羊,羊会吃菜羊会吃菜.农夫如何安全地将农夫如何安全地将这三样东西带过河？这三样东西带过河？一、研读教材一、研读教材P2P31.算法的概念及其理解；算法的概念及其理解；2.算法的基本特征；算法的基本特征；算法算法的的基本特征：基本特征：有序性、明确性、有限性等有序性、明确性、有限性等.算法算法(algorithm)，通常指按照通常指按

7、照一定规则一定规则解决解决某一类问题某一类问题的的明确的明确的和和有限的有限的步骤。步骤。现在，算法通常可以编成计算机程序，让现在，算法通常可以编成计算机程序，让计算机执行并解决问题计算机执行并解决问题二、算法的概念及特征二、算法的概念及特征运用运用1.1.下列的步骤能否成为算法下列的步骤能否成为算法?(1)判断判断7是否为质数是否为质数;算法分析算法分析:因为因为7不能写成不能写成2到到6之间的两之间的两个质数的积个质数的积,所以所以7是质数是质数.(2)求求1+2+100的算法；的算法；算法分析：第一步：计算算法分析：第一步：计算1+2+100 第二步：输出第一步中的结果第二步：输出第一步

8、中的结果(3)判断判断2009是否为质数是否为质数算法分析：算法分析：第第1步：用步：用2除除2009，得到余数为，得到余数为1，所以，所以2不能不能整除整除2009；第第2步：用步：用3除除2009，得到余数为，得到余数为2，所以，所以3不能不能整除整除2009；第第2007步：用步：用2008除除2009，得到余数为，得到余数为1，所，所以以2008不能整除不能整除2009，因此，因此2009是质数。是质数。运用运用2.2.理解下列算法，回答相关问题：理解下列算法，回答相关问题：已知算法：第一步：输入已知算法：第一步：输入x;第二步：计算第二步：计算y1=f(x)第三步：计算第三步：计算y

9、2=g(x)第四步：若第四步：若y1 2)是是否为质数否为质数”的算法吗？的算法吗？探究探究1：只能被只能被1和它本身整除的大于和它本身整除的大于1的整数叫质数。的整数叫质数。(1)设计一个算法，判断设计一个算法，判断7是否为质数。是否为质数。探究探究1：只能被只能被1和它本身整除的大于和它本身整除的大于1的整数叫质数。的整数叫质数。算法分析：算法分析：判断一个大于判断一个大于1的整数的整数n是否为质是否为质数，用比这个整数小比数，用比这个整数小比1大的数去除大的数去除n，如果不能，如果不能整除，则整除，则n就是质数就是质数.(1)设计一个算法，判断设计一个算法，判断7是否为质数。是否为质数。

10、探究探究1：只能被只能被1和它本身整除的大于和它本身整除的大于1的整数叫质数。的整数叫质数。算法分析：算法分析：判断一个大于判断一个大于1的整数的整数n是否为质是否为质数，用比这个整数小比数，用比这个整数小比1大的数去除大的数去除n，如果不能，如果不能整除，则整除，则n就是质数就是质数.第一步：用第一步：用2除除7，得余数为，得余数为1，所以，所以2不能整除不能整除7。(1)设计一个算法，判断设计一个算法，判断7是否为质数。是否为质数。探究探究1：只能被只能被1和它本身整除的大于和它本身整除的大于1的整数叫质数。的整数叫质数。算法分析：算法分析：判断一个大于判断一个大于1的整数的整数n是否为质

11、是否为质数，用比这个整数小比数，用比这个整数小比1大的数去除大的数去除n，如果不能，如果不能整除，则整除，则n就是质数就是质数.第一步：用第一步：用2除除7，得余数为，得余数为1，所以，所以2不能整除不能整除7。第二步：用第二步：用3除除7，得余数为，得余数为1，所以，所以3不能整除不能整除7。(1)设计一个算法，判断设计一个算法，判断7是否为质数。是否为质数。探究探究1：只能被只能被1和它本身整除的大于和它本身整除的大于1的整数叫质数。的整数叫质数。算法分析：算法分析：判断一个大于判断一个大于1的整数的整数n是否为质是否为质数，用比这个整数小比数，用比这个整数小比1大的数去除大的数去除n，如

12、果不能，如果不能整除，则整除，则n就是质数就是质数.第一步：用第一步：用2除除7，得余数为，得余数为1，所以，所以2不能整除不能整除7。第二步：用第二步：用3除除7，得余数为，得余数为1，所以，所以3不能整除不能整除7。第三步：用第三步：用4除除7，得余数为，得余数为3，所以，所以4不能整除不能整除7。(1)设计一个算法，判断设计一个算法，判断7是否为质数。是否为质数。探究探究1：只能被只能被1和它本身整除的大于和它本身整除的大于1的整数叫质数。的整数叫质数。算法分析：算法分析：判断一个大于判断一个大于1的整数的整数n是否为质是否为质数，用比这个整数小比数，用比这个整数小比1大的数去除大的数去

13、除n，如果不能，如果不能整除，则整除，则n就是质数就是质数.第一步：用第一步：用2除除7，得余数为，得余数为1，所以，所以2不能整除不能整除7。第二步：用第二步：用3除除7，得余数为，得余数为1，所以，所以3不能整除不能整除7。第三步：用第三步：用4除除7，得余数为，得余数为3，所以，所以4不能整除不能整除7。第四步：用第四步：用5除除7，得余数为，得余数为2，所以，所以5不能整除不能整除7。(1)设计一个算法，判断设计一个算法，判断7是否为质数。是否为质数。探究探究1：只能被只能被1和它本身整除的大于和它本身整除的大于1的整数叫质数。的整数叫质数。算法分析：算法分析：判断一个大于判断一个大于

14、1的整数的整数n是否为质是否为质数，用比这个整数小比数，用比这个整数小比1大的数去除大的数去除n，如果不能，如果不能整除，则整除，则n就是质数就是质数.第一步：用第一步：用2除除7，得余数为，得余数为1，所以，所以2不能整除不能整除7。第二步：用第二步：用3除除7，得余数为，得余数为1，所以，所以3不能整除不能整除7。第三步：用第三步：用4除除7，得余数为，得余数为3，所以，所以4不能整除不能整除7。第四步：用第四步：用5除除7，得余数为，得余数为2，所以，所以5不能整除不能整除7。第五步：用第五步：用6除除7，得余数为，得余数为1，所以，所以6不能整除不能整除7。(1)设计一个算法，判断设计

15、一个算法，判断7是否为质数。是否为质数。探究探究1：只能被只能被1和它本身整除的大于和它本身整除的大于1的整数叫质数。的整数叫质数。算法分析：算法分析：判断一个大于判断一个大于1的整数的整数n是否为质是否为质数，用比这个整数小比数，用比这个整数小比1大的数去除大的数去除n，如果不能，如果不能整除，则整除，则n就是质数就是质数.第一步：用第一步：用2除除7，得余数为，得余数为1，所以，所以2不能整除不能整除7。第二步：用第二步：用3除除7，得余数为，得余数为1，所以，所以3不能整除不能整除7。第三步：用第三步：用4除除7，得余数为，得余数为3，所以，所以4不能整除不能整除7。第四步：用第四步：用

16、5除除7，得余数为，得余数为2，所以，所以5不能整除不能整除7。第五步：用第五步：用6除除7，得余数为，得余数为1，所以，所以6不能整除不能整除7。因此，因此，7是质数是质数(1)设计一个算法，判断设计一个算法，判断7是否为质数。是否为质数。(2)设计一个算法，判断设计一个算法，判断35是否为质数。是否为质数。第一步：用第一步：用2除除35，得余数为，得余数为1，所以，所以2不能整除不能整除35。(2)设计一个算法，判断设计一个算法，判断35是否为质数。是否为质数。第一步：用第一步：用2除除35，得余数为，得余数为1，所以，所以2不能整除不能整除35。(2)设计一个算法，判断设计一个算法，判断

17、35是否为质数。是否为质数。第二步：用第二步：用3除除35，得余数为，得余数为2，所以，所以3不能整除不能整除35。第一步：用第一步：用2除除35，得余数为，得余数为1，所以，所以2不能整除不能整除35。(2)设计一个算法，判断设计一个算法，判断35是否为质数。是否为质数。第二步：用第二步：用3除除35，得余数为，得余数为2，所以，所以3不能整除不能整除35。第三步：用第三步：用4除除35，得余数为，得余数为3，所以，所以4不能整除不能整除35。第一步：用第一步：用2除除35，得余数为，得余数为1，所以，所以2不能整除不能整除35。(2)设计一个算法，判断设计一个算法，判断35是否为质数。是否

18、为质数。第二步：用第二步：用3除除35，得余数为，得余数为2，所以，所以3不能整除不能整除35。第三步：用第三步：用4除除35，得余数为，得余数为3，所以，所以4不能整除不能整除35。第四步：用第四步：用5除除35，得余数为，得余数为0，所以，所以5能整除能整除35。第一步：用第一步：用2除除35，得余数为，得余数为1，所以，所以2不能整除不能整除35。(2)设计一个算法，判断设计一个算法，判断35是否为质数。是否为质数。第二步：用第二步：用3除除35，得余数为，得余数为2，所以，所以3不能整除不能整除35。第三步：用第三步：用4除除35，得余数为，得余数为3，所以，所以4不能整除不能整除35

19、。第四步：用第四步：用5除除35，得余数为，得余数为0，所以，所以5能整除能整除35。因此，因此，35不是质数不是质数.（3）您能写出您能写出“判断整数判断整数n(n 2)是否为是否为质数质数”的算法么？的算法么？第一步：给定大于第一步：给定大于2的整数的整数n。第二步：令第二步：令 i=2第三步：用第三步：用i除除n，得余数，得余数r判断余数判断余数r是是否为否为0，若是，则，若是，则n不是质数，结束算法；否不是质数，结束算法；否则，将则，将i的值增加的值增加1，仍用，仍用i表示这个数。表示这个数。第四步：判断第四步：判断i是否大于是否大于n 1，若是，则，若是，则n是质数；否则，返回第三步

20、。是质数；否则，返回第三步。探究探究2.2.写出用写出用“二分法二分法”求方程求方程x2-2=0(x 0)的近似解的算法。的近似解的算法。“一分为二一分为二”为区间为区间，根据，根据是否，找出零点所在的区间，仍记做是否，找出零点所在的区间，仍记做对所得的区间对所得的区间重复以上步骤，直到包含零点的区间重复以上步骤，直到包含零点的区间“足够小足够小”，那，那么此区间么此区间内的数即为方程的近似解内的数即为方程的近似解二分法：把满足二分法：把满足的函数的函数的零点所在的区间的零点所在的区间0)()(bfaf)(xf,ba,bmma0)()(mfaf,ba,ba,ba“一分为二一分为二”为区间为区间

21、，根据，根据是否，找出零点所在的区间，仍记做是否，找出零点所在的区间，仍记做对所得的区间对所得的区间重复以上步骤，直到包含零点的区间重复以上步骤，直到包含零点的区间“足够小足够小”，那，那么此区间么此区间内的数即为方程的近似解内的数即为方程的近似解二分法：把满足二分法：把满足的函数的函数的零点所在的区间的零点所在的区间0)()(bfaf)(xf,ba,bmma0)()(mfaf,ba,ba,ba第一步：令第一步：令,2)(2 xxf给定精确度给定精确度d第三步：取区间中点第三步：取区间中点2bam .,ba含零点的区间为含零点的区间为.,bm第四步：若第四步：若()()0,f af m则含零点

22、的区间为则含零点的区间为;,ma否则，否则，将新得到的含零点的区间仍记为将新得到的含零点的区间仍记为第二步：确定区间第二步：确定区间满足满足0)()(bfaf,ba第五步：判断第五步：判断,ba的长度是否小于的长度是否小于d或或f(m)是否等于是否等于0若是，则若是，则m是方程的近似值；否则，返回第三步是方程的近似值；否则，返回第三步第一步：令第一步：令,2)(2 xxf给定精确度给定精确度d第一步：令第一步：令,2)(2 xxf给定精确度给定精确度d第三步：取区间中点第三步：取区间中点2bam 第三步：取区间中点第三步：取区间中点2bam .,ba含零点的区间为含零点的区间为.,bm第四步：

23、若第四步：若()()0,f af m则含零点的区间为则含零点的区间为;,ma否则，否则，将新得到的含零点的区间仍记为将新得到的含零点的区间仍记为.,ba含零点的区间为含零点的区间为.,bm含零点的区间为含零点的区间为.,bm第四步：若第四步：若()()0,f af m则含零点的区间为则含零点的区间为;,ma否则，否则，将新得到的含零点的区间仍记为将新得到的含零点的区间仍记为第四步：若第四步：若()()0,f af m则含零点的区间为则含零点的区间为;,ma否则，否则，将新得到的含零点的区间仍记为将新得到的含零点的区间仍记为第二步：确定区间第二步：确定区间满足满足0)()(bfaf,ba第二步：确定区间第二步：确定区间满足满足0)()(bfaf,ba第五步：判断第五步：判断,ba的长度是否小于的长度是否小于d或或f(m)是否等于是否等于0若是，则若是，则m是方程的近似值；否则，返回第三步是方程的近似值；否则，返回第三步第五步：判断第五步：判断,ba的长度是否小于的长度是否小于d或或f(m)是否等于是否等于0若是，则若是，则m是方程的近似值；否则，返回第三步是方程的近似值；否则，返回第三步写出用写出用“二分法二分法”求方程求方程近似解的算法近似解的算法)0(022 xx算法在设计中大致分几个步骤？算法在设计中大致分几个步骤？考向标考向标P-P