人教版高中数学必修三算法的概念课件.ppt

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

2、杰等等.著名的数学专著有著名的数学专著有九九章算术章算术、周髀算经周髀算经、数书九章数书九章、四元玉鉴四元玉鉴、黄帝九章算法细草黄帝九章算法细草、议古根源议古根源、数书九章数书九章、详解九章算法详解九章算法和和杨辉算法杨辉算法等等内容简介内容简介章头图体现了中国古代数学与现代计算机科章头图体现了中国古代数学与现代计算机科学的联系，它们的基础都是学的联系，它们的基础都是“算法算法”。问题：问题：一个农夫带着一只狼、一头山羊和一篮蔬菜要过河，一个农夫带着一只狼、一头山羊和一篮蔬菜要过河，但只有一条小船。乘船时但只有一条小船。乘船时,农夫只能带一样东西。农夫只能带一样东西。当农夫在场的时候当农夫在场

3、的时候,这三样东西相安无事，一旦农这三样东西相安无事，一旦农夫不在，狼会吃羊，羊会吃菜。请设计一个方案，夫不在，狼会吃羊，羊会吃菜。请设计一个方案，使农夫能安全地将这三样东西带过河。使农夫能安全地将这三样东西带过河。S1:S1:农夫带羊过河农夫带羊过河;S2:S2:农夫独自回来农夫独自回来;S3:S3:农夫带狼过河农夫带狼过河;S4:S4:农夫带羊回来农夫带羊回来;S5:S5:农夫带蔬菜过河农夫带蔬菜过河;S6:S6:农夫独自回来农夫独自回来;S7:S7:农夫带羊过河。农夫带羊过河。广义地说，广义地说，算法就是做某一件事的步算法就是做某一件事的步骤或程序骤或程序。菜谱是做菜肴的算法，洗衣。菜谱

4、是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。歌谱是一首歌曲的算法。在数学中，在数学中，主要研究计算机能实现的主要研究计算机能实现的算法算法，即按照某种机械程序步骤一定可，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。比如解以得到结果的解决问题的程序。比如解方程的算法、函数求值的算法、作图的方程的算法、函数求值的算法、作图的算法，等等。算法，等等。怎样才能设计出一个名副其实的算法呢？面对一个需要解决的问题?如何设计解决问题的操作步骤?怎样用数学语言描述这些操作序列?问问1:1:解二元一次方程组解二元一次方程组 的具体步骤

5、是什么？的具体步骤是什么？知识探究（一）：算法的概念知识探究（一）：算法的概念1212yxyx +2 2，得得 5 5x=1.=1.解解，得得 .15x -2 2，得得 5 5y3 3.解解，得得 .35y 第一步：第一步：第二步：第二步：第三步：第三步：第四步：第四步：第五步：第五步：1212yxyx 得到方程组的解为得到方程组的解为 .15x 35y 人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)问问2:2:参照上述思路参照上述思路,一般地一般地,解方程组解方程组 的基本步骤是

6、什么？的基本步骤是什么？111a xb yc222a xb yc1 22 10aba b（）人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)第一步：第一步：解解，得得2 11 21 22 1b cbcxa ba b -，得得1a2a1 22 11 22 1()aba b ya ca c解解，得得1 22 11 22 1a ca cya ba b得到方程组的解为得到方程组的解为 2112122112211221b cbcxa ba ba ca cya ba b2b1b -，得得 1 2

7、2 12 11 2()aba b xb cbc第二步：第二步：第三步：第三步：第四步：第四步：第五步：第五步：人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)根据上述分析，用加减消元法解二元根据上述分析，用加减消元法解二元一次方程组，可以分为五个步骤进行，一次方程组，可以分为五个步骤进行，这五个步骤就构成了解二元一次方程组这五个步骤就构成了解二元一次方程组的一个的一个“算法算法”.我们再根据这一算法编我们再根据这一算法编制计算机程序，就可以让计算机来解二制计算机程序，就可以让计算机来

8、解二元一次方程组元一次方程组.人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)你能归纳出你能归纳出算法算法的概念吗？的概念吗？在数学中，按照一定规则解决某一在数学中，按照一定规则解决某一类问题的明确和有限的步骤类问题的明确和有限的步骤称为算法称为算法.1.1.算法定义算法定义：人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)思考思考:一般地，一般地，算法算法是由按照一定规则

9、解是由按照一定规则解决某一类问题的基本步骤组成的决某一类问题的基本步骤组成的.你认为：你认为：(1)(1)这些步骤的个数是有限的还是无限这些步骤的个数是有限的还是无限 的？的？(2)(2)每个步骤是否有明确的计算任务？每个步骤是否有明确的计算任务？人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)思考思考:有人对哥德巴赫猜想有人对哥德巴赫猜想“任何大于任何大于4 4的偶的偶数都能写成两个质数之和数都能写成两个质数之和”设计了如下操作设计了如下操作步骤：步骤：第一步，检验第一步，检验6=

10、3+36=3+3，第二步，检验第二步，检验8=3+58=3+5，第三步，检验第三步，检验10=5+510=5+5，利用计算机无穷地进行下去！利用计算机无穷地进行下去！请问：这是一个算法吗？请问：这是一个算法吗？人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)第一步第一步：用：用2 2除除7 7，得到余数，得到余数1,1,所以所以2 2不能整除不能整除7.7.第二步第二步：用：用3 3除除7 7，得到余数，得到余数1,1,所以所以3 3不能整除不能整除7.7.例例1:1:设计一个算法，

11、判断设计一个算法，判断7 7是否为质数？是否为质数？第三步第三步：用：用4 4除除7 7，得到余数，得到余数3,3,所以所以4 4不能整除不能整除7.7.第四步第四步：用：用5 5除除7 7，得到余数，得到余数2,2,所以所以5 5不能整除不能整除7.7.第五步第五步：用：用6 6除除7 7，得到余数，得到余数1,1,所以所以6 6不能整除不能整除7.7.因此，因此，7 7是质数是质数.知识探究（二）知识探究（二）:算法的步骤设计算法的步骤设计人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张

12、PPT)例例2:2:设计一个算法，判断设计一个算法，判断3535是否为质数？是否为质数？第一步第一步：用：用2 2除除3535，得到余数，得到余数1,1,所以所以2 2不能整除不能整除35.35.第二步第二步：用：用3 3除除3535，得到余数，得到余数2,2,所以所以3 3不能整除不能整除35.35.第三步第三步：用：用4 4除除3535，得到余数，得到余数3,3,所以所以4 4不能整除不能整除35.35.第四步第四步：用：用5 5除除3535，得到余数，得到余数0,0,所以所以5 5能整除能整除35.35.因此，因此，3535不是质数不是质数.人教版高中数学必修三第一章第1节 1.1.1

13、算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)思考思考:整数整数8989是否为质数？如果让计算机是否为质数？如果让计算机判断判断8989是否为质数，按照上述算法需要是否为质数，按照上述算法需要设计多少个步骤？设计多少个步骤？第一步第一步，用，用2 2除除8989，得到余数，得到余数1,1,所以所以2 2不能整除不能整除89.89.第二步第二步，用，用3 3除除8989，得到余数，得到余数2,2,所以所以3 3不能整除不能整除89.89.第三步第三步，用，用4 4除除8989，得到余数，得到余数1,1,所以所以4 4不能整除不能

14、整除89.89.第八十七步第八十七步，用，用8888除除8989，得到余数，得到余数1,1,所以所以8888不能不能 整除整除89.89.因此，因此，8989是质数是质数.人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)思考思考:用用2 28888逐一去除逐一去除8989求余数，需要求余数，需要8787个个步骤，这些步骤基本是重复操作，我们可以步骤，这些步骤基本是重复操作，我们可以按下面的思路改进这个算法，减少算法的步按下面的思路改进这个算法，减少算法的步骤骤.（1 1）用）用i i

15、表示表示2 28888中的任意一个整数，并从中的任意一个整数，并从2 2开始取数；开始取数；（2 2）用）用i i除除8989，得到余数，得到余数r.r.若若r=0r=0，则，则8989不不是质数；若是质数；若r0r0，将，将i i用用i+1i+1替代，再执行同替代，再执行同样的操作；样的操作；（3 3）这个操作一直进行到）这个操作一直进行到i i取取8888为止为止.你能按照这个思路，设计一个你能按照这个思路，设计一个“判断判断8989是否是否为质数为质数”的算法步骤吗？的算法步骤吗？人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第

16、1节 1.1.1 算法的概念 课件(共26张PPT)用用i i除除8989，得到余数，得到余数r r；令令i=2i=2；若若r=0r=0，则，则8989不是质数，结束算不是质数，结束算法；若法；若r0r0，将，将i i用用i+1i+1替代；替代；判断判断“i i88”88”是否成立？若是，是否成立？若是，则则8989是质数，结束算法；否则，是质数，结束算法；否则，返回第二步返回第二步.第一步，第一步，第四步，第四步，第三步，第三步，第二步，第二步，算法设计算法设计:写出判断整数写出判断整数n(n2)2)是否为质数的算法是否为质数的算法第一步：第一步：给定一个大于给定一个大于2 2的整数的整数n

17、；令令i=2=2；第二步：第二步：第三步：第三步：用用i除除n，得到余数，得到余数r r；第四步：第四步：判断判断“r=0”r=0”是否成立是否成立.若是，则若是，则否则，将否则，将i的值增加的值增加1 1，仍用，仍用i表示；表示；第五步：第五步：判断判断“i(n-1)”-1)”是否成立，是否成立，若是，则若是，则否则，返回否则，返回n不是质数，结束算法；不是质数，结束算法；n是质数，结束算法；是质数，结束算法；第三步第三步.例例3.3.用二分法设计一个求方程用二分法设计一个求方程 x2-2=0（x0）的近似根的算法的近似根的算法.(.(精确度为精确度为0.005)0.005)第一步：第一步：

18、第二步：第二步：第三步：第三步：第四步：第四步：第五步：第五步：2()2f xx令令 ，给定精确度给定精确度d.确定区间确定区间 a，b，满足满足f(a)f(b)0.0.,2ab取区间中点取区间中点m 若若f(a)f(m)0,0,则含零点的区间为则含零点的区间为否则，含零点的区间为否则，含零点的区间为将新得到的含零点的区间仍记为将新得到的含零点的区间仍记为 a,b;判断判断|a-b|d是否成立是否成立或或f(m)是否等于是否等于0.0.若是，则若是，则m是方程的近似解；是方程的近似解；否则，返回否则，返回 a,m,m，b.第三步第三步.理论迁移理论迁移ab|a-b|1 12 21 11 11.

19、51.50.50.51.251.251.51.50.250.251.3751.3751.51.50.1250.1251.3751.3751.437 51.437 50.062 50.062 51.406 251.406 251.437 51.437 50.031 250.031 251.406 251.406 251.421 8751.421 8750.015 6250.015 6251.414 6251.414 6251.421 8751.421 8750.007 812 50.007 812 51.414 062 51.414 062 51.417 968 751.417 968 750.

20、003 906 250.003 906 25对于方程对于方程 ,给定给定d=0.005.d=0.005.220(0)xx此步骤也是求的近似值的一个算法此步骤也是求的近似值的一个算法.22.2.算法的基本特征算法的基本特征:确定性确定性:算法中的每一步都应该是确算法中的每一步都应该是确定的定的,并且能有效地执行且得到确定并且能有效地执行且得到确定的结果的结果.有限性有限性:一个算法的步骤序列是有限一个算法的步骤序列是有限的它应在有限步操作之后停止，而不能的它应在有限步操作之后停止，而不能是无限的是无限的有序性有序性:算法从初始步骤开始，分为若干明算法从初始步骤开始，分为若干明确的步骤，每一个步骤

21、只能有一个确定的后继确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只有执行完前步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，并且每一步都准确无误，一步才能进行下一步，并且每一步都准确无误，才能解决问题才能解决问题不唯一性不唯一性:求解某一个问题的算法不一定是求解某一个问题的算法不一定是唯一的，对于一个问题可以有不同的算法唯一的，对于一个问题可以有不同的算法普遍性普遍性:很多具体的问题，都可以设计合很多具体的问题，都可以设计合理的算法去解决理的算法去解决人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第

22、1节 1.1.1 算法的概念 课件(共26张PPT)教材教材5 5页练习页练习2:2:任意给定一个大于任意给定一个大于1 1的正整数的正整数n，设计一个算法求出，设计一个算法求出n的所有因数的所有因数.第一步：第一步：第二步：第二步：第三步：第三步：依次用依次用2（n 1）除）除 n，检查余数是否为检查余数是否为0；若是，则是若是，则是 n 的因数；的因数；若不是，则不是若不是，则不是 n 的因数；的因数；在在 n 的因数中加入的因数中加入 1 和和 n；输出输出n的所有因数的所有因数.人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第

23、1节 1.1.1 算法的概念 课件(共26张PPT)练习练习3:3:写出过写出过P(P(a1 1,b1 1)、Q(a2,b2)两点直线两点直线斜率的算法：斜率的算法：第一步：第一步：第二步：第二步：第三步：第三步：取取x1 1=a1 1，y1 1=b b1 1，x2 2=a2 2，y2 2=b b2 2；若若x1 1=x2 2,输出斜率不存在；输出斜率不存在；若若x1 1x2 2,计算计算2121;yykxx第四步：第四步：输出结果。输出结果。人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张

24、PPT)小结作业小结作业 算法是建立在解法基础上的操作过程，算法算法是建立在解法基础上的操作过程，算法不一定要有运算结果，问题答案可以由计算机解不一定要有运算结果，问题答案可以由计算机解决设计一个解决某类问题的算法的核心内容是决设计一个解决某类问题的算法的核心内容是设计算法的步骤，它没有一个固定的模式，但有设计算法的步骤，它没有一个固定的模式，但有以下几个基本要求：以下几个基本要求：(1)(1)符合运算规则，计算机能操作；符合运算规则，计算机能操作；(2)(2)每个步骤都有一个明确的计算任务每个步骤都有一个明确的计算任务；(4)(4)步骤个数尽可能少步骤个数尽可能少；(5)(5)每个步骤的语言描述要准确、简明每个步骤的语言描述要准确、简明.(3)(3)对重复操作步骤作返回处理对重复操作步骤作返回处理；人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)人教版高中数学必修三第一章第1节 1.1.1 算法的概念 课件(共26张PPT)