2019-2020年高中数学第二章算法初步2.1算法的基本思想知识导航北师大版必修.DOC

2019-2020年高中数学第二章算法初步2.1算法的基本思想知识导航北师大版必修知识梳理1.现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确的、有效的,而且能够在有限步之内完成.2.算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤,或看成按要求设计好的有限的确切的计算序列,并且这样的步骤或序列能够解决一类问题.3.在解决某些问题时,需要设计出一系列可操作或可计算的步骤来解决问题,这些步骤称为解决这些问题的算法.也就是说,算法实际上就是解决问题的一种程序性方法.算法一般是机械的,有时需进行大量重复的计算,它的优点是一种通法,只要按部就班地去做,总能得到结果.4.算法与一般意义上具体问题的解法既有联系又有区别,它们之间是一般与特殊、抽象与具体的关系.算法的获得要借助于一般意义上具体问题的求解方法,而任何一个具体问题都可以利用这类问题的一般算法来解决.5.描述算法可以有不同的形式.例如,可以用日常语言和数学语言加以叙述;也可以借助程序语言(算法语言)给出精确的说明;还可以用框图直观地显示算法的全貌.6.为了便于查询和检索,常常需要根据某种要求将被查询的对象按顺序排列,通常称为排序.所以排序就是按照一定的规则,对数据加以排列整理,以提高查找效率.7.排序的方法有很多,我们主要掌握两种:有序列直接插入排序法和折半插入排序法.8.所谓有序列插入排序法就是从部分到全体、从局部到整体的排序方法,它是先将前两个数按要求的顺序排好,然后把第三个数与这两个排好的数进行大小比较,按其大小关系将第3个数插到已排好的两个数中的适当位置使之符合要求,然后再把第4个数按同样的方法插到已排好的三个数的适当位置上,依次下去,直到把最后一个数插到前边已排好的数中的适当位置为止,这时的各数的顺序就是符合要求的最终顺序.知识导学由于算法可简单理解为解决某一问题的方法步骤,故可借助于我们熟悉的实例(如二元一次方程组解的求解步骤和方法),体会问题的求解过程就是一个算法.结合具体实例,明确算法的基本要求:(1)写出的算法必须能解决一类问题并且能重复使用;(2)算法的过程须能一步步执行,每步执行的操作必须确切,不能含糊不清,而且经过有限步运算后能得出结果.学习时可从熟知的问题出发,体会算法是问题解决的“机械“程序,即能在计算机上完成这一重要特征.它不同于一般意义上具体问题的解法,二者既有区别,又有联系.初学算法,可采用“照猫画虎法”,即通过几个典型的实例,用自然语言和数学语言写出解决问题的算法,贴于案头,时刻模仿研究;也可采用类比学法,如类比一个求解一元二次方程根的算法,可以写出所有方程(或组)求解的算法(形成感性经验).本节的重点、难点是算法的含义,突破它的关键是通过具体问题,按部就班地设计解决它的步骤方法,这也是算法的实质.本小节课本安排了常见的两种排序方法,旨在使同学们在学习了一些简单的算法后,再结合几个典型算法案例,通过模仿、操作、探究,进一步体会算法的基本思想,以及算法在解决实际问题的过程中所体现的特点.疑难突破1.算法概念的理解剖析:算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤,或看成按要求设计好的有限的确切的计算序列,并且这样的步骤或序列能够解决一类问题.现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确的、有效的,而且能够在有限步之内完成.算法与一般意义上具体问题的解法既有联系又有区别,它们之间是一般与特殊、抽象与具体的关系.算法的获得要借助于一般意义上具体问题的求解方法,而任何一个具体问题都可以利用这类问题的一般算法来解决.在解决某些问题时,需要设计出一系列可操作或可计算的步骤来解决问题,这些步骤称为解决这些问题的算法.也就是说,算法实际上就是解决一类问题的一种程序性方法.算法一般是机械的,有时需进行大量重复的计算,它的优点是一种通法,只要按部就班地去做,总能得到结果.2.算法具有的基本特征剖析:一般来讲,一个算法应具有下列五个基本特性:(1)概括性:写出的算法必须能解决一类问题,且能重复使用.(2)逻辑性:算法从起始步骤开始,分为若干个明确的步骤,前一步是后一步的前提,只有执行完前一步才能进行下一步,而且每一步都是正确无误的,从而组成了一个具有很强逻辑性的序列.(3)有穷性:对于一个算法来说,它的操作步骤必须是有限的,必须在执行有限个步骤之后结束.(4)不唯一性:求解某一问题的算法可以有多个.(5)普遍性:很多具体的问题,都可以设计出合理的算法去解决.典题精讲例1写出求1+2+3+4+5+6的算法.思路分析:本题按题意可以采取逐个相加的方法计算结果,但这样做的计算量较大.若使用公式1+2+3+n=则可使计算量大大减少.解法一:第一步:计算1+2得到3;第二步:将第一步的运算结果3与3相加,得到6;第三步:将第二步的运算结果6与4相加,得到10;第四步:将第三步的运算结果10与5相加,得到15;第五步:将第四步的运算结果15与6相加,得到21.解法二:第一步:取n=6;第二步:计算;第三步:输出运算结果21.绿色通道:本题的解法二体现了算法的本质:对一类问题的机械的、统一的求解方法.将步骤一直写下去,便得到任意有限个数相加的算法.运用公式使算法显得简单,特别地,当加数的个数比较多时,解法二便显示了它的优越性.变式训练写出求246810的一个算法.思路分析:根据算法的特点可知我们学过的加、减、乘、除运算法则都是算法,所以只要按照具体的规则有步骤地描述解决的过程,便可得到该题的算法.解:第一步:计算24,得到8;第二步:将第一步的运算结果8与6相乘,得到48;第三步:将第二步的运算结果48与8相乘,得到384;第四步:将第三步的运算结果384与10相乘,得到3 840.例2写出一个求有限整数序列中的最大值的算法.思路分析:你可能觉得,求一个整数序列的最大值是一个很简单的事,的确从10个、8个整数中找出最大值,你一眼就可以看得出来.可是如果是要从一百万个年龄序列表中找出年龄最大的一个,要是没有算法,可就是一件很困难的事了.可计算机利用软件瞬间就可以找出最大值,计算机要靠软件(程序)支持,编写程序要依赖算法,因此我们要编写出合理的、高效的算法就非常必要了.解:第一步:先假定序列中的第一个数为“最大值”.第二步:将序列的第二个整数值与“最大值”比较,如果第二个整数大于“最大值”,这时就假定这个数为“最大值”.第三步:将序列的第三个整数值与“最大值”比较,如果第三个整数大于“最大值”,这时就假定这个数为“最大值”.第四步:将序列的第四个整数值与“最大值”比较,如果第四个整数大于“最大值”,这时就假定这个数为“最大值”.依此类推第n步:将序列的第n个整数值与“最大值”比较,如果第n个整数大于“最大值”,这时就假定这个数为“最大值”.第n+1步:直到序列中没有可比的数为止,“最大值”就是序列的最大值.变式训练任意给定两个实数,设计一个算法判断它们的平方的大小关系.思路分析:设任意给定两个实数a、b,要比较a2、b2的大小,只要比较a2-b2与0的大小就行了.算法设计要符合算法的特性,即在有限步内完成,每一步准确清晰可行,给定值后能得出准确的结果.解:算法设计如下:第一步:任意给定两个实数a、b;第二步:计算a2-b2的值;第三步:若a2-b20,则a2b2;若a2-b2=0,则a2=b2;a2-b20,则a2b2.例3若要按从大到小给7,5,9,3,10五个数排序,试写出算法.思路分析:课本中例题3给出了求两个数的最大公因数的算法,可以参考此法先求五个数的最大值,设为a1,再求剩下几个数的最大值,设为a2,依次进行下去,最后按序输出即可,再请思考,是否还有其他方法?解:第一步:a7,b5,c9,d3,e10.第二步:依次用a与其余各数比较,若a大于其余各数,则a最大,令a1a,否则,拿那个比a大的数继续与剩下的数比较,按此法则进行下去,直到最后一个数也参与了比较,这样最后得到的数就是最大数令它为a1.第三步:剩下的四个数继续按照第二步的法则得到最大数令它为a2.第四步:剩下的三个数继续按照第二步的法则得到最大数令它为a3.第五步:剩下的最后两个数进行比较,较大者设为a4,较小者设为a5.第六步:输出a1,a2,a3,a4,a5.黑色陷阱:常见错误有以下几点:不知道如何使用算法,比如写成第一步,输入7,5,9,3,10;第二步比较这五个数的大小.这样就不符合计算机语言的特点,算法是让计算机理解的语言,有些问题计算机是无法做到的,比如让计算机出去买一斤鸡蛋.变式训练给定一个一元二次方程ax2+bx+c=0,设计一个算法,判断方程根的情况.思路分析:设D=b2-4ac,根据D0,D=0,D0即可判定出方程根的情况.所以可先计算出D=b2-4ac,再分三步设计算法.算法设计如下:解:第一步:计算D=b2-4ac;第二步:如果D0,那么方程有两个不相等的实数根;第三步:如果D=0,那么方程有两个相等的实数根;第四步:如果D0,那么方程没有实数根.例4在电视台的庆中秋的娱乐节目中,主持人出示了一份价值在100元以内的月饼,并开始竟猜.主持人只能回答高了,低了或正确.回答下列问题:(1)参与者回答:80元;主持人回答高了;问说明价格在哪个范围;(2)参与者回答:40元;主持人回答低了;问说明价格在哪个范围;(3)参与者回答:60元;主持人回答低了;问说明价格在哪个范围.接下来你会如何猜测?思路分析:根据参与者的猜测,我们知道,参与者首先需要确定的是商品价格的范围,数学上一般可以用区间来表示,然后再根据主持人的回答,报出区间中点,将价格区间缩小一半,因此应当猜70元.解:(1)价格在0到80元之间;(2)价格在40到80元之间;(3)价格在60到80元之间,接下来会猜测的数应是70元,然后根据主持人的回答继续猜,直至猜到正确的价格.绿色通道:从主持人和参与者的对话中把握参与者猜测的基本思路,实际上就是确定准确价格算法的算理.在分析算理后,归纳概括出逐步判断的步骤,即算法.从而把握算法的基本思想程序化思想,在归纳概括中培养逻辑思维能力.变式训练给出下面的算法:S1m=aS2若bm,则m=bS3若cm,则m=dS4若dm,则m=dS5输出m.该算法表示()A.a,b,c,d中最大值B.a,b,c,d中最小值C.将a,b,c,d由小到大排序D.将a,b,c,d由大到小排序思路分析:这是一给出算法描述,让我们理解其表达的意义的问题.关键是读懂算法每一步的含义.可以看出算法中一直将m与b、c、d做比较,并且总把最小的记为m,所以该算法表示的是找出a、b、c、d中最小值.答案:B例5在一次演讲比赛结束后的成绩统计中,张磊得了85分排第15名,王强得了82分排第16名,排完后,评委发现张哲得了84分,但没有给排进,事实上,张哲应排第几名?另外,孙明和石志伟在原来的排名中,分别排第5名和第23名,现在两个应分别排第几名?思路解析:首先根据得分情况,在82和85之间只能有一个84,所以,张哲应排第16名,这样在16名以前的名次都不会改变,而在16名以后的名次都要后推一个名次.答案:张哲应排第16名,孙明的排名不变仍排第5名,而石志伟的排名应向后退一位,排第24名.变式训练用直接插入排序法,给下面一组数据从小到大排序.83975解:按照直接插入排序法的思想和操作步骤,可如下进行排序.第一步:38975(前两个数3,8排序)第二步:38975(第3个数9按要求插入到已排好的序列中)第三步:37895(第4个数7按要求插入到已排好的序列中)第四步:35789(第5个数5按要求插入到已排好的序列中)这时各数的顺序就是符合要求的最终顺序.问题探究问题在实际问题和算法理论中,找出好的算法是一项重要的工作.但是对于“好”没有严格的定义.你能谈谈一个好的算法都应该满足哪些标准吗?导思:一个好的算法,必须正确,满足算法的五个基本特征,而且简洁,便于在计算机上操作运行.探究:算法就其本质来讲,就是一种解决问题的方法,只不过更具有程序化罢了.我们可以根据自己的经验思考一个好的解决问题的方法应该具有哪些特点,然后看这些特点在算法上都应该有什么样的体现,就可以回答这个问题了.正如所有的好的解决问题的方法必须是正确的一样,一个好的算法首先必须是正确的.正确性对不同的事情有着不同的含义.对于算法来讲,正确性包含以下几个层次:(1)算法不能含有语法错误,否则算法不能正常执行;(2)算法对于几组输入数据能够得出满足规格说明要求的结果;(3)算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果;(4)算法对于一切合法的输入数据都能产生满足规格说明要求的结果.其次,我们容易想到一个好的解决问题的方法应该是思路清晰,让人容易理解的,这样就可以让更多的人掌握我们的算法.同理,我们写出的算法要具有可读性,格式要工整、规范,思路要清晰、准确,以便和其他的人更好地交流、合作.此外,我们做事还要考虑这件事需要花费的时间和占用的空间.一般来讲,花费时间和占用空间少的方法会更好.同样地,算法也有效率高与低及存储量需求.效率指的是算法执行时间.对于解决同一问题的多个算法,执行时间短的算法效率高.存储量需求是指算法执行过程中所需要的最大存储空间.如果所占空间量依赖于特定的输入,则除特别指明外,均按最坏情况来分析.