《11-12高中数学 111 算法的概念1课件 新人教b版必修3.ppt》由会员分享，可在线阅读，更多相关《11-12高中数学 111 算法的概念1课件 新人教b版必修3.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、11-12学年高中数学学年高中数学 111 算法的概念算法的概念1课件课件 新人教新人教B版必修版必修3一、复习引入一、复习引入 算法作为一个名词，在中学教科书中并没有出现过，算法作为一个名词，在中学教科书中并没有出现过，我们在基础教育阶段还没有接触算法概念。但是我们却从我们在基础教育阶段还没有接触算法概念。但是我们却从小学就开始接触算法，熟悉许多问题的算法。如，做四则小学就开始接触算法，熟悉许多问题的算法。如，做四则运算要先乘除后加减，从里往外脱括弧，竖式笔算等都是运算要先乘除后加减，从里往外脱括弧，竖式笔算等都是算法，至于乘法口诀、珠算口诀更是算法的具体体现。广算法，至于乘法口诀、珠算口诀
2、更是算法的具体体现。广义地说，义地说，算法就是做某一件事的步骤或程序。算法就是做某一件事的步骤或程序。菜谱是做菜菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。在谱是一首歌曲的算法。在数学中，主要研究计算机能实现数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解的算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序决问题的程序。( (古代的计算工具：算筹与算盘古代的计算工具：算筹与算盘. 20. 20世纪最世纪最伟大的发明：计算机，计算机是强大的实现各种算法的工伟大的发明：计算
3、机，计算机是强大的实现各种算法的工具。具。) )一、复习引入一、复习引入 要把大象装冰箱，分几步？哈哈要把大象装冰箱，分几步？哈哈问：问：2、现有九枚硬币，有一枚略重，你能用天平、现有九枚硬币，有一枚略重，你能用天平(不用不用砝码砝码)将其找出来吗？设计一种最有效的方法，解将其找出来吗？设计一种最有效的方法，解决这一问题。决这一问题。S1S1：把九枚硬币平均分成三份，取其中两份放天平上称，：把九枚硬币平均分成三份，取其中两份放天平上称，若平衡则重的在剩下的一份里，若不平衡则在重的一份里；若平衡则重的在剩下的一份里，若不平衡则在重的一份里；S2S2：在重的一份里取两枚放天：在重的一份里取两枚放天
4、平的两边，若平衡则剩下的一平的两边，若平衡则剩下的一枚就是所找的，若不平衡则重枚就是所找的，若不平衡则重的那枚就是所要找的。的那枚就是所要找的。二、提出问题二、提出问题二、提出问题二、提出问题3.3.一个农夫带着一只狼、一头山羊和一篮蔬菜要过一个农夫带着一只狼、一头山羊和一篮蔬菜要过河，但只有一条小船。乘船时河，但只有一条小船。乘船时, ,农夫只能带一样东农夫只能带一样东西。当农夫在场的时候西。当农夫在场的时候, ,这三样东西相安无事，一这三样东西相安无事，一旦农夫不在，狼会吃羊，羊会吃菜。请设计一个方旦农夫不在，狼会吃羊，羊会吃菜。请设计一个方案，使农夫能安全地将这三样东西带过河。案，使农夫
5、能安全地将这三样东西带过河。S1:S1:农夫带羊过河农夫带羊过河; ;S2:S2:农夫独自回来农夫独自回来; ;S3:S3:农夫带狼过河农夫带狼过河; ;S4:S4:农夫带羊回来农夫带羊回来; ;S5:S5:农夫带蔬菜过河农夫带蔬菜过河; ;S6:S6:农夫独自回来农夫独自回来; ;S7:S7:农夫带羊过河。农夫带羊过河。 算法通常指可以用来解决的某一类问题的步算法通常指可以用来解决的某一类问题的步骤或程序，这些步骤或程序必须是明确的和有效骤或程序，这些步骤或程序必须是明确的和有效的，而且能够在有限步之内完成的。的，而且能够在有限步之内完成的。三、概念形成三、概念形成概念概念1.1.算法（算法
6、（algorithmalgorithm） 一般来说，一般来说，“用算法解决问题用算法解决问题” ” 可以利用计可以利用计算机帮助完成。算机帮助完成。四、应用举例四、应用举例例例1.1.写出交换两个大小相同的杯子中的液体写出交换两个大小相同的杯子中的液体(A(A水、水、 B B酒酒) ) 的一个算法。的一个算法。S1S1：找一个大小与：找一个大小与A A相同的空杯子相同的空杯子C C。酒酒B B空空C C水水A A四、应用举例四、应用举例例例1.1.写出交换两个大小相同的杯子中的液体写出交换两个大小相同的杯子中的液体(A(A水、水、 B B酒酒) ) 的一个算法。的一个算法。S1S1：找一个大小
7、与：找一个大小与A A相同的空杯子相同的空杯子C C。S2S2：将：将A A中的水倒入中的水倒入C C中。中。酒酒B B水水C C空空A A四、应用举例四、应用举例例例1.1.写出交换两个大小相同的杯子中的液体写出交换两个大小相同的杯子中的液体(A(A水、水、 B B酒酒) ) 的一个算法。的一个算法。S1S1：找一个大小与：找一个大小与A A相同的空杯子相同的空杯子C C。S2S2：将：将A A中的水倒入中的水倒入C C中。中。S3S3：将：将B B中的酒精倒入中的酒精倒入A A中。中。空空B B水水C C酒酒A A四、应用举例四、应用举例例例1.1.写出交换两个大小相同的杯子中的液体写出交
8、换两个大小相同的杯子中的液体(A(A水、水、 B B酒酒) ) 的一个算法。的一个算法。S1S1：找一个大小与：找一个大小与A A相同的空杯子相同的空杯子C C。S4S4：将：将C C中的水倒入中的水倒入B B中，结束。中，结束。S2S2：将：将A A中的水倒入中的水倒入C C中。中。S3S3：将：将B B中的酒精倒入中的酒精倒入A A中。中。水水B B空空C C酒酒A A四、应用举例四、应用举例例例2.2.写出求一元二次方程写出求一元二次方程axax2 2+bx+c=0+bx+c=0的根的算法的根的算法. .S1S1：计算：计算=b=b2 2-4ac.-4ac.S2S2：判断，如果：判断，如
9、果0,0,则原方程无实数解；否则则原方程无实数解；否则(0)(0)时，时，12,.22bbxxaa S3S3：输出：输出x x1 1, x, x2 2或无实数解的信息或无实数解的信息. .例例3.3.解二元一次方程组解二元一次方程组 2121xyxy 分析：解二元一次方程组的主要思想是消元的思想，有代分析：解二元一次方程组的主要思想是消元的思想，有代入消元和加减消元两种消元的方法，下面用加减消元法写入消元和加减消元两种消元的方法，下面用加减消元法写出它的求解过程出它的求解过程 解：解：S1S1： - - 2 2，得：，得： 5y=35y=3； S2S2：解：解得得 35y S3S3：将：将 代
10、入代入，得，得 35y 15x S4 S4：结论：结论： 1535xy本题的算法是由加减消元法求解本题的算法是由加减消元法求解的，这个算法也适合一般的二元的，这个算法也适合一般的二元一次方程组的解法。一次方程组的解法。四、应用举例四、应用举例加减消元法解二元一次方程组的算法加减消元法解二元一次方程组的算法( (利用计算机利用计算机) ) 1111 22 1222,0a xb ycaba ba xb ycS2：解：解 得得 122 11221a ca cya ba bS3：将：将 代入代入， 得得 12211221a ca cya ba b2 1121221bb ccxa ba bS1： 得得
11、- 2 a1 22 11 22 1()a ba b ya ca c1 a四、应用举例四、应用举例四、应用举例四、应用举例例例4.(1)4.(1)设计一个算法判断设计一个算法判断7 7是否为质数。是否为质数。S1S1：用：用2 2除除7 7，得到余数，得到余数1 1。因为余数不为。因为余数不为0 0，所以，所以2 2不能整除不能整除7 7。S2S2：用：用3 3除除7 7，得到余数，得到余数1 1。因为余数不为。因为余数不为0 0，所以，所以3 3不能整除不能整除7 7。S3S3：用：用4 4除除7 7，得到余数，得到余数3 3。因为余数不为。因为余数不为0 0，所以，所以4 4不能整除不能整除
12、7 7。S4S4：用：用5 5除除7 7，得到余数，得到余数2 2。因为余数不为。因为余数不为0 0，所以，所以5 5不能整除不能整除7 7。S5S5：用：用6 6除除7 7，得到余数，得到余数1 1。因为余数不为。因为余数不为0 0，所以，所以6 6不能整除不能整除7 7。因此，。因此，7 7是质数。是质数。四、应用举例四、应用举例例例4.(2)4.(2)设计一个算法判断设计一个算法判断3535是否为质数。是否为质数。S1S1：用：用2 2除除3535，得到余数，得到余数1 1。因为余数不为。因为余数不为0 0，所以，所以2 2不能整除不能整除3535。S2S2：用：用3 3除除3535，得
13、到余数，得到余数2 2。因为余数不为。因为余数不为0 0，所以，所以3 3不能整除不能整除3535。S3S3：用：用4 4除除3535，得到余数，得到余数3 3。因为余数不为。因为余数不为0 0，所以，所以4 4不能整除不能整除7 7。S4S4：用：用5 5除除3535，得到余数，得到余数0 0。因为余数为。因为余数为0 0，所以，所以5 5能能整除整除3535。因此，。因此，3535不是质数。不是质数。四、应用举例四、应用举例例例4.(3)4.(3)设计一个算法判断整数设计一个算法判断整数n(nn(n2 2）是否为质是否为质数。数。S1S1：给定大于：给定大于2 2的整数的整数n n。S2S
14、2：令：令i=2i=2。S3S3：用：用i i除除n n，得余数，得余数r r。S4S4：判断：判断“r=0”r=0”是否成立，若成立，则是否成立，若成立，则n n不是质数，不是质数，结束算法；否则，将结束算法；否则，将i+1i+1后返回第三步。后返回第三步。四、应用举例四、应用举例 在数学中，现代意义上的在数学中，现代意义上的 “ “算法算法”通常是指通常是指可以用计算机来解决的某一类问题的程序或步骤，可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成在有限步之内完成. .2.2.算法的要求：算法的
15、要求：(1)(1)写出的算法，必须能解决一类问题写出的算法，必须能解决一类问题( (例如解任意例如解任意一个二元一次方程组一个二元一次方程组) )，并且能重复使用；，并且能重复使用；(2)(2)算法过程要能一步一步执行，每一步执行的操算法过程要能一步一步执行，每一步执行的操作作, ,必须确切，不能含混不清，而且在有限步之内必须确切，不能含混不清，而且在有限步之内完成后能得出结果。完成后能得出结果。1.1.算法定义的理解：算法定义的理解：四、应用举例四、应用举例3.3.算法的基本特征算法的基本特征: :明确性：明确性：算法对每一个步骤都有确切的，能有效算法对每一个步骤都有确切的，能有效执行且得到
16、确定结果的，不能模棱两可。执行且得到确定结果的，不能模棱两可。顺序与正确性：顺序与正确性：算法从初始步骤开始，分为若干算法从初始步骤开始，分为若干明确的步骤，每一步都只能有一个确定的继任者，明确的步骤，每一步都只能有一个确定的继任者，只有执行完前一步才能进入到后一步，并且每一步只有执行完前一步才能进入到后一步，并且每一步都确定无误后，才能解决问题。都确定无误后，才能解决问题。有限性：有限性：算法应由有限步组成，至少对某些输入算法应由有限步组成，至少对某些输入，算法应在有限多步内结束，并给出计算结果。，算法应在有限多步内结束，并给出计算结果。不唯一性：不唯一性：求解某一个问题的解法不一定是唯一求
17、解某一个问题的解法不一定是唯一的，对于同一个问题可以有不同的解法。的，对于同一个问题可以有不同的解法。四、应用举例四、应用举例算法算法2:2:S1S1：取：取n=100n=100；S3S3：输出运算结果。：输出运算结果。S2S2：计算：计算(1)2n n点评点评: :算法算法1 1繁琐繁琐, ,步骤较多；步骤较多；算法算法2 2简单，步骤较少。找出简单，步骤较少。找出好的算法是我们的追求目标。好的算法是我们的追求目标。例例5 5、给出求、给出求1+2+3+1+2+3+99+99+100+100的一个算法。的一个算法。算法算法1 1：S2S2：使：使S=1S=1，i=2i=2；S3S3：使：使S
18、 S的值变为的值变为S+iS+i，i i的值增加的值增加1 1；S4S4：若：若i i100100，则输出，则输出S S，否则转到，否则转到S3S3；S1S1：给出两变量：给出两变量S,iS,i；四、应用举例四、应用举例例例6.6.用二分法设计一个求方程用二分法设计一个求方程 的近似正的近似正根的算法，精确度根的算法，精确度0.0050.005。220 x 算法分析算法分析: :回顾二分法解方程的过程回顾二分法解方程的过程, ,假设所求近似根与精假设所求近似根与精确解的差的绝对值不超过确解的差的绝对值不超过0.005,0.005,则不难设计出以下步骤：则不难设计出以下步骤：S1S1：令：令f(
19、x)=xf(x)=x2 2-2-2，因为，因为f(1)0f(1)0,f(2)0,所以设所以设a=1,b=2a=1,b=2。S2S2：令：令m= , m= , 判断判断f(m)f(m)是否为是否为0 0。若是。若是0 0，则，则m m为所求；为所求；若否，则继续判断若否，则继续判断f(a)f(m)f(a)f(m)大于大于0 0还是小于还是小于0 0 。2ab S3S3：若：若f(a)f(m) 0f(a)f(m) 0，则令，则令a=ma=m；否则，令；否则，令b=m b=m 。S4:S4:判断判断 |a-b|0.005|a-b|0.005是否成立？若是，则是否成立？若是，则a a或或b(b(或任意
20、值或任意值) )为为满足条件的近似根；若否，则返回满足条件的近似根；若否，则返回S2S2。评析评析: :实际上实际上, ,上述步骤就是在求上述步骤就是在求 的近似值。的近似值。2 2例例7.7.现有有限个实数，怎样从中找出最大值？现有有限个实数，怎样从中找出最大值？S1S1：先假定这些实数中的第一个数为：先假定这些实数中的第一个数为“最大值最大值”。S2S2：将这些实数中的下一个数与：将这些实数中的下一个数与“最大值最大值”比较，比较，如果它大于此如果它大于此“最大值最大值”，这时就假定，这时就假定“最大值最大值”是这个实数。是这个实数。S3S3：如果还有其他实数，重复：如果还有其他实数，重复
21、S2S2。S4S4：一直到没有可比的数为止，这时假定的：一直到没有可比的数为止，这时假定的“最大最大值值”就是这有限个实数的最大值。就是这有限个实数的最大值。四、应用举例四、应用举例例例8.8.应用应用ScilabScilab计算指令解方程组：（体会计算计算指令解方程组：（体会计算机的应用）机的应用）四、应用举例四、应用举例32142xyxy 五、课堂练习五、课堂练习思思考考课本第课本第7 7页，练习页，练习A A，1 1，2 2，3,43,421.430 xx写出解的算法。2.2.算法的特点：算法的特点：思路简单清晰，叙述复杂，步骤繁思路简单清晰，叙述复杂，步骤繁琐，计算量大，完全依靠人力难
22、以完成。而这些恰琐，计算量大，完全依靠人力难以完成。而这些恰恰就是计算机的特长，它能不厌其烦地完成枯燥的、恰就是计算机的特长，它能不厌其烦地完成枯燥的、重复的繁琐的工作。正因为这些，现代算法的作用重复的繁琐的工作。正因为这些，现代算法的作用之一就是使计算机代替人完成某些工作，这也是我之一就是使计算机代替人完成某些工作，这也是我们学习算法的重要原因之一。们学习算法的重要原因之一。六、课堂总结六、课堂总结1.1.知识结构知识结构算法的概念算法的概念算法的步骤算法的步骤 算法的特点算法的特点算法算法六、课堂总结六、课堂总结3.3.设计算法的注意事项设计算法的注意事项: : (1)(1)认真分析问题，联系解决此问题的一般数学方认真分析问题，联系解决此问题的一般数学方法；法；(2)(2)综合考虑此类问题中可能涉及的各种情况；综合考虑此类问题中可能涉及的各种情况；(3)(3)借助有关的变量或参数对算法加以表达；借助有关的变量或参数对算法加以表达；(4)(4)将解决问题的过程划分为若干个步骤；将解决问题的过程划分为若干个步骤；(5)(5)然后用简练的语言将各个步骤表示出来。然后用简练的语言将各个步骤表示出来。七、布置作业七、布置作业课本第课本第7 7页，练习页，练习B B，1 1，2 2，3 3