09年高考数学算法的概念课件

1、山东省临沂第二中学高一数学组山东省临沂第二中学高一数学组普通高中课程标准实验教科书必修普通高中课程标准实验教科书必修算法与程序框图算法与程序框图 一人带着一只狼、一只羊和一箱蔬菜要过河一人带着一只狼、一只羊和一箱蔬菜要过河,但只但只有一条小船有一条小船.乘船时，每次只能带狼、羊和蔬菜中的一乘船时，每次只能带狼、羊和蔬菜中的一种种.当有人在场时，狼、羊、蔬菜都相安无事当有人在场时，狼、羊、蔬菜都相安无事.一旦人一旦人不在不在,狼会吃羊狼会吃羊,羊会吃菜羊会吃菜.请设计一个方案请设计一个方案,安全地将狼、安全地将狼、羊和蔬菜带过河羊和蔬菜带过河.过河游戏趣味益智游戏:,?,下下面面就就是是一一种种

2、操操作作步步骤骤发发邮邮件件的的方方法法很很多多你你能能教教会会他他吗吗子子邮邮件件假假如如你你的的朋朋友友不不会会发发电电;第一步登录电子信箱如何发电子邮件？;第二步点击 “写信”;第三步输入收件人地址;第四步输入主题;第五步输入信件内容第六步点击“发送”.,;,.,也也是是按按一一定定程程序序操操作作的的程程用用配配方方法法解解一一元元二二次次方方按按照照某某一一程程序序进进行行操操作作就就可可以以元元一一次次方方程程组组时时例例如如用用加加减减消消元元法法解解二二此此解解决决数数学学问问题题也也常常常常如如序序执执行行的的一一系系列列操操作作种种顺顺都都是是在在一一定定条条件件下下按按某

3、某我我们们做做任任何何一一件件事事山东省临沂第二中学 徐帮利 一般地一般地, ,对于一类问题的机械式地、统一对于一类问题的机械式地、统一地、按部就班地求解过程称为算法地、按部就班地求解过程称为算法(algorithm)(algorithm)它是解决某一问题的程序或步骤它是解决某一问题的程序或步骤. . 按照这样的理解按照这样的理解, ,我们可以设计出很多具我们可以设计出很多具体数学问题的算法体数学问题的算法. .下面看几个例子下面看几个例子: : 所谓所谓 “算法算法”就是解题方法的精确描述就是解题方法的精确描述.从更广义的角度来看从更广义的角度来看,并不是只有并不是只有“计算计算”的的问题才

4、有算法问题才有算法,日常生活中处处都有日常生活中处处都有.如如乐谱乐谱是是乐队演奏的算法乐队演奏的算法,菜谱菜谱是做菜肴的算法是做菜肴的算法,珠算口珠算口诀诀是使用算盘的算法是使用算盘的算法. 请你写出解下面二元一次方程组的详细过程请你写出解下面二元一次方程组的详细过程. 2121xyxy 第二步第二步, 解解得得1;5x 第三步第三步, - 2得得 5y=3; 第四步第四步, 解解得得3;5y 1,53.5xy第五步第五步, 得到方程组的解为得到方程组的解为第一步第一步, +2得得 5x=1; 解：做一做 你能你能写出解一般的二元一次方程组的步写出解一般的二元一次方程组的步 骤吗？骤吗？11

5、11 22 1222(1)0(2)a xb ycaba ba xb yc 第一步第一步,21(1)(2)bb得 ：12211221.a ba bxc bc b（ 3） 第二步第二步,解（解（3）得）得 12211221.c bc bxa ba b思考 2 11 22 11 2.ac acyab ab 第四步第四步,解（解（4）得）得 21(1)(2)aa得：第三步第三步,2 11 22 11 2.a bab ya cac（4） 第五步第五步,得到方程组的解为得到方程组的解为 1221122121122112,.c bc bxa ba ba ca cya ba b解解，得，得 21122112a

6、 ca cya ba b将将带入带入得得2a1a 得得111222a xb yca xb yc122 12 112b cb cxa ba b解解 得得51.x 第一步第一步：第二步：第二步：第三步：第三步：+ +2 2，得，得1.5x 21,21xyxy15x 将将 代入代入, ,得得3.5y 思考思考这这 两个解方程组的两个解方程组的算法算法的适用范围有何不同？的适用范围有何不同？第一步：第一步：第二步：第二步：第三步：第三步：2 1122 112()a ba bya ca c-1 22 1(0)aba b 事实上，我们可以将一般的二元一次方程组的解法转化成计算机语言，做成一个求解二元一次方

7、程组的程序.这儿已经做好了，试一试吧！这儿已经做好了，试一试吧！练习练习1. 给出求给出求1+2+3+4+5+6的一个算法的一个算法.解法解法1.1.按照逐一相加的程序进行按照逐一相加的程序进行. .第一步第一步:计算计算1+2,得得3;第二步第二步:将第一步中的运算结果将第一步中的运算结果3与与3相加得相加得6;第三步第三步:将第二步中的运算结果将第二步中的运算结果6与与4相加得相加得10;第四步第四步:将第三步中的运算结果将第三步中的运算结果10与与5相加得相加得15;第五步第五步:将第四步中的运算结果将第四步中的运算结果15与与6相加得相加得21.解法解法2.2.可以运用下面公式直接计算

8、可以运用下面公式直接计算. .(1)12342n nn 第一步第一步, ,取取 n = =6; ;第二步第二步, ,计算计算 ; ;2)1( nn第三步第三步, ,输出计算结果输出计算结果. .点评点评: :解法解法1 1繁琐繁琐, ,步骤较多步骤较多; ; 解法解法2 2简单，步简单，步骤较少骤较少. . 找出好的算法是我们的追求目标找出好的算法是我们的追求目标. .现在你对算法有了新现在你对算法有了新的认识了吗？的认识了吗？ 在数学中，算法通常是指按照一定规则在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤解决某一类问题的明确和有限的步骤.现在，现在，算法通常可以编成计算

9、机程序，让计算机执算法通常可以编成计算机程序，让计算机执行并解决问题行并解决问题.2.2.算法的要求算法的要求(1)写出的算法写出的算法,必须能解决一类问题必须能解决一类问题(例如解任例如解任意一个二元一次方程组意一个二元一次方程组),并且能重复使用并且能重复使用;(2) 算法过程要能一步一步执行算法过程要能一步一步执行,每一步执行的每一步执行的操作操作,必须确切必须确切,不能含混不清不能含混不清,而且在有限步之而且在有限步之内完成后能得出结果内完成后能得出结果.1.1.算法的定义算法的定义讲授新课3.3.算法的基本特征算法的基本特征: :明确性明确性: :算法对每一个步骤都有确切的、非二算法

10、对每一个步骤都有确切的、非二义性的规定义性的规定, ,即每一步对于利用算法解决问题的即每一步对于利用算法解决问题的人或计算机来说都是可读的、可执行的人或计算机来说都是可读的、可执行的, ,而不需而不需要计算者临时动脑筋要计算者临时动脑筋. . 有效性有效性: :算法的每一个步骤都能够通过基本运算法的每一个步骤都能够通过基本运算有效地进行算有效地进行, ,并得到确定的结果；对于相同的并得到确定的结果；对于相同的输入输入, ,无论谁执行算法无论谁执行算法, ,都能够得到相同的最终都能够得到相同的最终结果结果讲授新课有限性有限性: :算法应由有限步组成算法应由有限步组成, ,至少对某些输入至少对某些

11、输入, ,算法应在有限多步内结束算法应在有限多步内结束, ,并给出计算结果并给出计算结果信息输出信息输出:一个算法至少要有一个有效的信一个算法至少要有一个有效的信息输出息输出,这就是问题求解的结果这就是问题求解的结果.不唯一性不唯一性:求解某一个题的解法不一定是唯求解某一个题的解法不一定是唯一的一的, 对于一个问题可以有不同的算法对于一个问题可以有不同的算法.4.4.算法的描述算法的描述: : 描述算法可以有不同的方式描述算法可以有不同的方式, ,常用的有常用的有自自然语言、程序框图、程序设计语言、伪代码然语言、程序框图、程序设计语言、伪代码等等. .数据输入数据输入: :算法一定要根据输入的

12、初始数据或算法一定要根据输入的初始数据或给定的初值才能正确执行它的每一步骤给定的初值才能正确执行它的每一步骤. . 自然语言就是人们日常使用的语言自然语言就是人们日常使用的语言, ,可以是可以是汉语、英语或数学语言等汉语、英语或数学语言等. .用自然语言描述算法用自然语言描述算法的优点是通俗易懂的优点是通俗易懂, ,当算法中的操作步骤都是顺当算法中的操作步骤都是顺序执行时比较容易理解序执行时比较容易理解. .缺点是如果算法中包含缺点是如果算法中包含判断和转向判断和转向, ,并且操作步骤较多时并且操作步骤较多时, ,就不那么直就不那么直观清晰了观清晰了. .(1)(1)自然语言自然语言(2)(2

13、)程序框图程序框图(3)(3)程序设计语言程序设计语言1.1.21.1.2程序框图程序框图中讲解中讲解1.21.2基本算法语句基本算法语句中讲解中讲解例例1.(1).(1)设计一个算法判断设计一个算法判断7 7是否为质数是否为质数. .第一步第一步, 用用2除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以2不能整除不能整除7.第二步第二步, 用用3除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以3不能整除不能整除7.第三步第三步, 用用4除除7,得到余数得到余数3.因为余数不为因为余数不为0， 所以所以4不能整除不能整除7.第四步第四步, 用用5除除7,得到

14、余数得到余数2.因为余数不为因为余数不为0， 所以所以5不能整除不能整除7.第五步第五步, 用用6除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以6不能整除不能整除7.因此，因此，7是质数是质数.例例1.(2).(2)设计一个算法判断设计一个算法判断3535是否为质是否为质数数. .第一步第一步, 用用2除除35,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以2不能整除不能整除35.第二步第二步, 用用3除除35,得到余数得到余数2.因为余数不为因为余数不为0， 所以所以3不能整除不能整除35.第三步第三步, 用用4除除35,得到余数得到余数3.因为余数不为因为余

15、数不为0， 所以所以4不能整除不能整除35.第四步第四步, 用用5除除35,得到余数得到余数0.因为余数为因为余数为0， 所以所以5能整除能整除35.因此，因此，35不是质数不是质数.变式变式1: “判断判断53是否质数是否质数”的算法如下：的算法如下：第第1步步,用用2除除53得余数为得余数为1,余数不为余数不为0,所以所以2不能整除不能整除53;第第2步步,用用3除除53得余数为得余数为2,余数不为余数不为0,所以所以3不能整除不能整除53;第第52步步,用用52除除53得余数为得余数为1,余数不为余数不为0,故故52不能整除不能整除53;所以所以53是质数是质数.上述算法正确吗？请说明理

16、由上述算法正确吗？请说明理由.算法要算法要“面面俱到面面俱到”,不能省略任何一个细小的步骤不能省略任何一个细小的步骤,只有这样只有这样,才能在人设计出算法后才能在人设计出算法后,把具体的执行过程交给计算机完成把具体的执行过程交给计算机完成.设计一个具体问题的算法时设计一个具体问题的算法时,与过去熟悉地解数学题的过程与过去熟悉地解数学题的过程有直接的联系有直接的联系,但这个过程必须被分解成但这个过程必须被分解成若干个明确的步骤若干个明确的步骤,而且这些步骤必须是有效的而且这些步骤必须是有效的.变式变式2:任意给定一个大于任意给定一个大于1的整数的整数n,试设计一个试设计一个程序或步骤对程序或步骤

17、对n是否为质数做出判定是否为质数做出判定.分析分析:回顾这个问题的解题过程回顾这个问题的解题过程.算法步骤算法步骤:第一步第一步:判断判断n是否等于是否等于2. 若若n=2,则则n是质数是质数;若若n2,则执行第二步则执行第二步. 第二步第二步:依次检验依次检验2(n-1)这些整数是不是这些整数是不是n的的约数约数,即是不是整除即是不是整除n的数的数.若有这样的数若有这样的数,则则n不是质数不是质数;若没有这样的数若没有这样的数,则则n是质数是质数.例例2. .用二分法设计一个求方程用二分法设计一个求方程220 x 的近似根的算法的近似根的算法. .(0)x 二分法 对于区间对于区间a,b 上

18、连续不断、且上连续不断、且f(a)f(b)0的函数的函数y=f(x),通过不断地通过不断地把函数把函数f(x)的零点所在的区间一分的零点所在的区间一分为二，使区间的两个端点逐步逼近为二，使区间的两个端点逐步逼近零点，进而得到零点或其近似值的零点，进而得到零点或其近似值的方法叫做方法叫做二分法二分法.第四步第四步, 若若f(a) f(m) 0,则含零点的区间为则含零点的区间为a,m；第二步第二步, 给定区间给定区间a,b,满足满足f(a) f(b)0第三步第三步, 取中间点取中间点2abm第五步第五步,判断判断f(m)是否等于或者是否等于或者a,b的长的长度是否小于度是否小于d，若是，则，若是，

19、则m是方程的近似解是方程的近似解;否否则，返回第三步则，返回第三步将新得到的含零点的仍然记为将新得到的含零点的仍然记为a,b.否则，含零点的区间为否则，含零点的区间为m, b.算法步骤：算法步骤：第一步第一步, 令令 ,给定精确度给定精确度d.2( )2f xxa 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

20、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.003 906 250.003 906 25当当d d=0.005=0.005时，按照以上算法，可得下面表和图时，按照以上算法，可得下面表和图. .y=x2-2121.51.3751.25 于是，开区间于是，开区间（1.4140625,1.41796875）中）中的实数都是当精确度为的实数都是当精确度为0.005时的原方程的近时的原方程的近似解似解.练习练习2. 任意给定一个正实数任意给定一个正实数,设计一个算设计一个算法求以这个数为半径的圆的面积法求以这个数为半径的圆的面积.算法步骤算法步骤:第一步第一步:给定一个正实数给定一个正实数r;第二步第二步:计算以计算以r为半径的圆的面积为半径的圆的面积s=r2;第三步第三步:得到圆的面积得到圆的面积s.练习练习3. 任意给定一个