搜索
§2.1算法的基本思想课前新知预习[航向标·学习目标]1．理解算法的概念与特点．2．学会用自然语言描述算法．3．通过解决具体问题的实例感受理解算法的特点，体会算法的基本思想，学会借助已有数学问题的解决方法和步骤设计算法．[读教材·自主学习]1．算法的概念：算法是指按照一定规则解决某一类问题的明确的过程和有限的__________，算法具有如下特点：(1)__________：即每一个算法都有明确的目的．(2)__________：即我们所设计的算法必须是有效的，并在有限步的操作后解决问题．(3)_________：即我们设计的算法要符合逻辑规律，能从头到尾运行下去．□01步骤□02明确性□03有效性□04逻辑性(4)_____________：我们所设计的算法必须能够解决一类问题，而不是某一个问题．(5)___________：算法不是唯一的，可有另外不同的设计方法．2．排序：为了便于查询和检索，我们常常根据某种要求把被查询的对象用数字(或者符号)表示出来，并把数字按大小_________，是信息处理中一项基本的工作，通常称为排序．3．有序列：按__________排列的数据列为有序列．□05普遍性□06不唯一性□07排列□08顺序[看名师·疑难剖析]1．对算法含义的理解(1)算法是机械的算法的设计要“面面俱到”不能省略任何一个小小的步骤，有时可能要进行大量重复计算，但只要按步骤一步一步地执行，总能得到结果．算法的这种机械化的特点，在设计出算法后，便于把具体过程交给计算机去完成．(2)算法是普遍存在的实际上处理任何问题都需要算法，如国际象棋的棋谱、走法、胜负的评判标准，邮寄物品的相关手续，求一个二元一次方程组的解等等．(3)求解某个具体问题的算法一般是不唯一的算法实际上是解决问题的步骤和方法，求解问题的出发点不同，就会得到不同的算法．如求二元一次方程组的解有代入消元法和加减消元法，但不同的算法可能会有“优劣”之分．2．算法与数学问题解法的区别与联系(1)联系算法与解法是一般与特殊的关系，也是抽象与具体的关系．如，由具体的二元一次方程组的求解过程(解法)出发，归纳出了二元一次方程组求解的步骤；同时指出，这样的求解步骤也适合有限制条件的二元一次方程组，这些步骤就构成了二元一次方程组的算法．算法的获得要借助一般意义上具体问题的求解方法，而任何一个具体问题都可利用这类问题的一般算法解决．(2)区别算法是解决某一类问题所需要的程序和步骤的统称，也可理解为数学中的“通法通解”；而解法是解决某一个具体问题的过程和步骤，是具体的解题过程．课堂师生共研考点一算法的概念例1下列关于算法的描述正确的是()A．算法与求解一个问题的方法相同B．算法只能解决一个问题，不能重复使用C．算法过程要一步一步执行，每步执行的操作必须确切D．有的算法执行完后，可能无结果[分析]由题目可获取以下主要信息：①给出的四个选项均与算法含义和特点有关；②对各选项要做正误判断．解答本题要先弄清楚算法的含义和特点，然后逐一判定选项命题的真假即可．[解析]算法与求解一个问题的方法既有区别又有联系，故A不对；算法能重复使用，故B不对；每个算法执行后必须有结果，故D不对；由算法的有序性和确定性可知C正确．解析[答案]C答案类题通法算法实际上是解决问题的一种程序性方法，它通常指向某一个或一类问题，而解决的过程是程序性和构造性的.算法也可以看成解决问题的特殊的、有效的方法.[变式训练1]下列关于算法的说法，正确的有()①求解某一类问题的算法是唯一的；②算法必须在有限步操作之后停止；③算法的每一步操作必须是明确的，不能有歧义和模糊；④算法执行后一定产生确定的结果．A．1个B．2个C．3个D．4个答案C答案解析本题是在熟练掌握算法概念的基础上的一个跃升，即对算法概念进行进一步的挖掘，理解其内涵．从而借助概念分析、解决问题．由于算法具有有穷性、确定性和可执行性，因而②③④正确．解决问题的算法不一定是唯一的，从而①错，故选C.解析考点二数值计算问题的算法设计例2写出一个算法，求二元一次方程组a1x＋b1y＝c1，①a2x＋b2y＝c2'②的解．[分析]联系该方程组的实际解法过程，但要注意对待定系数的分类讨论．因为是二元一次方程组，所以a1、a2不能同时为0，b1，b2也不能同时为0.[解]算法如下：1.若a1≠0，由①×－a2a1＋②，得到b2－a2b1a1y＝c2－a2c1a1.即方程组化为a1x＋b1y＝c1，①a1b2－a2b1y＝a1c2－a2c1.③2．若a1b2－a2b2≠0，解③得y＝a1c2－a2c1a1b2－a2b1.④3.将④代入①，整理得x＝b2c1－b1c2a1b2－a2b1.答案4.输出结果x，y.5.如果a1b2－a2b1＝0，从③可以看出，方程组无解或有无穷多组解．6.如果a1＝0，则b1≠0，所以y＝c1b1.⑤7.将⑤代入②，得x＝b1c2－b2c1a2b1.8.输出结果x，y.答案类题通法对于设计数值计算问题的算法，可以借助数学的常规解法或数学公式，将过程分解成清晰的步骤，使之条理化，但应注意多个数进行四则运算时应分步计算，依次进行，直到算出结果.本题中，把解方程组的过程转化为算法的步骤，应用了数学的转化思想.[变式训练2]写出解方程x2－2x－3＝0的一个算法．解解法一：第一步，移项，得x2－2x＝3.①第二步，①两边同加1并配方，得(x－1)2＝4.②第三步，②式两边开方，得x－1＝±2.③第四步，解③，得x＝3或x＝－1.解法二：第一步，计算方程的判别式并判断其符号：Δ＝22＋4×3＝160.第二步，将a＝1，b＝－2，c＝－3代入求根公式x＝－b±b2－4ac2a，得x1＝3，x2＝－1.答案考点三判断性问题的算法设计例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，我们判断它是否为质数的算法为：第一步：令i＝2.第二步，用i除n，得余数r.第三步，判断“r＝0”是否成立，若是，则n不是质数，结束算法；否则，将i的值增加1，仍用i表示.第四步，判断“in－1”是否成立，若是，则n是质数，结束算法；否则，返回第二步.分步处理是本类问题的特色，也是算法思想的重要体现.[变式训练3]设计算法，将1260分解成素因数的乘积．解算法步骤如下：(1)判断1260是否为素数：否．(2)确定1260的最小素因数：2.1260＝2×630.(3)判断630是否为素数：否．(4)确定630的最小素因数：2.630＝2×315.(5)判断315足否为素数：否．(6)确定315的最小素因数：3.315＝3×105.答案(7)判断105是否为素数：否．(8)确定105的最小素因数：3.105＝3×35.(9)判断35是否为素数：否．(10)确定35的最小素因数：5.35＝5×7.(11)判断7是否为素数：7是素数，所以分解结束．分解结果是：1260＝2×2×3×3×5×7.答案考点四关于整除性问题的算法设计例4设计一个算法，求1764与840的最大公约数．[分析]首先，将两个数分别进行素因数分解，1764＝22×32×72,840＝23×3×5×7.其次，确定两个数的公共素因数2,3,7.接着，确定公共素因数的指数：对于公共素因数2,22是1764的因数，23是840的因数，因此22是这两个数的公因数，同样可以确定公因数3和7的指数均为1.这样就确定了1764与840的最大公因数为22×3×7＝84.[解]算法步骤如下：(1)将1764进行素因数分解，1764＝22×32×72.(2)将840进行素因数分解，840＝23×3×5×7.(3)确定它们的公共素因数为2,3,7.(4)确定公共素因数的指数．公共素因数2,3,7的指数分别为2,1,1.(5)最大公因数为22×31×71＝84.答案类题通法1正确理解算法的概念，一个程序的算法要本着方便简捷的原则，还要讲求科学性，算法的步骤是按照一定顺序进行的，不具有可逆性.,2在设计算法的过程当中要牢固把握住它的五个特性：有限性、确定性、可行性、输入、输出.[变式训练4]求8251与6105的最大公因数．解算法步骤如下：(1)先将8251进行素因数分解：8251＝37×223；(2)然后将6105进行素因数分解：6105＝3×5×11×37；(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,5156.3.比较51与50,5150.4.将51插入到56和50之间，得到一个新的有序列{32,36,50,51,56,81}．答案类题通法本例的排序算法是有序列直接插入排序，解决本类问题也可以用折半插入排序法进行.[变式训练5]将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个环移到乙柱，必须先把上面的n－1个环移到丙柱，然后把第n个环移到乙柱，最后再把丙柱的第n－1个环移过来．解决n个环的问题，先要解决n－1个环的问题，而这个问题与前一个是类似的，可以用相同的办法解决．最终，得到只有一个环的情况，很简单，直接把环从甲柱移到乙柱即可．[解]如果移动一次算一步，则可按以下步骤进行：第一步，将C环移至乙柱．第二步，将B环移至丙柱．第三步，将C环移至丙柱．第四步，将A环移至乙柱．第五步，将C环移至甲柱．第六步，将B环移至乙柱．第七步，将C环移至乙柱．答案[变式训练6]一个人带着三只狼和三只羊过河，只有一条船，该船可容纳一个人和两只动物；没有人在的时候，如果狼的数量不少于羊的数量，狼就会吃羊，该人如何能将动物转移过河？请设计算法．解第一步，人带两只狼过河，并自己返回；第二步，人带一只狼过河，自己返回；第三步，人带两只羊过河，并带两只狼返回；第四步，人带一只羊过河，自己返回；第五步，人带两只狼过河．答案规范答题思维规范解答分段函数的算法设计[例](12分)已知分段函数f(x)＝x2－1，－1≤x≤1，lnx，x1，请设计一个算法，输入任意一个不小于－