《北师大版数学必修三：2.1算法的基本思想ppt课件》由会员分享，可在线阅读，更多相关《北师大版数学必修三：2.1算法的基本思想ppt课件（36页珍藏版）》请在金锄头文库上搜索。
1、数 学 精 品 课 件北 师 大 版第二章 算法初步1 算法的基本思想 作为家里的一员，在平时分担一些力所能及的作为家里的一员，在平时分担一些力所能及的家务是我们应尽的义务，你每天都帮家里做家务吗家务是我们应尽的义务，你每天都帮家里做家务吗？你会烧开水吗？请写出你在家中烧开水的过程？你会烧开水吗？请写出你在家中烧开水的过程. .1.1.往壶内注水；往壶内注水；2.2.点火加热；点火加热；3.3.观察：如果水开，则停止烧火，否则继续观察：如果水开，则停止烧火，否则继续烧火；烧火；4.4.如果水未开，重复过程如果水未开，重复过程 “3 3”，直至水开，直至水开. .【小结小结】1.1.其实大部分事
2、情都是按照一定的程序执行的，其实大部分事情都是按照一定的程序执行的，因此要理清事情的每一步因此要理清事情的每一步. .2.2.判断水是否烧开与是否继续烧火的过程是一判断水是否烧开与是否继续烧火的过程是一个反馈与判断的过程，因此有必要不断重复过个反馈与判断的过程，因此有必要不断重复过程程“3 3”. . 事实上，我们完成任何事，都要有步骤，合理事实上，我们完成任何事，都要有步骤，合理安排步骤，这样会达到事半功倍的效果安排步骤，这样会达到事半功倍的效果. .从我们数从我们数学的意义来讲，在解决某些问题时，需要设计出一学的意义来讲，在解决某些问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些
3、步骤来系列可操作或可计算的步骤，通过实施这些步骤来解决问题，我们通常把这些步骤称为解决问题的一解决问题，我们通常把这些步骤称为解决问题的一种算法种算法. .这种描述不是算法的定义，但反映了算法这种描述不是算法的定义，但反映了算法的基本思想的基本思想. . 随着计算科学和信息技术的飞速发展，算法的随着计算科学和信息技术的飞速发展，算法的思想已经渗透到社会的方方面面思想已经渗透到社会的方方面面. .在以前的学习中，在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量的算法思想，如四则运算的过程、中已经渗透了大量的算法思想，如四则运
4、算的过程、求解方程的步骤等求解方程的步骤等. .完成这些工作都需要一系列程序完成这些工作都需要一系列程序化的步骤，这就是算法的思想化的步骤，这就是算法的思想. . 1.1.了解算法的含义，形成算法的初步印象，体会算了解算法的含义，形成算法的初步印象，体会算法是解决问题的法是解决问题的“机械机械”程序，并能在有限步内解程序，并能在有限步内解决问题；决问题；2.2.能够用自然语言叙述算法；能够用自然语言叙述算法；3.3.掌握正确的算法应满足的条件；掌握正确的算法应满足的条件；（重点）（重点）4.4.会写出简单问题的算法会写出简单问题的算法. .（难点）（难点）例例1 1 在电视台的某个娱乐节目中，
5、要求参与者快在电视台的某个娱乐节目中，要求参与者快速猜出物品价格速猜出物品价格. .主持人出示某件物品，参与者每主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或次估算出一个价格，主持人只能回答高了、低了或者正确者正确. .在某次节目中，主持人出示了一台价值在在某次节目中，主持人出示了一台价值在1 1 000000元以内的随身听，并开始了竞猜元以内的随身听，并开始了竞猜. .下面是主持人下面是主持人和参与者之间的一段对话：和参与者之间的一段对话：参与者：参与者：800800元！元！主持人：高了！主持人：高了！参与者：参与者：400400元！元！主持人：低了！主持人：低了！
6、参与者：参与者：600600元！元！主持人：低了主持人：低了! !如果你是参与者，你接下来会怎么猜？如果你是参与者，你接下来会怎么猜？实际上，可以把过程概括如下：实际上，可以把过程概括如下：按照上述方法，继续判断，直到游戏结束按照上述方法，继续判断，直到游戏结束. .像这样像这样的一系列步骤通常称为解决这个问题的一个算法的一系列步骤通常称为解决这个问题的一个算法. .例例2 2 在给定素数表的条件下，设计算法，将在给定素数表的条件下，设计算法，将936936分解成分解成素因数的乘积素因数的乘积.(4 000.(4 000以内的素数表见课本附录以内的素数表见课本附录1)1)解解: :算法步骤如下
7、：算法步骤如下：1.1.判断判断936936是否为素数：否是否为素数：否. .2.2.确定确定936936的最小素因数：的最小素因数：2. 936=22. 936=2468.468.3.3.判断判断468468是否为素数：否是否为素数：否. .4.4.确定确定468468的最小素因数：的最小素因数：2. 936=22. 936=22 2234.234.5.5.判断判断234234是否为素数：否是否为素数：否. .6.6.确定确定234234的最小素因数：的最小素因数：2. 936=22. 936=22 22 2117.117.7.7.判断判断117117是否为素数：否是否为素数：否. .8.8
8、.确定确定117117的最小素因数：的最小素因数：3. 936=23. 936=22 22 23 339.39.9.9.判断判断3939是否为素数：否是否为素数：否. .10.10.确定确定3939的最小素因数：的最小素因数：3. 936=23. 936=22 22 23 33 313.13.11.11.判断判断1313是否为素数：是否为素数：1313是素数，所以分解结束是素数，所以分解结束. .分解结果是：分解结果是： 936=2936=22 22 23 33 313.13. 按照以上程序，完成了对按照以上程序，完成了对936936的素因数分解的素因数分解. .实际实际上，在给定素数表的基础
9、上，对任意自然数上，在给定素数表的基础上，对任意自然数n n，都可，都可以按照上述办法进行分解以按照上述办法进行分解. . 以上步骤是解决素因数分解问题的一个过程，只以上步骤是解决素因数分解问题的一个过程，只要依照这一系列步骤，都能解决这个问题，我们把这要依照这一系列步骤，都能解决这个问题，我们把这一系列步骤称为解决这个问题的一个算法一系列步骤称为解决这个问题的一个算法. . 例例3 3 设计一个算法，求设计一个算法，求840840与与1 7641 764的最大公因数的最大公因数. .1.1.先将先将840840进行素因数分解：进行素因数分解： ；2.2.然后将然后将1 7641 764进行素
10、因数分解：进行素因数分解： ；3.3.确定它们的公共素因数确定它们的公共素因数:2,3,7:2,3,7；4.4.确定公共素因数的指数：公共素因数确定公共素因数的指数：公共素因数2,3,72,3,7的指数的指数分别为分别为2,1,1;2,1,1;5.5.最大公因数为最大公因数为: : . .解：解：算法步骤如下：算法步骤如下： 以上步骤就是求两个正整数的最大公因数的一以上步骤就是求两个正整数的最大公因数的一个算法个算法. .这个算法的思想具有一般性，它可以帮助设这个算法的思想具有一般性，它可以帮助设计求三个或者三个以上正整数的最大公因数的算法计求三个或者三个以上正整数的最大公因数的算法. . 通
11、过以上的例子可以看出，算法是解决某类问通过以上的例子可以看出，算法是解决某类问题的一系列步骤或程序，只要按照这些步骤执行，题的一系列步骤或程序，只要按照这些步骤执行，都能使问题得到解决，一般来说，都能使问题得到解决，一般来说，“用算法解决问用算法解决问题题”都是可以利用计算机帮助完成的都是可以利用计算机帮助完成的. .例例4 4 “韩信点兵韩信点兵”问题问题. .韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为建立汉朝立下了汗马功劳群，为建立汉朝立下了汗马功劳. .据说他在点兵的时候，据说他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的
12、实力，为了保住军事机密，不让敌人知道自己部队的实力，采用下述点兵方法：先令士兵从采用下述点兵方法：先令士兵从1 13 3报数，结果最后报数，结果最后一个士兵报一个士兵报2 2；再令士兵从；再令士兵从1 15 5报数，结果最后一个士报数，结果最后一个士兵报兵报3 3；又令士兵从；又令士兵从1 17 7报数，结果最后一个士兵报报数，结果最后一个士兵报4.4.这样，韩信很快就算出了自己部队士兵的总人数这样，韩信很快就算出了自己部队士兵的总人数. .请设请设计一个算法，求出士兵至少有多少人计一个算法，求出士兵至少有多少人? ?分析：分析：从报数情况分析，总人数除以从报数情况分析，总人数除以3 3余余2
13、 2；总人数；总人数除以除以5 5余余3 3；总人数除以；总人数除以7 7余余4.4.算法的第一步是将所有算法的第一步是将所有的除以的除以3 3余余2 2的正整数找出来，按从小到大排成一列的正整数找出来，按从小到大排成一列. .第二步是从第一步的数列中找出除以第二步是从第一步的数列中找出除以5 5余余3 3的一列数，的一列数，按从小到大排成一列按从小到大排成一列. .最后在满足前两个条件的第二最后在满足前两个条件的第二步数列中再找出除以步数列中再找出除以7 7余余4 4的一列数，这列数中最小的一列数，这列数中最小的数，即为我们所求的数的数，即为我们所求的数. .1.1.首先确定最小的满足除以首
14、先确定最小的满足除以3 3余余2 2的正整数：的正整数：2;2;解：解：具体算法步骤如下：具体算法步骤如下：5.5.在第在第4 4步得到的一列数中找出满足除以步得到的一列数中找出满足除以7 7余余4 4的最的最小数小数53,53,这就是我们要求的数这就是我们要求的数. .4.4.然后依次加上然后依次加上1515，得到，得到8 8，2323，3838，53 53 ，显显然这些数既满足除以然这些数既满足除以3 3余余2 2，又满足除以，又满足除以5 5余余3;3;3.3.在上列数中确定最小的满足除以在上列数中确定最小的满足除以5 5余余3 3的正整数：的正整数：8;8;2.2.依次加依次加3 3就
15、得到所有除以就得到所有除以3 3余余2 2的正整数：的正整数：2 2，5 5，8 8，1111，1414，1717，2020，2323，2626，2929，3232，3535，3838，4141，4444，4747，5050，5353，5656，3.3.算法要简洁，要清晰可读，不能繁杂，易程序化算法要简洁，要清晰可读，不能繁杂，易程序化. .算法不同于求解一个具体问题的方法，是这算法不同于求解一个具体问题的方法，是这种方法的高度概括种方法的高度概括. .一个好的算法有如下要求：一个好的算法有如下要求：1.1.写出的算法，必须能解决一类问题（如一元二次方写出的算法，必须能解决一类问题（如一元二次
16、方程求根公式），并且能重复使用程求根公式），并且能重复使用. .2.2.算法过程要能一步一步执行，每步执行的操作，必须算法过程要能一步一步执行，每步执行的操作，必须确切，不能含混不清，而且在有限步后能得出结果确切，不能含混不清，而且在有限步后能得出结果. .例例5. 5. 一位商人有一位商人有9 9枚银元，其中有枚银元，其中有1 1枚略轻的是假银元枚略轻的是假银元. .你能用天平（不用砝码）将假银元找出来吗？你能用天平（不用砝码）将假银元找出来吗？解解: : 1. 1.把银元分成把银元分成3 3组，每组组，每组3 3枚枚. . 2.2.先将两组分别放在天平的两边先将两组分别放在天平的两边. .
17、如果天平不平衡，那如果天平不平衡，那 么假银元就在轻的那一组；如果天平左右平衡，则假银么假银元就在轻的那一组；如果天平左右平衡，则假银元就在未称的第元就在未称的第3 3组里组里. .3.3.取出含假银元的那一组，从中任取两枚银元放在天平取出含假银元的那一组，从中任取两枚银元放在天平的两边的两边. .如果左右不平衡，则轻的那一边就是假银元；如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则未称的那一枚就是假银元如果天平两边平衡，则未称的那一枚就是假银元. .算法是什么？算法是什么？算法可以理解为由基本运算及规定的运算顺序算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤，或看
18、成按要求设计好的、构成的完整的解题步骤，或看成按要求设计好的、有限的、确切的计算序列，并且这样的步骤或序有限的、确切的计算序列，并且这样的步骤或序列能解决一类问题列能解决一类问题. .现代意义上的现代意义上的“算法算法”通常是指可以用计算机通常是指可以用计算机来解决的某一类问题的程序或步骤来解决的某一类问题的程序或步骤. .说明：说明：1.1.算法实际上就是解决某一类问题的步骤和方法，算法实际上就是解决某一类问题的步骤和方法，在解决问题时形成的规律性的东西，按照算法描在解决问题时形成的规律性的东西，按照算法描述的规则与步骤，一步一步地去做，最终便能解述的规则与步骤，一步一步地去做，最终便能解决
19、问题决问题. .2.2.算法的基本思想就是我们分析问题时的想法算法的基本思想就是我们分析问题时的想法. .由由于想法不同、思考的角度不同，着手点不一样，于想法不同、思考的角度不同，着手点不一样，同一问题存在不同的算法，算法有优劣之分同一问题存在不同的算法，算法有优劣之分. .3.3.从熟悉的问题出发，体会算法的程序化思想，从熟悉的问题出发，体会算法的程序化思想，学会用自然语言来描述算法学会用自然语言来描述算法. .在函数的应用部分，我们学习了用二分法求方程在函数的应用部分，我们学习了用二分法求方程f(x)=0f(x)=0的近似解，二分法求方程近似解的基本思想的近似解，二分法求方程近似解的基本思
20、想是：将方程的有解区间平分为两个小区间，然后判是：将方程的有解区间平分为两个小区间，然后判断解在哪个小区间；继续把有解的区间一分为二进断解在哪个小区间；继续把有解的区间一分为二进行判断，如此周而复始，直到求出满足精度要求的行判断，如此周而复始，直到求出满足精度要求的近似解近似解. .其算法步骤如下其算法步骤如下5.5.判断新的有解区间的长度是否大于精度判断新的有解区间的长度是否大于精度: :(1)(1)如果新的有解区间长度大于精度如果新的有解区间长度大于精度, ,则在新的有则在新的有解区间的基础上重复相应步骤解区间的基础上重复相应步骤; ;(2)(2)如果新的有解区间长度小于或等于精度如果新的
21、有解区间长度小于或等于精度, ,则这则这个有解区间中的任意一个数均为方程的满足精度个有解区间中的任意一个数均为方程的满足精度的近似解的近似解. .3.3.计算计算f(0.5)=-0.625;f(0.5)=-0.625;例例6 6；6.6.计算计算f(0.75)=-0.015 625;f(0.75)=-0.015 625;9.9.计算计算f(0.875)=0.435 546 875;f(0.875)=0.435 546 875;10.10.由于由于f(0.75)f(0.875)0,f(0.75)f(0.875)0.1;0.75,0.875,0.875-0.75=0.1250.1; ;12.12.
22、计算计算f(0.812 5)=0.196 533 203 125;f(0.812 5)=0.196 533 203 125;所以，区间所以，区间0.75,0.812 50.75,0.812 5中的任一数值，都可中的任一数值，都可以作为方程的近似解以作为方程的近似解. .13.13.因因f(0.75) f(0.812 5)f(0.75) f(0.812 5)0 0，得有解区间，得有解区间0.75,0.812 50.75,0.812 5，0.812 5-0.75=0.062 50.812 5-0.75=0.062 50.1.0.1.1.1.令令f(x)=xf(x)=x3 3+x+x2 2-1,-1
23、,因为因为f(0)f(1)0,f(0)f(1)0,)f(m)0,则令则令x x1 1= m;= m;否则否则, ,令令x x2 2= m.= m.简化写法简化写法: :4.4.判断判断|x|x1 1-x-x2 2|0.1|0.1是否成立，若是是否成立，若是, ,则则x x1 1,x,x2 2之间之间的任意值为满足条件的近似解的任意值为满足条件的近似解; ;若否若否, ,则返回则返回2.2.算法的特征算法的特征: : 有穷性：有穷性：一个算法应当包含有限的操作步骤而不应当一个算法应当包含有限的操作步骤而不应当是无限的是无限的; ; 确定性：确定性：算法中每一个步骤应当是确定的，而不应算法中每一个
24、步骤应当是确定的，而不应当是含糊的、模棱两可的当是含糊的、模棱两可的; ;有效性：有效性：算法中的每一个步骤应当能有效地执行，算法中的每一个步骤应当能有效地执行，并得到确定的结果并得到确定的结果. .输入输入: :有零个或多个输入有零个或多个输入; ;输出输出: :有一个或多个输出有一个或多个输出; ;1.1.下列语句中是算法的个数为（）下列语句中是算法的个数为（）从济南到巴黎：先从济南坐火车到北京，再坐飞机从济南到巴黎：先从济南坐火车到北京，再坐飞机到巴黎；到巴黎；统筹法中统筹法中“烧水泡茶烧水泡茶”的故事；的故事；测量某棵树的高度，判断其是否是大树；测量某棵树的高度，判断其是否是大树；已知
25、三角形的一部分边长和角，借助正余弦定理求已知三角形的一部分边长和角，借助正余弦定理求得剩余的边角，再利用三角形的面积公式求出该三角得剩余的边角，再利用三角形的面积公式求出该三角形的面积形的面积A.1 B.2 C.3 D.4A.1 B.2 C.3 D.4C C2.2.设计一个算法求三角形的面积，把下列步骤补充设计一个算法求三角形的面积，把下列步骤补充完整：完整：(1)(1)求出三角形的底边长；求出三角形的底边长；(2)_(2)_；(3)(3)根据三角形的面积公式求出三角形的面积根据三角形的面积公式求出三角形的面积. .【解析解析】由题意知由题意知, ,第（第（2 2）步应为求底边上的高）步应为求
26、底边上的高. .求底边上的高求底边上的高3.3.一个人带三只狼和三只羚羊过河，只有一条船，一个人带三只狼和三只羚羊过河，只有一条船，船可以容纳一个人和两只动物没有人在的时候，船可以容纳一个人和两只动物没有人在的时候，如果狼的数量不少于羚羊的数量，狼就会吃掉羚羊如果狼的数量不少于羚羊的数量，狼就会吃掉羚羊请设计过河的算法请设计过河的算法解：解：算法如下：算法如下：4.4.人带两只狼返回；人带两只狼返回；2.2.人自己返回；人自己返回；3.3.人带人带一一只羚羊过河；只羚羊过河；1.1.人带两只狼过河；人带两只狼过河；5.5.人带两只羚羊过河；人带两只羚羊过河； 6.6.人自己返回；人自己返回；7.7.人带两只狼过河；人带两只狼过河； 8.8.人自己返回；人自己返回；9.9.人带一只狼过河人带一只狼过河1.1.算法：算法是解决某类问题的一系列步骤或算法：算法是解决某类问题的一系列步骤或程序；程序；2.2.算法的基本思想：程序化思想；算法的基本思想：程序化思想；3.3.算法的特征算法的特征: :有穷性、有穷性、 确定性、确定性、 输入、输入、输出、输出、有效性有效性. . 世间没有一种具有真正价值的东西可以不经过艰苦辛勤的劳动而得到.
