数学算法概念ppt课件

数学必修数学必修 3 第一章第一章 算法初步算法初步 1.1算法与程序框图算法与程序框图 1.1.1算法的概念（算法的概念（1）2011年年11月月14日日1.;算法作为一个名词，在中学课本中并没有出现过，没有学习算法作为一个名词，在中学课本中并没有出现过，没有学习过什么叫算法这个概念。但是我们对算法并不陌生，从小学过什么叫算法这个概念。但是我们对算法并不陌生，从小学就开始接触算法，熟悉许多问题的算法。如，数的四则运算就开始接触算法，熟悉许多问题的算法。如，数的四则运算要先乘除后加减，从里往外脱括弧，竖式笔算等都是算法，要先乘除后加减，从里往外脱括弧，竖式笔算等都是算法，还有乘法口诀、珠算口诀更是算法的具体体现。生活中，菜还有乘法口诀、珠算口诀更是算法的具体体现。生活中，菜谱是菜肴的算法，洗衣机的说明书是操作洗衣机的算法，歌谱是菜肴的算法，洗衣机的说明书是操作洗衣机的算法，歌谱是歌曲的算法，谱是歌曲的算法，在数学中，我们主要研究用计算机实现的在数学中，我们主要研究用计算机实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。题的程序。从小学到高中我们所学的算法很多是与计算有关从小学到高中我们所学的算法很多是与计算有关的问题。比如解方程的算法、函数求值的算法、作图的算法，的问题。比如解方程的算法、函数求值的算法、作图的算法，等等。等等。在数学课上的算法，数学课上的计算机课，与计算机课上的在数学课上的算法，数学课上的计算机课，与计算机课上的数学不一样，主要是利用计算机解决与数学有关的算术问题，数学不一样，主要是利用计算机解决与数学有关的算术问题，利用计算机解决一起我们所学过的数学问题。利用计算机解决一起我们所学过的数学问题。计算工具：古代计算工具：古代 算盘算盘 现代：计算机现代：计算机20世纪最伟大的发明：计算机，计算机是强大的实现各种算世纪最伟大的发明：计算机，计算机是强大的实现各种算法的工具。法的工具。2下面通过几个具体的生活实例体会算法的含义。下面通过几个具体的生活实例体会算法的含义。1.把苹果装入冰箱里分几步？把苹果装入冰箱里分几步？第一步：第一步：把冰箱门打开。把冰箱门打开。第二步：第二步：把苹果放进冰箱。把苹果放进冰箱。第三步：第三步：把冰箱门关上。把冰箱门关上。32.在家中烧开水的过程分几步？在家中烧开水的过程分几步？第一步：打开壶盖加水盖上盖子第一步：打开壶盖加水盖上盖子第二步：壶放在火上开火第二步：壶放在火上开火第三步：水开后关火。第三步：水开后关火。4小结：小结：这是生活中的算法，做这件事是这是生活中的算法，做这件事是有先后顺序的，逻辑性的，打乱顺序就不有先后顺序的，逻辑性的，打乱顺序就不能完成任务，分三步完成步骤缺一不可，能完成任务，分三步完成步骤缺一不可，步骤是有限的，每步的结果是明确的，每步骤是有限的，每步的结果是明确的，每步都有通用性，人们只要按照该步骤执行步都有通用性，人们只要按照该步骤执行可完成任务。谁家烧开水都会按这个顺序可完成任务。谁家烧开水都会按这个顺序完成的，只要按以上步骤做都可以完成这完成的，只要按以上步骤做都可以完成这一类问题，但他们不能用计算机来操作。一类问题，但他们不能用计算机来操作。5这是生活中的例子，这是生活中的例子，下面我们重要学习数学中的算法。下面我们重要学习数学中的算法。6知识探究（一）：算法的概念知识探究（一）：算法的概念在初中，对于解二元一次方程组你学过在初中，对于解二元一次方程组你学过哪些方法？哪些方法？用加减消元法解二元一次方程组用加减消元法解二元一次方程组 x-2y=-1 x-2y=-1 2x+y=1 2x+y=1 的具体步骤是什么？的具体步骤是什么？加减消元法和代入消元法加减消元法和代入消元法7 +2 2，得，得 5x=1.5x=1.15x 15x 15x 解，得解，得 .15x -2 2，得，得 5y5y3 3.解，得解，得 .35y 第一步，第一步，第二步，第二步，第三步，第三步，第四步，第四步，第五步，第五步，得到方程组的解为得到方程组的解为 .1535xy=yxyx12128代入消元法：代入消元法：yxyx1212解：第一步：解：第一步：-2得得5y=3；第二步：解得第二步：解得53y53y51x第三步：将第三步：将代入，得代入，得9小结：解二元一次方程组的过程小结：解二元一次方程组的过程1.步骤有一定的顺序性，打乱顺序不能步骤有一定的顺序性，打乱顺序不能完成任务完成任务2.步骤完整性缺一不可步骤完整性缺一不可3.步骤有限性步骤有限性4.每步结果明确每步结果明确5.步骤通用性，任何人只要按照步骤执步骤通用性，任何人只要按照步骤执行就可以完成这类任务行就可以完成这类任务10参照上述思路，一般地，解方程参照上述思路，一般地，解方程组组 的基的基本步骤是什么？本步骤是什么？111a xb yc222a xb yc1 22 10aba b（）112b1b第一步，第一步，-，得，得 .1 22 12 11 2()aba b xb cbc第二步，解第二步，解，得，得 .2 112122 1b cb cxa ba b 第三步，第三步，-，得，得 .1a2a1 22 11 22 1()aba b ya ca c第四步，解第四步，解，得，得 .12211221a ca cya ba b第五步，得到方程组的解为第五步，得到方程组的解为 2112122112211221b cb cxa ba ba ca cya ba b1213 在数学中，算法通常是按照一定规则在数学中，算法通常是按照一定规则解决某解决某一类一类问题的问题的明确明确和和有限有限的步骤。的步骤。一、算法的定义一、算法的定义现在算法通常可以编写成计算机程序现在算法通常可以编写成计算机程序让计算机执行并解决问题。让计算机执行并解决问题。14二、对算法定义的理解二、对算法定义的理解1在数学中在数学中 ，只针对数学中的问题，只针对数学中的问题2一定的规则：一定的规则：设计算法的依据，设计算法的依据，即不同的数学结论或方法不同的即不同的数学结论或方法不同的规则得到的算法是不同的算法。规则得到的算法是不同的算法。3某一类问题某一类问题：通用性有时也可把某：通用性有时也可把某一具体问题的步骤看成算法一具体问题的步骤看成算法4明确和有限：明确和有限：步骤最显著特征就是顺步骤最显著特征就是顺序，每一步都是明确的，在有限步内完成序，每一步都是明确的，在有限步内完成不能无限执行。不能无限执行。15三、算法的特征三、算法的特征1有限性有限性（一个算法的步骤序列是有限（一个算法的步骤序列是有限性的，必须在有限操作后停止不能无限）性的，必须在有限操作后停止不能无限）2确定性确定性（算法中的每一步都是确定的，（算法中的每一步都是确定的，并且能有效的执行且得到确定的结果，而不并且能有效的执行且得到确定的结果，而不应是摸棱两可）应是摸棱两可）3有序性有序性（前后顺序缺一不可）（前后顺序缺一不可）4不惟一性不惟一性（对于一个问题有不同的算法）（对于一个问题有不同的算法）5通用性通用性161自然语言自然语言四、算法的表现形式四、算法的表现形式2。程序框图。程序框图3。程序语句。程序语句17五、设计算法的格式五、设计算法的格式stepS1:S2:.Sn:.第一步：第一步：.第二步：第二步：.第几步：第几步：.18知识探究（二）知识探究（二）:算法的步骤设计算法的步骤设计如果让计算机判断如果让计算机判断7 7是否为质数，如何设计是否为质数，如何设计算法步骤？算法步骤？第一步，用第一步，用2 2除除7 7，得到余数，得到余数1,1,所以所以2 2不能整除不能整除7.7.第四步，用第四步，用5 5除除7 7，得到余数，得到余数2,2,所以所以5 5不能整除不能整除7.7.第五步，用第五步，用6 6除除7 7，得到余数，得到余数1,1,所以所以6 6不能整除不能整除7.7.第二步，用第二步，用3 3除除7 7，得到余数，得到余数1,1,所以所以3 3不能整除不能整除7.7.第三步，用第三步，用4 4除除7 7，得到余数，得到余数3,3,所以所以4 4不能整除不能整除7.7.因此，因此，7 7是质数是质数.19如果让计算机判断如果让计算机判断3535是否为质数，如何设计是否为质数，如何设计算法步骤？算法步骤？第一步，用第一步，用2 2除除3535，得到余数，得到余数1,1,所以所以2 2不能整除不能整除35.35.第二步，用第二步，用3 3除除3535，得到余数，得到余数2,2,所以所以3 3不能整除不能整除35.35.第三步，用第三步，用4 4除除3535，得到余数，得到余数3,3,所以所以4 4不能整除不能整除35.35.第四步，用第四步，用5 5除除3535，得到余数，得到余数0,0,所以所以5 5能整除能整除35.35.因此，因此，3535不是质数不是质数.20整数整数8989是否为质数？如果让计算机判断是否为质数？如果让计算机判断8989是否为质数，按照上述算法需要设计是否为质数，按照上述算法需要设计多少个步骤？多少个步骤？第一步，用第一步，用2 2除除8989，得到余数，得到余数1,1,所以所以2 2不能整除不能整除89.89.第二步，用第二步，用3 3除除8989，得到余数，得到余数2,2,所以所以3 3不能整除不能整除89.89.第三步，用第三步，用4 4除除8989，得到余数，得到余数1,1,所以所以4 4不能整除不能整除89.89.第八十七步，用第八十七步，用8888除除8989，得到余数，得到余数1,1,所以所以8888不能不能 整除整除89.89.因此，因此，8989是质数是质数.21用用2 28888逐一去除逐一去除8989求余数，需要求余数，需要8787个步骤，个步骤，这些步骤基本是重复操作，我们可以按下面这些步骤基本是重复操作，我们可以按下面的思路改进这个算法，减少算法的步骤的思路改进这个算法，减少算法的步骤.（1 1）用）用i i表示表示2 28888中的任意一个整数，并从中的任意一个整数，并从2 2开始取数；开始取数；（2 2）用）用i i除除8989，得到余数，得到余数r.r.若若r=0r=0，则，则8989不不是质数；若是质数；若r0r0，将，将i i用用i+1i+1替代，再执行同替代，再执行同样的操作；样的操作；（3 3）这个操作一直进行到）这个操作一直进行到i i取取8888为止为止.你能按照这个思路，设计一个你能按照这个思路，设计一个“判断判断8989是否是否为质数为质数”的算法步骤吗？的算法步骤吗？22用用i i除除8989，得到余数，得到余数r r；令令i=2i=2；若若r=0r=0，则，则8989不是质数，结束算不是质数，结束算法；若法；若r0r0，将，将i i用用i+1i+1替代；替代；判断判断“i i88”88”是否成立？若是，是否成立？若是，则则8989是质数，结束算法；否则，是质数，结束算法；否则，返回第二步返回第二步.第一步，第一步，第四步，第四步，第三步，第三步，第二步，第二步，算法设计算法设计:23一般地，判断一个大于一般地，判断一个大于2 2的整数是否为质数的整数是否为质数的算法步骤如何设计？的算法步骤如何设计？第一步，给定一个大于第一步，给定一个大于2 2的整数的整数n n；第二步，令第二步，令i=2i=2；第三步，用第三步，用i i除除n n，得到余数，得到余数r r；第四步，判断第四步，判断“r=0”r=0”是否成立是否成立.若是，则若是，则n n 不是质数，结束算法；否则，将不是质数，结束算法；否则，将i i 的值增加的值增加1 1，仍用，仍用i i表示；表示；第五步，判断第五步，判断“i i(n-1)”(n-1)”是否成立，若是，是否成立，若是，则则n n是质数，结束算法；否则，返回是质数，结束算法；否则，返回 第三步第三步.24例：例：写出解方程写出解方程x22x30的一个的一个算法。算法。解：算法解：算法1：第一步：移项，得第一步：移项，得x22x3；第二步：式两边同加第二步：式两边同加1得得x22x+14第三步：两边配方，得（第三步：两边配方，得（x1）24 第四步：式两边开方，得第四步：式两边开方，得x12 第五步：解得第五步：解得x3或或x1。25算法算法2：第一步：计算方程的判别式判断其符号第一步：计算方程的判别式判断其符号2243160；aacbb242第二步：将第二步：将a1，b2，c3代入求根公式代入求根公式x得得x13，x2126下面设计一个求一般的一元二次方程下面设计一个求一般的一元二次方程ax2bxc0的根的算法如下：的根的算法如下：第一步：输入第一步：输入a,b,c第二步：计算第二步：计算b24ac；第三步：若第三步：若0；则输出方程无实根；则输出方程无实根；第四步：若第四步：若0；计算并输出方程根；计算并输出方程根x1,2aacbb24227数值性计算：数值性计算：解方程、解不等式、解方程、解不等式、套用公式判断性问题累加累乘套用公式判断性问题累加累乘算法问题分为：算法问题分为：数值性计算和非数值性计算数值性计算和非数值性计算非数值性计算；非数值性计算；文字处理、排序、文字处理、排序、变量交换变量交换28例：例：写出一个求整数写出一个求整数a、b、c最大值的算法最大值的算法解解：S1 ：max=aS2：如果：如果bmax，则，则max=bS3：如果：如果cmax，则，则max=cS4：max就是就是a、b、c的最大值。的最大值。29例例 用二分法设计一个求方程用二分法设计一个求方程 的近似根的算法的近似根的算法.022 x设所求近似根与精确解的差的绝对值设所求近似根与精确解的差的绝对值不超过不超过0.0053031练习练习、有蓝和黑两个墨水瓶，但现在却错把蓝墨水有蓝和黑两个墨水瓶，但现在却错把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这瓶中，要求将其互换，请你设计算法解决这一问题。一问题。由于两个墨水瓶中的墨水不能直接交换，由于两个墨水瓶中的墨水不能直接交换，故可以考虑通过引入第三个空墨水瓶的故可以考虑通过引入第三个空墨水瓶的办法进行交换。办法进行交换。32解：算法步骤如下：解：算法步骤如下：第一步：取一只空的墨水瓶，设其为白色；第一步：取一只空的墨水瓶，设其为白色；第二步：将黑墨水瓶中的蓝墨水装入白瓶中；第二步：将黑墨水瓶中的蓝墨水装入白瓶中；第三步：将蓝墨水瓶中的黑墨水装入黑瓶中；第三步：将蓝墨水瓶中的黑墨水装入黑瓶中；第四步：将白瓶中的蓝墨水装入蓝瓶中；第四步：将白瓶中的蓝墨水装入蓝瓶中；第五步：交换结束。第五步：交换结束。33 算法是建立在解法基础上的操作过程，算算法是建立在解法基础上的操作过程，算法不一定要有运算结果，问题答案可以由法不一定要有运算结果，问题答案可以由计算机解决设计一个解决某类问题的算计算机解决设计一个解决某类问题的算法的核心内容是设计算法的步骤，它没有法的核心内容是设计算法的步骤，它没有一个固定的模式，但有以下几个基本要求：一个固定的模式，但有以下几个基本要求：(1)符合运算规则，计算机能操作；符合运算规则，计算机能操作；(2)每个步骤都有一个明确的计算任务；每个步骤都有一个明确的计算任务；(3)对重复操作步骤作返回处理；对重复操作步骤作返回处理；(4)步骤个数尽可能少；步骤个数尽可能少；(5)每个步骤的语言描述要准确、简明每个步骤的语言描述要准确、简明.34