1.1.1《算法与程序框图——算法的概念》（新人教A版必修3）.ppt

主讲老师潘学国,算法初步,算筹,算盘,计算器,计算机,中国古代数学中蕴涵了丰富的算法思想，算筹、算盘都是盛行一时的计算工具。如今，算法已经成为计算机科学的重要基础，同时计算机又是强大的实现各种算法的工具。,1.1算法与程序框图,算法的概念,请你说出登录腾讯QQ的步骤。（电脑已经打开）,第一步：打开QQ程序。第二步：输入QQ号码。第三步：输入密码。第四步：点击登录。,一人带着一只狼、一只羊和一箱蔬菜要过河，但只有一条小船。乘船时，每次只能带狼、羊和蔬菜中的一种。当有人在场时，狼、羊、蔬菜都相安无事。一旦人不在，狼会吃羊，羊会吃菜。请设计一个方案，安全地将狼、羊和蔬菜带过河。,趣味益智游戏,一般地，对于一类问题的机械式地、统一地、按部就班地求解过程称为算法(algorithm)。它是解决某一问题的程序或步骤。,所谓“算法”就是解题方法的精确描述。从更广义的角度来看，并不是只有“计算”的问题才有算法，日常生活中处处都有。如乐谱是乐队演奏的算法，菜谱是做菜肴的算法，珠算口诀是使用算盘的算法。,按照这样的理解,我们可以设计出很多具体数学问题的算法.下面看几个例子：,思考：回顾二元一次方程组有哪些解法？,导入新课,思考,分析：解二元一次方程组的主要思想是消元的思想，有代入消元和加减消元两种消元的方法。下面分别用两种方法写出它的求解过程。,加减消元,代入消元,思考：你能写出解一般的二元一次方程组的步骤吗？,思考：根据上述分析，你能归纳出算法的概念吗？,在数学中，按照一定规则解决某一类问题的明确和有限的步骤称为算法。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。,讲授新课,思考：有人对哥德巴赫猜想“任何大于4的偶数都能写成两个质数之和”设计了如下操作步骤：,第一步，检验6=3+3，第二步，检验8=3+5，第三步，检验10=5+5，利用计算机无穷地进行下去！请问：这是一个算法吗？,思考：请你根据前面两个问题总结一下算法有哪些特点和要求？,1、有限性：一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。,2、确定性：算法对每一个步骤都有确切的，能有效执行且得到确定结果的，不能模棱两可。,3、顺序与可行性：算法中的每下一个步骤都是在上一个步骤完成才能执行，并且每一步都是可以完成的。,4、不唯一性：求解某一个问题的算法不一定是唯一的，对于同一个问题可以有不同的算法。,5、普遍性：一个算法通常设计成能解决一类问题，不仅仅是解决一个问题。,1、下列对算法描述正确的一项是（）A.某一个具体问题的一系列解决步骤B.数学问题的解题过程C.某一类问题的一系列解决步骤D.计算机程序,C,2、算法具有精确性，指的是（）A.算法的步骤是有限的B.算法一定包含输出C.算法的每个步骤是具体的、可操作D.以上说法都不正确,C,3、算法具有有穷性，指的是（）A.算法的每个步骤都是可执行的B.算法的步骤是有限的C.算法一定包含输出D.以上说法都不正确,B,4、下列对算法描述正确的一项是（）A.算法只能用自然语言来描述B.算法只能用图形方式来表示C.同一问题可以有不同的算法D.同一问题的算法不同，结果必然不同,C,5、下面关于算法的说法，正确的个数是_.(1)求解某一类问题的算法是唯一的(2)算法必须在有限步操作之后停止(3)算法的每一步操作必须是明确的，不能有歧义或模糊(4)算法执行后一定产生确定的结果,3,例1：(1)设计一个算法判断7是否为质数.(2)设计一个算法判断35是否为质数.,算法分析：根据质数的定义，依次用26除7，如果它们中的一个能整除7，则7不是质数，否则7是质数，类似地，也可以写出“35是否是质数”的算法。,例1：(1)设计一个算法判断7是否为质数.(2)设计一个算法判断35是否为质数.,第一步，用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，得到余数1.因为余数不为0，所以2不能整除35.,第二步,用3除35，得到余数2.因为余数不为0，所以3不能整除35.,第三步,用4除35，得到余数3.因为余数不为0，所以4不能整除35.,第四步,用5除35，得到余数0.因为余数为0，所以5能整除35.因此，35不是质数.,例1：(1)设计一个算法判断7是否为质数.(2)设计一个算法判断35是否为质数.,思考:“判断1997是否质数”的算法如下：第1步,用2除1997得余数为1,余数不为0,所以2不能整除1997;第2步,用3除1997得余数为2,余数不为0,所以3不能整除1997;第1995步,用1996除1997得余数为1,余数不为0,故1996不能整除1997;所以1997是质数.,上述算法正确吗？请说明理由.,不正确。,算法分析：对于整数1997，若用i表示21996中的任意整数，则判断整数1997是否为质数的算法包含下面的重复操作。用i除1997，得到余数r，判断余数r是否为0，若是，则1997不是质数；否则，将i的值增加1.再执行同样的操作.这个操作一直要进行到i的值等于1996为止。,第一步：令i=2；,第二步：用i除1997得余数r；,第三步：判断“r=0”是否成立，若是，则1997不是质数，结束算法，否则，将i的值增加1，仍用i表示；,第四步：判断“i1996”是否成立，若是则1997是质数，结束算法，否则，返回第二步。,算法设计：,你能写出“判断整数n(n2)是否为质数”的算法吗？,思考？,算法分析：对于任意的整数n(n2)，若用i表示2（n-1）中的任意整数，则判断整数n(n2)是否为质数的算法包含下面的重复操作。用i除n，得到余数r，判断余数r是否为0，若是，则n不是质数；否则，将i的值增加1.再执行同样的操作.这个操作一直要进行到i的值等于（n-1）为止。,你能写出“判断整数n(n2)是否为质数”的算法吗？,第一步，给定大于2的整数n;,第二步，令i=2;,第三步，用i除n，得到余数r;第四步，判断余数r是否为0,若是则n不是质数，结束算法；否则，将i的值增加1，仍用i表示;,第五步，判断i是否大于(n-1)，若是，则n是质数；否则，返回第三步。,算法设计：,思考？,（1）请你设计出求1+2+3+4+5+6+7的算法.,第一步:计算1+2,得3;第二步:将第一步结果3+3，得6;第三步:将第二步结果6+4，得10;第四步:将第三步结果10+5，得15;第五步:将第四步结果15+6，得21；第六步:将第五步结果21+7，得28.,第一步,取n=7;第二步,计算第三步,计算结果28.,解法2.,1+2+3+n=n(n+1)/2,解法1.,按照逐一相加的程序进行.,-,用公式运算,练习2：有蓝和黑两个墨水，但现在却错把蓝墨水装在了黑墨水瓶中，黑墨水装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题.,分析：由于两个墨水瓶中的墨水不能直接交换，故可以考虑通过引入第三个空墨水瓶的办法进行交换。,第二步：将黑墨水瓶中的蓝墨水倒入白瓶中；,第三步：将蓝墨水瓶中的黑墨水倒入黑瓶中；,第五步：交换结束。,第一步：取一只空墨水瓶，设其为白色；,第四步：将白瓶中的蓝墨水倒入蓝瓶中；,练习3：任意给定一个正实数，试设计一个算法求以这个数为半径的圆的面积。,算法设计：,第一步，给定一个正实数r；第二步，计算以r为半径的圆的面积；第三步，得到圆的面积s。,练习4：任意给定一个大于1的正整数n，试设计一个算法求出n的所有因数。,第一步，给定一个大于1的正整数n；第二步，令i=1；第三步，用i除n得余数r；第四步，判断“r=0”是否成立：若是，则i是n的因数；否则，i不是n的因数；第五步，使i的值增加1，仍用i表示第六步，判断“in”是否成立，若是，则结束算法；否则，返回第三步。,算法分析：令f(x)=x2-2=0(x0),则方程x2-2=0的解就是函数f(x)的零点.二分法的基本思想：把函数f(x)的零点所在区间a,b（满足f(a)f(b)0）一分为二，得到a,m和m,b.根据f(a)f(m)0是否成立，取出零点所在的区间a,m或m,b,仍记为a,b.对所得的区间a,b,重复上述步骤，直到包含零点的区间a,b足够小，则a,b内的数可以作为方程的近似解.,当d=0.005时，按照以上算法，可得下面表和图.,第四步,若f(a)f(m)0,则含零点的区间为a,m；,第二步，给定区间a，b，满足f(a)f(b)0,第三步,取中间点,第五步,判断f(m)是否等于0或者a,b的长度是否小于d，若是，则m是方程的近似解；否则，返回第三步,将新得到的含零点的仍然记为a,b.,否则，含零点的区间为m,b.,算法设计：第一步，令，给定精确度d.,于是，开区间（1.4140625,1.41796875）中的实数都是当精确度为0.005时的原方程的近似解.,实际上，上述步骤也是求的近似值的一个算法。,思考：与一般的解决问题的过程相比，你认为算法最重要的特征是什么？,设计一个具体问题的算法时,与过去熟悉地解数学题的过程有直接的联系,