资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精品课件,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精品课件,1.1.1,算法的概念,1.1.1 算法的概念,一人带着一只狼、一只羊和一箱蔬菜要过河,但只有一条小船,.,乘船时，每次只能带狼、羊和蔬菜中的一种,.,当有人在场时，狼、羊、蔬菜都相安无事,.,一旦人不在,狼会吃羊,羊会吃菜,.,请设计一个方案,安全地将狼、羊和蔬菜带过河,.,过河游戏,趣味益智游戏,一人带着一只狼、一只羊和一箱蔬菜要过河,但只,如何发电子邮件？,假如你的朋友不会发电子邮件，你能教会他么？,发邮件的方法很多，下面就是其中一种的操作步骤：,第一步 登陆电子信箱,第二步 点击“写信”,第三步 输入收件人地址,第四步 输入主题,第五步 输入信件内容,第六步 点击“发送”,如何发电子邮件？假如你的朋友不会发电子邮件，你能教会他么？第,一般地,对于一类问题的机械式地、统一地、按部就班地求解过程称为算法,(algorithm),它是解决某一问题的程序或步骤,.,按照这样的理解,我们可以设计出很多具体数学问题的算法,.,下面看几个例子,:,所谓“算法”就是解题方法的精确描述,.,从更广义的角度来看,并不是只有“计算”的问题才有算法,日常生活中处处都有,.,如,乐谱,是乐队演奏的算法,菜谱,是做菜肴的算法,珠算口诀,是使用算盘的算法,.,一般地,对于一类问题的机械式地、统一地、按部就班地求,请你写出解下面二元一次方程组的详细过程,.,第二步,解得,第三步,-,2,得,5,y,=3;,第四步,解,得,第五步,得到方程组的解为,第一步,+,2,得,5,x,=1,;,解：,做一做,请你写出解下面二元一次方程组的详细过程.,你能写出解一般的二元一次方程组的步骤吗？,第一步,第二步,解（,3,）得,思考,你能写出解一般的二元一次方程组的步骤吗？第一步,第四步,解（,4,）得,第三步,第五步,得到方程组的解为,上述步骤构成了解二元一次方程组的一个算法，我们可以进一步根据这一算法编制计算机程序，让计算机来解二元一次方程组,.,第四步,解（4）得 第三步,第五步,得到方,练习,1.,给出求,1+2+3+4+5+6,的一个算法,.,解法,1.,按照逐一相加的程序进行,.,第一步,:,计算,1+2,得,3;,第二步,:,将第一步中的运算结果,3,与,3,相加得,6;,第三步,:,将第二步中的运算结果,6,与,4,相加得,10;,第四步,:,将第三步中的运算结果,10,与,5,相加得,15;,第五步,:,将第四步中的运算结果,15,与,6,相加得,21.,练习1.给出求1+2+3+4+5+6的一个算法.解法1.按,解法,2.,可以运用下面公式直接计算,.,第一步,取,n,=,6,;,第二步,计算,;,第三步,输出计算结果,.,点评,:,解法,1,繁琐,步骤较多,;,解法,2,简单，步骤较少,.,找出好的算法是我们的追求目标,.,解法2.可以运用下面公式直接计算.第一步,取 n=6;第二,现在你对算法有了新的认识了吗？,现在你对算法有了新的认识了吗？,在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤,.,现在，算法通常可以编成计算机程序，让计算机执行并解决问题,.,2.,算法的要求,(1),写出的算法,必须能解决一类问题,(,例如解任意一个二元一次方程组,),并且能重复使用,;,(2),算法过程要能一步一步执行,每一步执行的操作,必须确切,不能含混不清,而且在有限步之内完成后能得出结果,.,1.,算法的定义,在数学中，算法通常是指按照一定规则解决某一类,3.,算法的基本特征,:,明确性,:,算法对每一个步骤都有确切的、非二义性的规定,即每一步对于利用算法解决问题的人或计算机来说都是可读的、可执行的,而不需要计算者临时动脑筋,.,有效性,:,算法的每一个步骤都能够通过基本运算有效地进行,并得到确定的结果；对于相同的输入,无论谁执行算法,都能够得到相同的最终结果,有限性,:,算法应由有限步组成,至少对某些输入,算法应在有限多步内结束,并给出计算结果,3.算法的基本特征:明确性:算法对每一个步骤都有确切的、非二,例,1:,(1),设计一个算法判断,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,是质数,.,例1:(1)设计一个算法判断7是否为质数.第一步 用2,例,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,不是质数,.,例1:(2)设计一个算法判断35是否为质数.第一步,用,变式,:,“,判断,53,是否质数”的算法如下：,第,1,步,用,2,除,53,得余数为,1,余数不为,0,所以,2,不能整除,53;,第,2,步,用,3,除,53,得余数为,2,余数不为,0,所以,3,不能整除,53;,第,52,步,用,52,除,53,得余数为,1,余数不为,0,故,52,不能整除,53;,所以,53,是质数,.,上述算法正确吗？请说明理由,.,算法要“面面俱到”,不能省略任何一个细小的步骤,只有这样,才能在人设计出算法后,把具体的执行过程交给计算机完成,.,设计一个具体问题的算法时,与过去熟悉地解数学题的过程,有直接的联系,但这个过程必须被分解成,若干个明确的步骤,而且这些步骤必须是有效的,.,变式:“判断53是否质数”的算法如下：上述算法正确吗？请说,判断“整数,n(n2),是否是质数”的算法,自然语言描述,第一步 给定大于,2,的整数,n,.,第二步 令,i=2,.,第三步 用,i,除,n,，得到余数,r.,第四步 判断“,r=0”,是否成立,.,若是，则,n,不是质,数，结束算法；否则将,i,的值增加,1,，仍用,i,表示,.,第五步 判断“,i(n-1)”,是否成立,.,若是，则,n,是质数，结束算法；否则返回第三步,.,判断“整数n(n2)是否是质数”的算法自然语言描述第一步,例,2,:,用二分法设计一个求方程 近似根的算法,二分法,对于区间,a,b,上连续不断、且,f(a)f(b)0,的函数,y=f(x),通过不断地把函数,f(x),的零点所在的区间一分,为二，使区间的两个端点逐步逼近零点，进而得到零点或其近似值的方法叫做二分法,.,例2:用二分法设计一个求方程 近似,第四步,若,f,(,a,),f,(,m,)0,则含零点的区间为,a,m,；,第二步,给定区间,a,b,满足,f,(,a,),f,(,b,),0,第三步,取中间点,第五步,判断,f,(,m,),是否等于或者,a,b,的长度是否小于,d,，若是，则,m,是方程的近似解,;,否则，返回第三步,将新得到的含零点的仍然记为,a,b,.,否则，含零点的区间为,m,b,.,算法步骤：,第一步,令,给定精确度,d,.,第四步,若f(a)f(m)0,则含零点的区间为,a,b,|a-b|,1,2,1,1,1.5,0.5,1.25,1.5,0.25,1.375,1.5,0.125,1.375,1.437 5,0.062 5,1.406 25,1.437 5,0.031 25,1.406 25,1.421 875,0.015 625,1.414 625,1.421 875,0.007 812 5,1.414 062 5,1.417 968 75,0.003 906 25,当,d,=0.005,时，按照以上算法，可得下面表和图,.,ab|a-b|12111.50.51.251.50.251.,y,=,x,2,-2,1,2,1.5,1.375,1.25,于是，开区间（,1.4140625,1.41796875,）中的实数都是当精确度为,0.005,时的原方程的近似解,.,y=x2-2121.51.3751.25 于是，开,小结：,算法的特征是什么？,明确性,有效性,有限性,算法的概念：,算法通常指可以用来解决的某,一类问题的步骤或程序，这些步骤或程序必须是明,确的和有效的，而且能够在有限步之内完成的,.,小结：算法的特征是什么？明确性有效性有限性算法的概念：算法通,
展开阅读全文