资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,必修,3,第一章 算法初步,1.1.1,算法的概念,一、提出问题,1,、赵本山与宋丹丹演的小品,钟点工,中有这样一段：,要把大象装冰箱，拢共分几步？,三步第一步，把冰箱门打开，第二步，把大象装进去，第三步，把冰箱门带上,第二步,解得,第三步,2,得,5,y,=3;,第四步,解,得,第五步,得到方程组的解为,第一步,+2,得,5,x,=1;,时，若先消去,y,，可归纳出以下步骤：,第一步,第二步,解得,第三步,其中,a,1,b,2,a,2,b,1,0,，你可以写出类似的求解步骤吗？,第四步,解得,第五步,得到方程组的解为,上述步骤构成了解二元一次方程组的一个算法，事实上，我们可以将一般的二元一次方程组的解法转化成计算机语言，做成一个求解二元一次方程组的程序,.,算法不仅是数学及其应用的重要组成部分，也是计算机科学的重要基础在现代社会里，计算机已成为人们日常生活和工作中不可缺少的工具听音乐、看电影、玩游戏、打字、画卡通画、处理数据，计算机是怎样工作的呢？要想弄清楚这个问题，算法的学习是一个开始,二、探索研究,1,、算法的概念,在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤,现在，算法通常可以编成计算机程序，让计算机执行并解决问题,2,、算法的基本特征,程序性：,算法从开始的,“,第一步,”,直到,“,最后一步,”,之间做到环环相扣，分工明确，,“,前一步,”,是,“,后一步,”,的前提，,“,后一步,”,是,“,前一步,”,的继续,明确性：,算法对每一个步骤都有确切的、非二义性的规定，即每一步对于利用算法解决问题的人或计算机来说都是可读的、可执行的,有限性：,算法要有明确的开始和结束，当到达终止步骤时所要解决的问题必须有明确的结果，也就是说必须在有限步内完成任务，不能无限制地持续进行,3,、算法的要求,（,1,）写出的算法，必须能解决一类问题（例如解任意一个二元一次方程组），并且能重复使用；,（,2,）算法过程要能一步一步执行，每一步执行的操作，必须确切，不能含混不清，而且在有限步之内完成后能得出结果,4,、算法的描述,描述算法可以有不同的方式，常用的有自然语言、程序框图、程序设计语言、伪代码等,（,1,）自然语言,自然语言就是人们日常使用的语言，可以是汉语、英语或数学语言等用自然语言描述算法的优点是通俗易懂，当算法中的操作步骤都是顺序执行时比较容易理解缺点是如果算法中包含判断和转向，并且操作步骤较多时，就不那么直观清晰了,（,2,）程序框图,在,1.1.2,程序框图中学习,（,3,）程序设计语言,在,1.2,基本算法语句中学习,5,、例题,例,1,（,1,）设计一个算法，判断,7,是否为质数,（,2,）设计一个算法，判断,35,是否为质数,算法分析：,（,1,）根据质数的定义，可以这样判断：依次用,26,除,7,，如果它们中有一个能整除,7,，则,7,不是质数，否则,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,是质数,.,算法：,（,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,不是质数,.,算法：,点评：,上述算法有很大的局限性，用上述算法判断,35,是否为质数还可以，如果判断,2013,是否为质数就麻烦了，因此，我们需要寻找普遍适用的算法步骤,探究：,请写出判断,n,(,n,2),是否为质数的算法,算法如下：,第一步，给定大于,2,的整数,n,第二步，令,i,=2,第三步，用,i,除,n,，得到余数,r,.,第四步，判断,“,r,=0,”,是否成立若是，则,n,不是质数，结束算法；否则将,i,的值增加,1,，仍用,i,表示,.,第五步，判断,“,i,(,n,1),”,是否成立若是，则,n,是质数，结束算法；否则返回第三步,分析：,对于任意的整数,n,(,n,2),，若用,i,表示,2(,n,1),中的任意整数，则,“判断,n,是否为,质数”的,算法包含下面的重复操作：用,i,除,n,，得到余数,r,判断余数,r,是否为,0,，若是，则,n,不是质数；否则，将,i,的值增加,1,，再执行同样的操作,这个操作一直要进行到,i,的值等于,(,n,1),为止,变式训练：,1,、判断,“,53,是否为质数,”的如下,操作步骤是否为算法？,第,1,步，用,2,除,53,，得到余数,1,因为余数不为,0,，所以,2,不能整除,53,第,2,步，用,3,除,53,，得到余数,2,因为余数不为,0,，所以,3,不能整除,53,第,3,步，用,4,除,53,，得到余数,1,因为余数不为,0,，所以,4,不能整除,53,第,51,步，用,52,除,53,，得到余数,1,因为余数不为,0,，所以,52,不能整除,53,因此,53,是质数,2,、有人对哥德巴赫,猜想“任何,大于,4,的偶数都能写成两个质数之和,”设计,了如下操作步骤：,第一步，检验,6=3+3,，,第二步，检验,8=3+5,，,第三步，检验,10=5+5,，,利用计算机无穷地进行下去,!,请问：这是一个算法吗？,例,2,写出用,“二分法”求,方程,x,2,2=0(,x,0),的近似解的算法,“二分法”的,基本思想是：把函数,f,(,x,),的零点所在的区间,a,，,b,(,满足,f,(,a,),f,(,b,)0,）,“一分为二”,，得到,a,，,m,和,m,，,b,根据,“,f,(,a,),f,(,m,)0),的解就是函数,f,(,x,),的零点,第四步，若,f,(,a,),f,(,m,),n,”,是否成立，若成立，则结束算法；否则，返回第三步,四、课堂小结,本节课学习了算法的概念、特征，以及针对某一类问题如何分析算法、写出算法,五、课外作业,同步练习,
展开阅读全文