2019_2020学年高中数学第二章算法初步2.1算法的基本思想学案北师大版必修3.docx

2.1 算法的基本思想航向标学习目标1理解算法的概念与特点2学会用自然语言描述算法3通过解决具体问题的实例感受理解算法的特点，体会算法的基本思想，学会借助已有数学问题的解决方法和步骤设计算法读教材自主学习1算法的概念：算法是指按照一定规则解决某一类问题的明确的过程和有限的步骤，算法具有如下特点：(1)明确性：即每一个算法都有明确的目的(2)有效性：即我们所设计的算法必须是有效的，并在有限步的操作后解决问题(3)逻辑性：即我们设计的算法要符合逻辑规律，能从头到尾运行下去(4)普遍性：我们所设计的算法必须能够解决一类问题，而不是某一个问题(5)不唯一性：算法不是唯一的，可有另外不同的设计方法2排序：为了便于查询和检索，我们常常根据某种要求把被查询的对象用数字(或者符号)表示出来，并把数字按大小排列，是信息处理中一项基本的工作，通常称为排序3有序列：按顺序排列的数据列为有序列看名师疑难剖析1对算法含义的理解(1)算法是机械的算法的设计要“面面俱到”不能省略任何一个小小的步骤，有时可能要进行大量重复计算，但只要按步骤一步一步地执行，总能得到结果算法的这种机械化的特点，在设计出算法后，便于把具体过程交给计算机去完成(2)算法是普遍存在的实际上处理任何问题都需要算法，如国际象棋的棋谱、走法、胜负的评判标准，邮寄物品的相关手续，求一个二元一次方程组的解等等(3)求解某个具体问题的算法一般是不唯一的算法实际上是解决问题的步骤和方法，求解问题的出发点不同，就会得到不同的算法如求二元一次方程组的解有代入消元法和加减消元法，但不同的算法可能会有“优劣”之分2算法与数学问题解法的区别与联系(1)联系算法与解法是一般与特殊的关系，也是抽象与具体的关系如，由具体的二元一次方程组的求解过程(解法)出发，归纳出了二元一次方程组求解的步骤；同时指出，这样的求解步骤也适合有限制条件的二元一次方程组，这些步骤就构成了二元一次方程组的算法算法的获得要借助一般意义上具体问题的求解方法，而任何一个具体问题都可利用这类问题的一般算法解决(2)区别算法是解决某一类问题所需要的程序和步骤的统称，也可理解为数学中的“通法通解”；而解法是解决某一个具体问题的过程和步骤，是具体的解题过程考点一 算法的概念例1下列关于算法的描述正确的是()A算法与求解一个问题的方法相同B算法只能解决一个问题，不能重复使用C算法过程要一步一步执行，每步执行的操作必须确切D有的算法执行完后，可能无结果分析由题目可获取以下主要信息：给出的四个选项均与算法含义和特点有关；对各选项要做正误判断解答本题要先弄清楚算法的含义和特点，然后逐一判定选项命题的真假即可解析算法与求解一个问题的方法既有区别又有联系，故A不对；算法能重复使用，故B不对；每个算法执行后必须有结果，故D不对；由算法的有序性和确定性可知C正确答案C类题通法算法实际上是解决问题的一种程序性方法，它通常指向某一个或一类问题，而解决的过程是程序性和构造性的.算法也可以看成解决问题的特殊的、有效的方法.下列关于算法的说法，正确的有()求解某一类问题的算法是唯一的；算法必须在有限步操作之后停止；算法的每一步操作必须是明确的，不能有歧义和模糊；算法执行后一定产生确定的结果A1个 B2个 C3个 D4个答案C解析本题是在熟练掌握算法概念的基础上的一个跃升，即对算法概念进行进一步的挖掘，理解其内涵从而借助概念分析、解决问题由于算法具有有穷性、确定性和可执行性，因而正确解决问题的算法不一定是唯一的，从而错，故选C.考点二 数值计算问题的算法设计例2写出一个算法，求二元一次方程组的解分析联系该方程组的实际解法过程，但要注意对待定系数的分类讨论因为是二元一次方程组，所以a1、a2不能同时为0，b1，b2也不能同时为0.解算法如下：1.若a10，由，得到yc2.即方程组化为2若a1b2a2b20，解得y.3.将代入，整理得x.4.输出结果x，y.5.如果a1b2a2b10，从可以看出，方程组无解或有无穷多组解6.如果a10，则b10，所以y.7.将代入，得x.8.输出结果x，y.类题通法对于设计数值计算问题的算法，可以借助数学的常规解法或数学公式，将过程分解成清晰的步骤，使之条理化，但应注意多个数进行四则运算时应分步计算，依次进行，直到算出结果.本题中，把解方程组的过程转化为算法的步骤，应用了数学的转化思想.写出解方程x22x30的一个算法解解法一：第一步，移项，得x22x3.第二步，两边同加1并配方，得(x1)24.第三步，式两边开方，得x12.第四步，解，得x3或x1.解法二：第一步，计算方程的判别式并判断其符号：2243160.第二步，将a1，b2，c3代入求根公式x，得x13，x21.考点三 判断性问题的算法设计例3设计一个算法，判断7是否为质数分析只能被1和自身整除的大于1的整数叫质数因而要判断一个数是否为质数，只需用比这个数小的任一个大于1的整数来除该数，然后利用余数是否为0来判断解算法步骤如下：(1)用2除7，得到余数1.因为余数不为0，所以2不能整除7.(2)用3除7，得到余数1.因为余数不为0，所以3不能整除7.(3)用4除7，得到余数3.因为余数不为0，所以4不能整除7.(4)用5除7，得到余数2.因为余数不为0，所以5不能整除7.(5)用6除7，得到余数1.因为余数不为0，所以6不能整除7.(6)判断7是否为质数：7是质数类题通法从本例可以看出，本类问题的算法具有很强的机械重复性，因而对于任意给定一个大于2的整数n，我们判断它是否为质数的算法为：第一步：令i2.第二步，用i除n，得余数r.第三步，判断“r0”是否成立，若是，则n不是质数，结束算法；否则，将i的值增加1，仍用i表示.第四步，判断“in1”是否成立，若是，则n是质数，结束算法；否则，返回第二步.分步处理是本类问题的特色，也是算法思想的重要体现.设计算法，将1260分解成素因数的乘积解算法步骤如下：(1)判断1260是否为素数：否(2)确定1260的最小素因数：2.12602630.(3)判断630是否为素数：否(4)确定630的最小素因数：2.6302315.(5)判断315足否为素数：否(6)确定315的最小素因数：3.3153105.(7)判断105是否为素数：否(8)确定105的最小素因数：3.105335.(9)判断35是否为素数：否(10)确定35的最小素因数：5.3557.(11)判断7是否为素数：7是素数，所以分解结束分解结果是：1260223357.考点四 关于整除性问题的算法设计例4设计一个算法，求1764与840的最大公约数分析首先，将两个数分别进行素因数分解，1764223272,84023357.其次，确定两个数的公共素因数2,3,7.接着，确定公共素因数的指数：对于公共素因数2,22是1764的因数，23是840的因数，因此22是这两个数的公因数，同样可以确定公因数3和7的指数均为1.这样就确定了1764与840的最大公因数为223784.解算法步骤如下：(1)将1764进行素因数分解，1764223272.(2)将840进行素因数分解，84023357.(3)确定它们的公共素因数为2,3,7.(4)确定公共素因数的指数公共素因数2,3,7的指数分别为2,1,1.(5)最大公因数为22317184.类题通法(1)正确理解算法的概念，一个程序的算法要本着方便简捷的原则，还要讲求科学性，算法的步骤是按照一定顺序进行的，不具有可逆性., (2)在设计算法的过程当中要牢固把握住它的五个特性：有限性、确定性、可行性、输入、输出.求8251与6105的最大公因数解算法步骤如下：(1)先将8251进行素因数分解：825137223；(2)然后将6105进行素因数分解：6105351137；(3)确定它们的公共素因数：37；(4)确定公共素因数的指数：1；(5)最大公因数为37.考点五 排序问题的算法设计例5对于有序列32,36,50,56,81，现在要将数据51插入到有序列中请设计算法确定数据51在有序列中的位置，并用自然语言描述算法分析我们可以将51与有序列中的数据从右到左依次进行比较，来确定51在有序列中的位置，也可以将51与有序列中的数据从左向右依次进行比较，来确定51在有序列中的位置解将51与有序列中的数据从右向左逐个进行比较，从而确定51在有序列中的位置其算法如下：1.比较51与81,5181.2.比较51与56,5150.4.将51插入到56和50之间，得到一个新的有序列32,36,50,51,56,81类题通法本例的排序算法是有序列直接插入排序，解决本类问题也可以用折半插入排序法进行.将52插入有序列13,27,38,39,43,47,48,51,57,66,74,82中，构成一个新的有序列解首先选择有序列中具有中间位置序号的数据47，将52与47进行比较，显然5247，故52不能插入到47的左边的任何位置所以，应该排在47的右边，再将余下数据的中间位置的数据57与52比较，显然5257，因此应插到57的左边，又5152，则52插入到51的右边，57的左边，即可得到52的位置.考点六 实际问题的算法设计例6汉诺塔问题：如图三根柱子，甲柱上从大到小放置了三个圆环A、B、C，现在要将这三个圆环移至乙柱，也要从大到小放置要求一次移动一个，移动过程中，大圆环不能放于小圆环上，应如何移动？分析这是一个古典的数学问题要把甲柱的n个环移到乙柱，必须先把上面的n1个环移到丙柱，然后把第n个环移到乙柱，最后再把丙柱的第n1个环移过来解决n个环的问题，先要解决n1个环的问题，而这个问题与前一个是类似的，可以用相同的办法解决最终，得到只有一个环的情况，很简单，直接把环从甲柱移到乙柱即可解如果移动一次算一步，则可按以下步骤进行：第一步，将C环移至乙柱第二步，将B环移至丙柱第三步，将C环移至丙柱第四步，将A环移至乙柱第五步，将C环移至甲柱第六步，将B环移至乙柱第七步，将C环移至乙柱一个人带着三只狼和三只羊过河，只有一条船，该船可容纳一个人和两只动物；没有人在的时候，如果狼的数量不少于羊的数量，狼就会吃羊，该人如何能将动物转移过河？请设计算法解第一步，人带两只狼过河，并自己返回；第二步，人带一只狼过河，自己返回；第三步，人带两只羊过河，并带两只狼返回；第四步，人带一只羊过河，自己返回；第五步，人带两只狼过河规范解答 分段函数的算法设计例(12分)已知分段函数f(x)请设计一个算法，输入任意一个不小于1的实数x0，输出相应的f(x0)的值(一)精妙思路点拨(二)分层规范细解1输入x0；3分2.，则输出“输入的数据有误”，结束算法，否则执行第3步；6分3若1x01，则f(x0)x1，否则f(x0)lnx0；9分4.，结束算法.12分(三)来自一线的报告通过阅卷后分析，对解答本题的失分警示和解题启示总结如下：(注：此处的见分层规范细解过程)(四)类题练笔掌握已知函数f(x)解1.输入x0；2若x01，则计算f(x0)2x01，否则执行第3步；3若x04，则计算f(x0)，否则执行第4步；4计算f(x0)x02；5输出f(x0)的值，结束算法(五)解题设问解答本题时，需对谁进行分类讨论？_.答案自变量x1.以下给出关于算法的几种说法，其中正确的是()A算法就是某一个问题的解题方法B对于给定的一个问题，其算法不一定是唯一的C一个算法可以不产生确定的结果D算法的步骤可以无限地执行下去不停止答案B解析算法是做某一件事的步骤或程序，不是解决问题的方法，所以A不正确；一个算法产生的结果是确定的，所以C不正确；一个算法的步骤是有限的，它应在有限步骤之后停止，而不能是无限的，所以D不正确；求解某一个问题可以有不同的算法，所以B正确2下面四种叙述能称为算法的是()A在家里一般是妈妈做饭B做米饭需要刷锅、淘米、添水、加热这些步骤C在野外做饭叫野炊D做饭必须有米答案B解析四个选项中仅有B是表达解决问题的步骤3下列对算法的理解不正确的是()A算法有一个共同特点就是对一类问题都有效(而不是个别问题)B算法要求是一步一步地执行，每一步都能得到唯一的结果