《高考数学一轮复习 1.1.1《算法的概念》课件 新人教A必修3.ppt》由会员分享，可在线阅读，更多相关《高考数学一轮复习 1.1.1《算法的概念》课件 新人教A必修3.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法与程序框图算法与程序框图2021/8/11 星期三1 一一人人带带着着一一只只狼狼、一一只只羊羊和和一一箱箱蔬蔬菜菜要要过过河河,但但只只有有一一条条小小船船.乘乘船船时时，每每次次只只能能带带狼狼、羊羊和和蔬蔬菜菜中中的的一一种种.当当有有人人在在场场时时，狼狼、羊羊、蔬蔬菜菜都都相相安安无无事事.一一旦旦人人不不在在,狼狼会会吃吃羊羊,羊羊会会吃吃菜菜.请请设设计计一一个个方方案案,安安全全地地将将狼狼、羊和蔬菜带过河羊和蔬菜带过河.过河游戏趣味益智游戏2021/8/11 星期三2如何发电子邮件？2021/8/11 星期三32021/8/11 星期三41.1.1 1.1.1 算法的概念
2、算法的概念2021/8/11 星期三5 一一般般地地,对对于于一一类类问问题题的的机机械械式式地地、统统一一地地、按按 部部 就就 班班 地地 求求 解解 过过 程程 称称 为为 算算 法法(algorithm)(algorithm)它是解决某一问题的程序或步骤它是解决某一问题的程序或步骤.按照这样的理解按照这样的理解,我们可以设计出很多具我们可以设计出很多具体数学问题的算法体数学问题的算法.下面看几个例子下面看几个例子:所所谓谓“算算法法”就就是是解解题题方方法法的的精精确确描描述述.从从更更广广义义的的角角度度来来看看,并并不不是是只只有有“计计算算”的的问问题题才才有有算算法法,日日常常
3、生生活活中中处处处处都都有有.如如乐乐谱谱是是乐乐队队演演奏奏的的算算法法,菜菜谱谱是是做做菜菜肴肴的的算算法法,珠珠算算口口诀诀是使用算盘的算法是使用算盘的算法.2021/8/11 星期三6 请你写出解下面二元一次方程组的详细过程请你写出解下面二元一次方程组的详细过程.第二步第二步,解解得得第三步第三步,-2得得 5y=3;第四步第四步,解解得得 第五步第五步,得到方程组的解为得到方程组的解为第一步第一步,+2得得 5x=1;解：做一做2021/8/11 星期三7 你能你能写出解一般的二元一次方程组的步写出解一般的二元一次方程组的步 骤吗？骤吗？第一步第一步,第二步第二步,解（解（3）得）得
4、 思考2021/8/11 星期三8 第四步第四步,解（解（4）得）得 第三步第三步,第五步第五步,得到方程得到方程组组的解的解为为 2021/8/11 星期三9解解，得，得 将将带入带入得得 得得解解 得得第一步第一步：第二步：第二步：第三步：第三步：+2+2，得，得将将 代入代入,得得思考思考这这 两个解方程组的两个解方程组的算法算法的的适用范围有何不同？适用范围有何不同？第一步：第一步：第二步：第二步：第三步：第三步：-2021/8/11 星期三10 事实上，我们可以将一般的二元一次方程组的解法转化成计算机语言，做成一个求解二元一次方程组的程序.这儿已经做好了，试一试吧！这儿已经做好了，试
5、一试吧！2021/8/11 星期三11练习练习1.给出求给出求1+2+3+4+5+6的一个算法的一个算法.解法解法1.1.按照逐一相加的程序进行按照逐一相加的程序进行.第一步第一步:计算计算1+2,得得3;第二步第二步:将第一步中的运算结果将第一步中的运算结果3与与3相加得相加得6;第三步第三步:将第二步中的运算结果将第二步中的运算结果6与与4相加得相加得10;第四步第四步:将第三步中的运算结果将第三步中的运算结果10与与5相加得相加得15;第五步第五步:将第四步中的运算结果将第四步中的运算结果15与与6相加得相加得21.2021/8/11 星期三12解法解法2.2.可以运用下面公式直接计算可
6、以运用下面公式直接计算.第一步第一步,取取 n=6;第二步第二步,计算计算 ;第三步第三步,输出计算结果输出计算结果.点点评评:解解法法1 1繁繁琐琐,步步骤骤较较多多;解解法法2 2简简单单，步步骤较少骤较少.找出好的算法是我们的追求目标找出好的算法是我们的追求目标.2021/8/11 星期三13现在你对算法有了新现在你对算法有了新的认识了吗？的认识了吗？2021/8/11 星期三14 在在数数学学中中，算算法法通通常常是是指指按按照照一一定定规规则则解解决决某某一一类类问问题题的的明明确确和和有有限限的的步步骤骤.现现在在，算算法法通通常常可可以以编编成成计计算算机机程程序序，让让计计算算
7、机机执执行并解决问题行并解决问题.2.2.算法的要求算法的要求(1)写出的算法写出的算法,必须能解决一类问题必须能解决一类问题(例如解任例如解任意一个二元一次方程组意一个二元一次方程组),并且能重复使用并且能重复使用;(2)算法过程要能一步一步执行算法过程要能一步一步执行,每一步执行的每一步执行的操作操作,必须确切必须确切,不能含混不清不能含混不清,而且在有限步之而且在有限步之内完成后能得出结果内完成后能得出结果.1.1.算法的定义算法的定义讲授新课2021/8/11 星期三153.3.算法的基本特征算法的基本特征:明明确确性性:算算法法对对每每一一个个步步骤骤都都有有确确切切的的、非非二二义
8、义性性的的规规定定,即即每每一一步步对对于于利利用用算算法法解解决决问问题题的的人人或或计计算算机机来来说说都都是是可可读读的的、可可执执行行的的,而而不不需需要计算者临时动脑筋要计算者临时动脑筋.有有效效性性:算算法法的的每每一一个个步步骤骤都都能能够够通通过过基基本本运运算算有有效效地地进进行行,并并得得到到确确定定的的结结果果；对对于于相相同同的的输输入入,无无论论谁谁执执行行算算法法,都都能能够够得得到到相相同同的的最最终终结果结果讲授新课有限性有限性:算法应由有限步组成算法应由有限步组成,至少对某些输入至少对某些输入,算法应在有限多步内结束算法应在有限多步内结束,并给出计算结果并给出
9、计算结果2021/8/11 星期三16信信息息输输出出:一一个个算算法法至至少少要要有有一一个个有有效效的的信信息息输出输出,这就是问题求解的结果这就是问题求解的结果.不不唯唯一一性性:求求解解某某一一个个题题的的解解法法不不一一定定是是唯唯一的一的,对于一个问题可以有不同的算法对于一个问题可以有不同的算法.4.4.算法的描述算法的描述:描描述述算算法法可可以以有有不不同同的的方方式式,常常用用的的有有自自然语言、程序框图、程序设计语言、伪代码然语言、程序框图、程序设计语言、伪代码等等.数数据据输输入入:算算法法一一定定要要根根据据输输入入的的初初始始数数据据或或给定的初值才能正确执行它的每一
10、步骤给定的初值才能正确执行它的每一步骤.2021/8/11 星期三17 自自然然语语言言就就是是人人们们日日常常使使用用的的语语言言,可可以以是是汉汉语语、英英语语或或数数学学语语言言等等.用用自自然然语语言言描描述述算算法法的的优优点点是是通通俗俗易易懂懂,当当算算法法中中的的操操作作步步骤骤都都是是顺顺序序执执行行时时比比较较容容易易理理解解.缺缺点点是是如如果果算算法法中中包包含含判判断断和和转转向向,并并且且操操作作步步骤骤较较多多时时,就就不不那那么么直直观观清晰了清晰了.(1)(1)自然语言自然语言(2)(2)程序框图程序框图(3)(3)程序设计语言程序设计语言1.1.21.1.2
11、程序框图程序框图中讲解中讲解1.21.2基本算法语句基本算法语句中讲解中讲解2021/8/11 星期三18例例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,得到余数得到余数2.因为余数不为因为余数不为0，所以所以5不能整除
12、不能整除7.第五步第五步,用用6除除7,得到余数得到余数1.因为余数不为因为余数不为0，所以所以6不能整除不能整除7.因此，因此，7是质数是质数.2021/8/11 星期三19例例1.(2).(2)设计一个算法判断设计一个算法判断3535是否为质数是否为质数.第一步第一步,用用2除除35,得到余数得到余数1.因为余数不为因为余数不为0，所以所以2不能整除不能整除35.第二步第二步,用用3除除35,得到余数得到余数2.因为余数不为因为余数不为0，所以所以3不能整除不能整除35.第三步第三步,用用4除除35,得到余数得到余数3.因为余数不为因为余数不为0，所以所以4不能整除不能整除35.第四步第四
13、步,用用5除除35,得到余数得到余数0.因为余数为因为余数为0，所以所以5能整除能整除35.因此，因此，35不是质数不是质数.2021/8/11 星期三20变式变式1:“判断判断53是否质数是否质数”的算法如下：的算法如下：第第1步步,用用2除除53得余数为得余数为1,余数不为余数不为0,所以所以2不能整除不能整除53;第第2步步,用用3除除53得余数为得余数为2,余数不为余数不为0,所以所以3不能整除不能整除53;第第52步步,用用52除除53得余数为得余数为1,余数不为余数不为0,故故52不能整除不能整除53;所以所以53是质数是质数.上述算法正确吗？请说明理由上述算法正确吗？请说明理由.
14、算法要算法要“面面俱到面面俱到”,不能省略任何一个细小的步骤不能省略任何一个细小的步骤,只有这样只有这样,才能在人设计出算法后才能在人设计出算法后,把具体的执行过程交给计算机完成把具体的执行过程交给计算机完成.设计一个具体问题的算法时设计一个具体问题的算法时,与过去熟悉地解数学题的过程与过去熟悉地解数学题的过程有直接的联系有直接的联系,但这个过程必须被分解成但这个过程必须被分解成若干个明确的步骤若干个明确的步骤,而且这些步骤必须是有效的而且这些步骤必须是有效的.2021/8/11 星期三21变式变式2:任意给定一个大于任意给定一个大于1的整数的整数n,试设计一个试设计一个程序或步骤对程序或步骤
15、对n是否为质数做出判定是否为质数做出判定.分析分析:回顾这个问题的解题过程回顾这个问题的解题过程.算法步骤算法步骤:第一步第一步:判断判断n是否等于是否等于2.若若n=2,则则n是质数是质数;若若n2,则执行第二步则执行第二步.第二步第二步:依次检验依次检验2(n-1)这些整数是不是这些整数是不是n的的约数约数,即是不是整除即是不是整除n的数的数.若有这样的数若有这样的数,则则n不不是质数是质数;若没有这样的数若没有这样的数,则则n是质数是质数.2021/8/11 星期三22例例2.用二分法设计一个求方程用二分法设计一个求方程的近似根的算法的近似根的算法.2021/8/11 星期三23二分法
16、对于区间对于区间a,b 上连续不断、且上连续不断、且f(a)f(b)0的函数的函数y=f(x),通过不断地通过不断地把函数把函数f(x)的零点所在的区间一分的零点所在的区间一分为二，使区间的两个端点逐步逼近为二，使区间的两个端点逐步逼近零点，进而得到零点或其近似值的零点，进而得到零点或其近似值的方法叫做方法叫做二分法二分法.2021/8/11 星期三24第四步第四步,若若f(a)f(m)0,则含零点的区间为则含零点的区间为a,m；第二步第二步,给定区间给定区间a,b,满足满足f(a)f(b)0第三步第三步,取中间点取中间点第五步第五步,判断判断f(m)是否等于或者是否等于或者a,b的长的长度是
17、否小于度是否小于d，若是，则，若是，则m是方程的近似解是方程的近似解;否否则，返回第三步则，返回第三步将新得到的含零点的仍然记为将新得到的含零点的仍然记为a,b.否则，含零点的区间为否则，含零点的区间为m,b.算法步骤：算法步骤：第一步第一步,令令 ,给定精确度给定精确度d.2021/8/11 星期三25a 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
18、51.437 50.031 250.031 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时，按照以上算法，可得下面表和图时，按照以上算法，可得下面表和图.2021/8/11 星期三26y=x2-2121.51.3751.25 于是，开区间于是，开
19、区间（1.4140625,1.41796875）中）中的实数都是当精确度为的实数都是当精确度为0.005时的原方程的近时的原方程的近似解似解.2021/8/11 星期三27练习练习2.任意给定一个正实数任意给定一个正实数,设计一个算设计一个算法求以这个数为半径的圆的面积法求以这个数为半径的圆的面积.算法步骤算法步骤:第一步第一步:给定一个正实数给定一个正实数r;第二步第二步:计算以计算以r为半径的圆的面积为半径的圆的面积S=r2;第三步第三步:得到圆的面积得到圆的面积S.2021/8/11 星期三28练习练习3.任意给定一个大于任意给定一个大于 1 的正整数的正整数 n，设计一个算法求出，设计
20、一个算法求出 n 的所有因数的所有因数.算法步骤：算法步骤：第一步第一步,依次以依次以2（n 1）为除数除）为除数除 n，检查余数是否为，检查余数是否为0；若是，则是；若是，则是 n 的因的因数；若不是，则不是数；若不是，则不是 n 的因数；的因数；第二步第二步,在在 n 的因数中加入的因数中加入 1 和和 n；第三步第三步,输出输出n的所有因数的所有因数.2021/8/11 星期三29练习练习4.写出求一元二次方程写出求一元二次方程 ax2+bx+c=0 的根的算法的根的算法.第一步第一步,计算计算=b2 2-4-4ac.第二步第二步,如果如果0,0,则原方程无实数解则原方程无实数解 ;否则
21、否则(0)(0)时，时，第三步第三步:输出输出x x1 1,x x2 2或无实数解或无实数解.2021/8/11 星期三30小结：小结：算法的特征是什么？算法的特征是什么？n明确性明确性n有效性有效性n有限性有限性算法的概念：算法的概念：算法通常指可以用来解决的某算法通常指可以用来解决的某一类问题的步骤或程序，这些步骤或程序必须是明一类问题的步骤或程序，这些步骤或程序必须是明确的和有效的，而且能够在有限步之内完成的确的和有效的，而且能够在有限步之内完成的.2021/8/11 星期三31作业：作业：1.写出你在家里烧开水过程的一个算法写出你在家里烧开水过程的一个算法.2.已知平面直角坐标系的两点已知平面直角坐标系的两点A(1，0)，B(3，2)，写出求直线，写出求直线AB的方程的一个算法。的方程的一个算法。2021/8/11 星期三32 下下课2021/8/11 星期三33