人教高中数学必修三1.1.1算法的概念 课件(共29张PPT)

1、1.1.1 1.1.1 算法的概念算法的概念我国古代的计算工具我国古代的计算工具世界上第一台电子计算机世界上第一台电子计算机我国第一台电子计算机我国第一台电子计算机 算筹、算盘、计算机等从古到今的计算算筹、算盘、计算机等从古到今的计算工具的基础都是工具的基础都是“算法算法”.算法对我们而言并算法对我们而言并不陌生，其实我们从小学就开始接触算法，不陌生，其实我们从小学就开始接触算法，例如，做四则运算要先乘除后加减、从里往例如，做四则运算要先乘除后加减、从里往外去括号外去括号 、竖式笔算等都是算法，至于乘法、竖式笔算等都是算法，至于乘法口诀、珠算口诀更是算法的具体体现口诀、珠算口诀更是算法的具体体

2、现. 在现代社会里，计算机已经成为人们日常在现代社会里，计算机已经成为人们日常生活和工作不可缺少的工具听音乐、看电影、生活和工作不可缺少的工具听音乐、看电影、玩游戏、画卡通画、处理数据玩游戏、画卡通画、处理数据计算机几乎可计算机几乎可以是一个全能的助手，你可以用它来做你想做以是一个全能的助手，你可以用它来做你想做的任何事情那么，计算机是怎样工作呢？要的任何事情那么，计算机是怎样工作呢？要想弄清楚这个问题，就需要学习算法想弄清楚这个问题，就需要学习算法 l第一步：把冰箱门打开l第二步：把大象放进去l第三步：把冰箱门带上情境情境2：农夫过河问题农夫过河问题 有一个农夫带三只狼和三只羚羊过河，只有一

3、条船，有一个农夫带三只狼和三只羚羊过河，只有一条船，同船可以容纳一个人和两只动物。没有人在的时候，如果同船可以容纳一个人和两只动物。没有人在的时候，如果狼的数量不少于羚羊的数量，狼就会吃掉羚羊狼的数量不少于羚羊的数量，狼就会吃掉羚羊。农夫应农夫应该如何渡河？该如何渡河？河河 流流如何求解二元一次方程组？如何求解二元一次方程组？ 回顾回顾二元一次方程组二元一次方程组 12 12yxyx的求解过程的求解过程. 归纳它的步骤归纳它的步骤:第一步第一步: -2，得，得 5y=3 第三步第三步:5153xy，得代入将第二步第二步: 解得解得 y= 53第二步第二步: 解得解得 y= 53思考？0 122

4、1222111babacybxacybxa其中一般的二元一次方程组第二步：解，得第二步：解，得12211221babacacay第一步：第一步： - - ，得，得 1a2a12211221)(cacaybaba第三步：将第三步：将 代入代入，得，得12211221babacacay12212112babacbcbx 我们做每件事情都需要设计出我们做每件事情都需要设计出“行动步行动步骤骤”. 上述上述步骤构成了解二元一次方程组的算法，步骤构成了解二元一次方程组的算法，我们可以进一步根据这一算法编制计算机程我们可以进一步根据这一算法编制计算机程序，让计算机来解二元一次方程组序，让计算机来解二元一次

5、方程组.1.1.算法的概念：算法的概念：在数学中在数学中“算法算法”通常是指按照一定的规则来通常是指按照一定的规则来解决的某一类问题的解决的某一类问题的明确明确和和有限有限的的步骤步骤。3.3.算法的基本思想与特征算法的基本思想与特征: :2.2.算法的表示方法：算法的表示方法： 自然语言、程序框图、程序语言自然语言、程序框图、程序语言(1)解决某一类问题解决某一类问题(2)在在有限步有限步之内完成之内完成(3)每一步都是明确的，有确定的结果和有效性每一步都是明确的，有确定的结果和有效性(4)每一步具有顺序每一步具有顺序(5)解决问题的算法不唯一解决问题的算法不唯一(普遍性普遍性)(有限性有限

6、性)(确定性与可行性确定性与可行性)(有有序性序性)(不唯不唯一一性性)练习练习判断下列关于算法的说法是否确：判断下列关于算法的说法是否确：1、求解某一类问题的算法是唯一的；、求解某一类问题的算法是唯一的；2、算法必须在有限步操作之后停止；、算法必须在有限步操作之后停止；3、算法的每一步必须是明确的，不能有歧、算法的每一步必须是明确的，不能有歧义或模糊；义或模糊；4、算法执行后一定产生确定的结果、算法执行后一定产生确定的结果.练习练习判断下列关于算法的说法是否确：判断下列关于算法的说法是否确：1、求解某一类问题的算法是唯一的；、求解某一类问题的算法是唯一的；2、算法必须在有限步操作之后停止；、

7、算法必须在有限步操作之后停止；3、算法的每一步必须是明确的，不能有歧、算法的每一步必须是明确的，不能有歧义或模糊；义或模糊；4、算法执行后一定产生确定的结果、算法执行后一定产生确定的结果.例题例题1(2).设计一个算法，判断设计一个算法，判断35是否为质数？是否为质数？(1).设计一个算法，判断设计一个算法，判断7是否为质数？是否为质数？只能被只能被1 1和自身整除的大于和自身整除的大于1 1的整数叫质数的整数叫质数. .例题例题1(1).设计一个算法，判断设计一个算法，判断7是否为质数？是否为质数？解：解： 算法分析：算法分析：由质数的定义，可以这样判断由质数的定义，可以这样判断:依次用依次

8、用26除除7,若它们中有一个能整除若它们中有一个能整除7，则，则7不是质数，否则不是质数，否则7是质数是质数.根据以上分析，可以写出如下的算法：根据以上分析，可以写出如下的算法：第一步第一步,用用2除除7,余数不为余数不为0, 第二步第二步,用用3除除7,余数不为余数不为0, 得到余数得到余数1.2不能整除不能整除7.得到余数得到余数1.3不能整除不能整除7.第三步第三步,用用4除除7,余数不为余数不为0, 得到余数得到余数3.4不能整除不能整除7.第四步第四步,用用5除除7,余数不为余数不为0, 得到余数得到余数2.5不能整除不能整除7.第五步第五步,用用6除除7,余数不为余数不为0, 得到

9、余数得到余数1.6不能整除不能整除7.故故7是质数是质数.例题例题1(2).设计一个算法，判断设计一个算法，判断35是否为质数？是否为质数？解：解： 根据以上分析，可以写出如下的算法：根据以上分析，可以写出如下的算法：第一步第一步,用用2除除35,余数不为余数不为0, 第二步第二步,用用3除除35,余数不为余数不为0, 得到余数得到余数1.2不能整除不能整除35.得到余数得到余数2.3不能整除不能整除35.第三步第三步,用用4除除35,余数不为余数不为0, 得到余数得到余数3.4不能整除不能整除35.第四步第四步,用用5除除35,余数为余数为0, 得到余数得到余数0.5能整除能整除35.故故3

10、5不是质数不是质数.探究：探究：你能写出你能写出“判断整数判断整数n(n2)是否为质数是否为质数”的算法吗？的算法吗？ 【算法分析算法分析】对于对于任意任意的整数的整数n(n2)，若用，若用i表示表示2(n-1)中的任中的任意整数，则意整数，则“判断判断n是否为质数是否为质数”的算法包含下面的算法包含下面的重复操作：的重复操作：用用i除除n，得到余数，得到余数r，判断余数，判断余数r是否为是否为0，若为若为0，则，则n不是质数，否则将不是质数，否则将i 的值增加的值增加1，再执行同样的操作，一直到再执行同样的操作，一直到i的值等于的值等于n-1为止为止.写出写出“判断整数判断整数n(n2)是否

11、为质数是否为质数”的算法。的算法。 解：解：第一步：给定大于第一步：给定大于2的整数的整数n；第二步：令第二步：令i=2；第三步：用第三步：用i除除n，得到余数，得到余数r；第四步：判断第四步：判断“r=0”是否成立，若是，则是否成立，若是，则n不是不是质数，结束算法；否则，将质数，结束算法；否则，将i的值增加的值增加1，仍用，仍用i表表示；示；第五步，判断第五步，判断“in-1”是否成立，若成立，则是否成立，若成立，则n是是质数，结束算法；否则，返回第三步质数，结束算法；否则，返回第三步.写出写出“判断整数判断整数n(n2)是否为质数是否为质数”的算法。的算法。 分析：分析： 1二分法求方程

12、近似解是通过求对应函二分法求方程近似解是通过求对应函数的近似零点得到的，所以首先要建立数的近似零点得到的，所以首先要建立函数，而且要有具体精确度要求，因此函数，而且要有具体精确度要求，因此第一步应该怎么做？第一步应该怎么做？ 2二分法分的是什么？二分法分的是什么？ 3如何确定新区间的端点？如何确定新区间的端点？ 4如何表达出反复二分区间的过程？如何表达出反复二分区间的过程？ 例例2、用二分法设计一个求方程用二分法设计一个求方程x2-2=0的近的近似解的算法（精确度为似解的算法（精确度为0.005）. .什么是二分法？什么是二分法？对于区间对于区间a,b a,b 上连续不断、且上连续不断、且f(

13、a)f(b)0f(a)f(b)0)-2(x0)xa ab b|a-b|a-b|1 12 21 11 11.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 062 51.414 062 51.421 8751.421 8750.007 812 50.

14、007 812 51.414 062 51.414 062 51.417 968 751.417 968 750.003 906 250.003 906 25对于方程对于方程x x2 2-2=0(x0),-2=0(x0),给定给定d=0.005.d=0.005.此步骤也是求的近似值的一个算法此步骤也是求的近似值的一个算法. .2例例2、用二分法设计一个求方程用二分法设计一个求方程x2-2=0的近的近似根的算法（精确度为似根的算法（精确度为0.005）. .第一步：第一步：令令f(x)=x2-2，给定精确度，给定精确度d. ,0a bf af b第第二二步步：确确定定区区间间满满足足；;2abm

15、 第第三三步步：取取区区间间中中点点 0,.f af ma mmba b 第第四四步步：若若，则则含含零零点点的的区区间间为为否否则则为为，将将新新得得到到的的区区间间仍仍记记为为 ,0a bdf mm第第五五步步：判判断断区区间间的的长长度度是是否否小小于于 或或是是否否等等于于 ；若若是是，则则 即即为为所所求求方方程程的的近近似似解解，不不是是，则则返返回回第第三三步步。根据以上分析，可以写出如下的算法：根据以上分析，可以写出如下的算法： 1、任意给定一个正实数，设计一个算法求以、任意给定一个正实数，设计一个算法求以这个数为半径的圆的面积。这个数为半径的圆的面积。算法步骤：算法步骤：第一

16、步：给定一个正实数第一步：给定一个正实数 r.第二步：计算以第二步：计算以r为半径的圆的面积为半径的圆的面积 .2Sr 第三步：得到圆的面积第三步：得到圆的面积S.P5练习练习 2、任意给定一个大于、任意给定一个大于1的正整数的正整数n，设计一个算，设计一个算法求出法求出n的所有因数。的所有因数。算法步骤：算法步骤：第一步：给定一个大于第一步：给定一个大于1的正整数的正整数n. 第二步：令第二步：令i=1. （i表示表示1n中的任意整数）中的任意整数）.第三步：用第三步：用i除除n，得到余数，得到余数r.第四步：判断第四步：判断“r=0”是否成立，若是，则是否成立，若是，则i是是n的因数；的因

17、数；否则否则i不是不是n的因数的因数.第五步：将第五步：将i的值增加的值增加1，仍用，仍用i表示表示.第六步，判断第六步，判断“i n”是否成立，若是，则结束算法；是否成立，若是，则结束算法；否则，返回第三步否则，返回第三步.必修必修3 1.1.1 算法的概念算法的概念课后作业课后作业例例3. 写出一个求整数写出一个求整数a、b、c最大值的算法最大值的算法解：解：步骤一步骤一: max=a步骤二步骤二: 如果如果bmax，则，则max=b.步骤三步骤三: 如果如果cmax，则，则max=c.思考：思考：你能写出一个求有限整数列中的最大值的算法吗？你能写出一个求有限整数列中的最大值的算法吗？思考：思考：写出一个求有限整数列中的最大值的算法。写出一个求有限整数列中的最大值的算法。步骤一步骤一: :