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