数学北师大版必修3学案2-1算法的基本思想

第二章算法初步§1算法的基本思想知识点一算法的概念及思想[填一填]1．算法的概念及描述方式算法是解决某类问题的一系列步骤或程序，只要按照这些步骤执行，都能使问题得到解决．一般来说，“用算法解决问题”都是可以利用计算机帮助完成的．算法的描述方式有：自然语言、数学语言、形式语言(算法语言)、框图．2．算法的基本思想在解决某些问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，通常把这些步骤称为解决这些问题的算法．这种解决问题的思想方法称为算法的基本思想．[答一答]1．一个好的算法应有哪些要求？提示：算法的基本思想是程序化思想，应满足以下两个基本要求．(1)写出的算法，必须能解决一类问题，并且能够重复使用．如在解二元一次方程组时，高斯消去法就是一个典型的算法实例，这种算法可用来求解任意一个二元一次方程组，只要我们将高斯消去法中的参数值换为二元一次方程组的相应系数值即可．(2)算法过程要能一步一步执行，每一步执行的操作必须确切，不能含糊不清，而且经过有限步后能得出结果．知识点二算法的性质[填一填]3．算法的性质(1)确定性：算法中的每一步都应该是确定的，并且能有效地执行并得到确定的结果，而不能含糊其辞，含有歧义．(2)有限性：对于一个算法来说，它的操作步骤必须是有限的，必须在有限的步骤之内完成．(3)普遍性：一个算法通常能解决一类问题，不是仅仅解决一个单独的问题．4．(1)作用：使计算机代替人完成某些工作．(2)注意：解决一个问题可能有多个算法，但有优劣之分，其中操作简单、步骤少且能解决一类问题的算法称为最优算法．[答一答]2．算法与解法的区别与联系是什么？提示：学习算法的概念应注意以下两点：1．在数学中，现代意义上的“算法”通常是指解决某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成．2．通俗点说，算法就是计算机解题的过程，在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法，前者是推理实现的算法，后者是操作实现的算法．类型一算法的概念【例1】小明早上从起床到出门需要洗脸刷牙(5min)、刷水壶(2min)、烧水(8min)、泡面(3min)、吃饭(10min)、听广播(8min)几个步骤，下列选项中最好的一种算法是()A．①洗脸刷牙；②刷水壶；③烧水；④泡面；⑤吃饭；⑥听广播B．①刷水壶；②烧水同时洗脸刷牙；③泡面；④吃饭；⑤听广播C．①刷水壶；②烧水同时洗脸刷牙；③泡面；④吃饭同时听广播D．①吃饭同时听广播；②泡面；③烧水同时洗脸刷牙；④刷水壶【思路探究】题中给出了各步骤及所需的时间，保证了算法步骤的确定性和可执行性，现在只需根据时间最短来确定出最好的算法步骤即可．【解析】因为A选项共用时间36min，B选项共用时间31min，C选项共用时间23min，D选项的算法步骤不符合常理，所以最好的算法是C.【答案】C规律方法解决有关算法概念的判断题时，应根据算法的特征进行判断，特别注意必须能在有限步内求解某类问题，其中每个步骤都必须明确可行，不能模棱两可．(1)下列关于算法的几种说法：①算法对一类问题都有效；②算法对个别问题有效；③算法就是某个问题的解题过程；④算法是一种通法，只要按部就班地做，总能得到结果．其中正确的个数为(B)A．1B．2C．3D．4(2)下列描述中不能看作算法的是(D)A．做米饭需要刷锅，淘米，添水，加热这些步骤B．洗衣机的使用说明书C．从济南到台湾旅游，先坐火车，再坐飞机D．解方程2x2＋x－1＝0时需先判断判别式的符号解析：(1)算法通常是指可以用计算机来解决的某一类问题的程序或步骤，所以①正确，②不正确；算法不等同于解法，所以③不正确；算法的程序或步骤必须是明确的、有效的，而且必须在有限步内完成，所以④正确．(2)因为A，B，C都描述了解决问题的过程，可以看作算法，而D只描述了一个事实，没说明如何解决问题，不是算法．类型二借助算法解方程或方程组【例2】写出解方程组eq\b\lc\{\rc\(\a\vs4\al\co1(2x＋y＝7①，,4x＋5y＝11②))的算法．【思路探究】解线性方程组的常用方法是加减消元法和代入消元法，这两种方法没有本质的差别，但是代入消元法更适用于解一般的线性方程组，且便于在计算机上实现．【解】算法1(代入消元法)算法步骤如下：1．由①得y＝7－2x③；2．将③代入②得4x＋5(7－2x)＝11④；3．解④得x＝4；4．将x＝4代入③得y＝－1；5．得到方程组的解为eq\b\lc\{\rc\(\a\vs4\al\co1(x＝4，,y＝－1.))算法2(加减消元法)算法步骤如下：1．①×5－②得(2×5－4)x＝7×5－11③；2．解③得x＝4；3．①×2－②得(1×2－5)y＝7×2－11④；4．解④得y＝－1；5．得到方程组的解为eq\b\lc\{\rc\(\a\vs4\al\co1(x＝4，,y＝－1.))规律方法设计算法时，经常遇到解方程或方程组的算法问题，一般是按照数学上解方程或方程组的方法进行设计，但应注意全面考虑解的情况，即先确定方程或方程组是否有解，有解时有几个或几组解，然后按照求解步骤设计算法步骤．写出解方程x2－2x－3＝0的一个算法．解：解法1：1.移项，得x2－2x＝3；①2．①两边同时加1并配方，得(x－1)2＝4；②3．②式两边开方，得x－1＝±2；③4．解③得x＝3，或x＝－1.解法2：1.计算方程的判别式并判断其符号，Δ＝(－2)2－4×1×(－3)＝16>0；2．将a＝1，b＝－2，c＝－3代入求根公式x＝eq\f(－b±\r(b2－4ac),2a)，得x1＝3，x2＝－1.类型三求两个数的最大公因数或最小公倍数【例3】设计一个算法，求1896与2008的最大公因数．【思路探究】分别对1896与2008进行素因数分解，最后找出最大公因数．【解】首先，对两个数分别进行素因数分解：1896＝23×3×79,2008＝23×251.其次，确定两个数的公共素因数为2.接着，确定公共素因数的指数：对于公共素因数2,23是1896的因数，也是2008的因数，因此23是这两个数的公因数．这样，就确定了1896与2008的最大公因数为：23＝8.算法步骤如下：第一步，将1896行素因数分解：1896＝23×3×79；第二步，将2008进行素因数分解：2008＝23×251；第三步，确定它们的公共素因数：2；第四步，确定公共素因数2的指数为3；第五步，最大公因数为23＝8.规律方法把1896与2008分别进行素因数分解，一般是从2开始，用“是则留下，不是则去掉”的方法，然后是3,5,7，…直到分别将两个数分解为素因数的积为止．设计一个算法，求1356和2400的最小公倍数．解：算法步骤如下：(1)先将1356进行素因数分解：1356＝22×3×113；(2)然后将2400进行素因数分解：2400＝25×3×52；(3)确定两个数的所有素因数：2,3,5,113；(4)确定素因数的指数：2的指数为5,3的指数为1,5的指数为2,113的指数为1；(5)最小公倍数为：25×3×52×113＝271200.类型四筛选问题的算法设计【例4】设计一个算法，对任意3个整数a，b，c，求出其中的最小值．【思路探究】eq\x(比较a，b)eq\o(→,\s\up15(较小的数记为m))eq\x(比较m与c)→eq\x(最小数)【解】算法步骤如下：1．比较a与b的大小，若a<b，则m＝a；若b<a，则m＝b.2．比较m与c的大小，若m<c，则m为最小数；若c<m，则c为最小数．规律方法求最小(大)数就是从中筛选出最小(大)的一个，筛选过程中的每一步都是比较两个数的大小，保证了筛选的可行性，这种方法可以推广到从多个不同数中筛选出满足要求的一个．在下列数字序列中，写出搜索89的算法：21,3,0,9,15,72,89,91,93.解：1.先找到序列中的第一个数m，m＝21；2．将m与89比较，是否相等，如果相等，则搜索到89；3．如果m与89不相等，则往下执行；4．继续将序列中的其他数赋给m，重复第2步，直到搜索到89.类型五算法的应用【例5】一次青青草原园长包包大人带着灰太狼、懒羊羊和一捆青草过河．河边只有一条船，由于船太小，只能装下两样东西．若包包大人不在跟前，灰太狼要吃懒羊羊，懒羊羊要吃青草，请问包包大人如何才能带着他们平安过河？试设计一种算法．【思路探究】包包大人先带谁过去是解决本题的关键所在．【解】包包大人采取的过河的算法可以是：第一步，包包大人带懒羊羊过河；第二步，包包大人自己返回；第三步，包包大人带青草过河；第四步，包包大人带懒羊羊返回；第五步，包包大人带灰太狼过河；第六步，包包大人自己返回；第七步，包包大人带懒羊羊过河．规律方法对于实际生活中的问题，首先应建立过程模型，根据过程设计步骤，完成算法．在设计算法时应简练、清晰，要善于分析任何可能出现的情况，以体现思维的严谨性．一位商人有9枚银元，其中有1枚略轻的是假银元，你能用天平(无砝码)将假银元找出来吗？解：法1算法如下：第一步，任取2枚银元分别放在天平的两边，若天平左、右不平衡，则轻的一枚就是假银元，若天平平衡，则进行第二步．第二步，取下右边的银元放在一边，然后把剩下的7枚银元依次放在右边进行称量，直到天平不平衡，偏轻的那一枚就是假银元．法2算法如下：第一步，把9枚银元平均分成3组，每组3枚．第二步，先将其中两组放在天平的两边，若天平不平衡，则假银元就在轻的那一组；否则假银元在未称量的那一组．第三步，取出含假银元的那一组，从中任取2枚银元放在天平左、右两边称量，若天平不平衡，则假银元在轻的那一边；若天平平衡，则未称量的那一枚是假银元．——易错警示——对算法的概念理解错误【例6】用自然语言描述求y＝－x2－2x＋3的最大值的算法．【错解】第一步，配方得y＝－(x＋1)2＋4.第二步，函数的最大值为4.【错解分析】作为一个具体问题来说，上述解法没有什么错误，但是我们要描述的是求这一类问题的算法，它可以用来解决这个问题，也可以用来求这一类问题，则上述解法就欠妥了．应就y＝ax2＋bx＋c作一般讨论．【正解】第一步，给a，b，c赋值．第二步，判断a≥0是否成立，若成立，则输出“函数无最大值”，结束算法；否则执行第三步．第三步，计算eq\f(4ac－b2,4a)，并将结果赋给max.第四步，输出max，结束算法．(算法执行过程中，依次给a、b、c取值－1、－2、3)设计算法，给定任一x的值，求y的值，其中y＝eq\b\lc\{\rc\(\a\vs4\al\co1(2x－1，x≤0，,x2＋1，x>0.))解：第一步，输入x的值．第二步，判断x是否大于零，若x>0，执行第三步；否则，执行第四步．第三步，计算y＝x2＋1的值，转去执行第五步．第四步，计算y＝2x－1的值．第五步，输出y的值．一、选择题1．下列语句表达中是算法的有(C)①从济南到巴黎可以先乘火车到北京，再坐飞机抵达；②利用公式S＝eq\f(1,2)ah计算底为1，高为2的三角形的面积；③eq\f(1,2)x>2x＋4；④求M(1,2)与N(－3，－5)两点所在直线的方程，可先求MN的斜率，再利用点斜式求方程．A．1个B．2个C．3个D．4个解析：算法是解决某类问题的步骤与过程，这个问题并不仅仅限于数学问题，①②④都表达了一种算法，故应选C.2．588与378的最大公因数是(D)A．6 B．14C．21 D．42解析：588＝22×3×72,378＝2×33×7，所以588