广东广州增城中学2015-2016高二文科数学必修三1.1.1算法的概念课件ppt48页.ppt

1.1.1 算法的概念,普通高中课程标准试验教科书 人教A版数学必修3 第一章 算法初步,计算机与算法: 在现代社会里，计算机已经成为人们日常生活和工作不可缺少的工具听音乐、看电影、玩游戏、画卡通画、处理数据计算机几乎可以是一个全能的助手，你可以用它来做你想做的任何事情那么，计算机是怎样工作呢？要想弄清楚这个问题，就需要学习算法 什么是算法？,1.请看小品“钟点工”片段。,一、问题情境,要把大象装冰箱，分几步？,问：,答：分三步：,第一步：打开冰箱门,第二步：把大象装冰箱,第三步：关上冰箱门,2、现有九枚硬币，有一枚略重，你能用天平(不用砝码) 将其找出来吗？设计一种方法，解决这一问题.,一、问题情境,第一步：把九枚硬币平均分成三份，取其中两份放天平上称，若平衡则重的在剩下的一份里，若不平衡则在重的一份里；,第二步：在重的一份里取两枚放天平的两边，若平衡则剩下的一枚就是所找的，若不平衡则重的那枚就是所要找的。,3、“幸运52”中猜商品价格:,第一步 报4000;,第二步 若正确，就结束,若高了,则报2000. 若低了,则报6000;,第三步 重复第二步的报数方法，直到得出正确结果.,一、问题情境,一商品价格在08000元之间，问竞猜者采取什 么策略才能在较短时间内猜出商品价格？,思考：由上面三个问题你能归纳出什么共同的东西？有什么特点？,第三步：将 代入， 得,一、问题情境,注意：这种消元回代的算法适用于一般线性方程组的求解.,思考：写出一般二元一次方程组的解法步骤.,第一步,第二步,解（3）得,写出一般二元一次方程组的解法步骤.,第四步,解（4）得,第三步,第五步,得到方程组的解为,二、新课研探,1、定义：,广义地说，算法就是做某一件事的步骤或程序。如：菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法，在数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。,算法（algorithm）这个出现于12世纪，指的是用阿拉伯数字进行算术运算的过程，在数学中，现在意义上的“算法”通常是指按照一定规则来解决某一类问题的明确和有限的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成。,一般来说算法通常可以编成计算机程序,让计算机执行并解决问题.,2.算法的特点:,明确性:算法中的每一个步骤都是确切的,能有效的执行且得到确定的结果,不能模棱两可。,有序性:算法从初始步骤开始,分为若干明确的步骤,每一步都只能有一个确定的继任者,只有执行完前一步才能进入到后一步,并且每一步都确定无误后,才能解决问题。,不唯一性:求解某一个问题的解法不一定是唯一的,对于同一个问题可以有不同的解法,但算法有优劣之分,好的算法是我们追求的目标.,普适性:写出的算法必须能解决一类问题,并且能重复使用,这是设计算法的一条基本原则,这样才能使算法更有价值.,有限性:算法应由有限步组成,必须在有限操作之后停止,并给出计算结果。,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.(2)设计一个算法判断35是否为质数.,第一步, 用2除35,得到余数1.因为余数不为0， 所以2不能整除35.,第二步, 用3除35,得到余数2.因为余数不为0， 所以3不能整除35.,第三步, 用4除35,得到余数3.因为余数不为0， 所以4不能整除7.,第四步, 用5除35,得到余数0.因为余数为0， 所以5能整除35.因此，35不是质数.,应用举例,思考 设计一个算法判断1997是否为质数.,第一步, 用2除 ,得到余数1.因为余数不为0， 所以2不能整除7.,第二步, 用3除 ,得到余数1.因为余数不为0， 所以3不能整除7.,第三步, 用4除 ,得到余数3.因为余数不为0， 所以4不能整除7.,第四步, 用5除 ,得到余数2.因为余数不为0， 所以5不能整除7., 所以6不能整除 .因此， 是质数.,1997,7,7,7,7,1997,1997,1997,1997,1997,1997,1997,7,7,1997,1997,问：省略号的使用合适吗？,设计一个算法,判断整数n(n2)是否为质数?,第一步，给定大于2的整数n。,第二步，令i=2,第三步，用i除n，得到余数r。,第四步，判断“r=0”是否成立。,第五步，判断“i(n-1)”是否成立。,若是，则n不是质数，结束算法;,否则，将i的值增加1，仍用i表示。,若是，则n不是质数，结束算法;,否则，返回第三步,做一做,第一步：,第二步：,第三步：,判断 是否等于1。若是，则 既不是质数，也不是合数。若 1，则执行第二步。,判断是 否等于2。若 =2，则 是质数；若 2，则执行第三步。,任意给定一个正整数 ，试设计一个算法对 是否为质数做出判断。,依次检验 的结果是否 为整数。若有，则 不是质数；若没有，则 是质数。,1,1,2,例2 用二分法设计一个求方程 x2 2 = 0 的近似根的算法。,解决问题,第四步, 若f(a) f(m) 0,则含零点的区间为a,m；,第一步, 令 .给定精确度d.,第二步, 给定区间a,b,满足f(a) f(b)0,第三步, 取中间点 ,第五步, 判断a,b的长度是否小于d或者 f(m)是否等于.,将新得到的含零点的仍然记为a,b .,否则，含零点的区间为m, b.,若是，则m是方程的近似 解;否则，返回第三步,第一步，令s=0,第二步，令i=1。,第三步，求出s+i，仍用s表示。,第四步，判断i100是否成立？若是，输出s；若不是，将i的值增加1，仍用i表示返回第三步。,例3：读下列算法，回答问题：,（1）该算法是解决什么问题的？,（2）最终输出的结果是什么？,三、练习1,1、写出求1+2+3+4+5+6的一个算法,解：算法 1：,算法分析：,可以按逐一相加的程序进行，也可以利用公 式 进行，也可以 根据加法运算律简化运算,第一步：计算1+2 得到 3；,第二步：将第一步中的运算结果 3 与 3 相加得到 6；,第三步：第二步中的运算结果 6 与 4 相加得到 10；,第四步：将第三步中的运算结果 10 与 5 相加得到 15；,第五步：将第四步中的运算结果 15 与 6 相加得到 21。,算法2：,第一步：取n=6；,第二步：计算 ；,第三步：输出结果。,算法3：,第一步：将原式变形为（1+6）+（2+5）+（3+4）=37；,第二步：计算 37；,第三步：输出运算结果。,2、任意给定的一个实数，设计一个算法求以这个数为半径的圆的面积。,算法步骤：,第一步：输入任意一个正实数 r；,第二步：计算以r为半径的圆的面积：,第三步：输出圆的面积 S。,3、任意给定一个大于 1 的正整数 n ，设计一个算法求出 n 的所有因数。,算法步骤：,第一步：依次以2 （n 1）为除数除 n ，检查余数是否为0；若是，则是 n 的因数；若不是，则不是 n 的因数；,第二步：在 n 的因数中加入 1 和 n；,第三步：输出n的所有因数。,巩固概念,4。写出交换两个大小相同的杯子中 的液体 (A 水、 B 酒) 的一个算法,第一步,找一个大小与A相同的空杯子C. 第二步,将A 中的水倒入C中. 第三步,将B中的酒精倒入A中. 第四步,将C中的水倒入B中,结束.,巩固概念,5、写出求一元二次方程 ax2+bx+c=0 的根的算法.,第一步,计算=b2-4ac.,第二步,如果0,则原方程无实数解 ;否则(0)时，,第三步:输出x1, x2或无实数解的信息.,1下面的四种叙述不能称为算法的是（ ） （A）广播的广播操图解 （B）歌曲的歌谱 （C）做饭用米 （D）做米饭需要刷锅、淘米、添水、加热这些步骤,练习题,C,2下列关于算法的说法正确的是（ ） （A）某算法可以无止境地运算下去 （B）一个问题的算法步骤可以是可逆的 （C）完成一件事情的算法有且只有一种 （D）设计算法要本着简单、方便、可操作的原则,D,3下列关于算法的说法中，正确的是（ ）. A. 算法就是某个问题的解题过程 B. 算法执行后可以不产生确定的结果 C. 解决某类问题的算法不是惟一的 D. 算法可以无限地操作下去不停止,C,4下列运算中不属于我们所讨论算法范畴的是（ ）. A. 已知圆的半径求圆的面积 B. 从一副扑克牌随意抽取3张扑克牌抽到24点的可能性 C. 已知坐标平面内的两点求直线的方程 D. 加减乘除运算法则,B,5下列语句表达中是算法的有（ ）. 从济南到巴黎可以先乘火车到北京再坐飞机抵达； 利用公式 S = ah2 计算底为1高为2的三角形的面积； x2x +4； 求M(1，2)与N(3，5)两点连线的方程可先求MN的斜率再利用点斜式方程求得 A. 1 个 B. 2 个 C. 3 个 D. 4 个,C,6写出求123100的一个算法.可以运用公式123n 直接计算. 第一步 ； 第二步 ； 第三步 输出运算结果.,取n100,计算,7已知一个学生的语文成绩为89，数学成绩为96，外语成绩为99，求他的总分和平均成绩的一个算法为： 第一步 取A89，B96，C99; 第二步 ； 第三步 ； 第四步 输出D，E.,计算总分DA+B+C,计算平均成绩E,四、回顾反思,1、算法的含义：为一类问题的机械的、统一的求解方法,2、算法的特征 ： 明确性、有效性、有限性,3、算法的思想 ：程序化思思想,4、算法的表述形式：,用日常语言和数学语言或借助于形式语言（算法语言）各种精确的说明。 程序框图（简称框图）。 程序语言。,五、作业,1、求13 5 7 9 11的值，写出其算法。,2、写出解不等式 的一个算法。,1.1.2 程序框图与算法的基本逻辑结构,回答下列问题：,（1）123+100 ；,（2）123 ；,（3）123 2011,请设计一个算法，求满足条件的最小整数,开始,输入n=1,计算 的值,2011,输出n,Y,开始,输入n=2,计算 的值,2011,输出n,Y,用 流 程 图 表 示,若1代入不满足不等式，则代入2验算，如右图,N,开始,输入n=1,计算 的值,2011,输出n,Y,开始,输入n,计算 的值,2011,Y,使n的值增加1,结束,输出n,结束,N,N,开始,输入n,计算 的值,2011,输出n,Y,使n的值增加1,输入输出框,结束,处理框,判断框,流程线,起止框,N,起止框,流程图是由一些图框和带箭头的流线组成的，又叫程序框图。,辨析练习1,1. 流程图的判断框，有一个入口和n个出口，则n的值为（ ） 1 (B) 2 (C) 3 (D) 4 2. 下列图形符号表示输入输出框的是（ ） 矩形框 (B) 平行四边形框 (C) 圆角矩形框 (D) 菱形框 3.表示“根据给定条件判断”的图形符号框的是（ ） 矩形框 (B) 平行四边形框 (C) 圆角矩形框 (D) 菱形框,B,B,D,2.对程序框 表示的功能描述正确的一项是:( ). A.表示算法的起始和结束. B.表示算法输入和输出的信息. C.赋值、计算. D. 按照算法顺