1、最新人教版高中数学必修3第一章算法与程序框图教材梳理庖丁巧解牛知识巧学一、算法的含义1.算法的定义 广义的算法是指完成某项工作的方法和步骤,所以我们可以说洗衣机的使用说明书是操作洗衣机的算法,菜谱是做菜的算法,等等. 在数学中,现代意义上的算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤,或看成按要求设计好的有限的确切的计算序列.2.算法的要求 我们现在学习的算法不同于求解一个具体问题的方法,它有如下要求:(1)写出的算法可适用于一类问题,并且再遇到类似问题时能够重复使用;(2)算法过程要做到能一步一步地执行,每一步执行的操作,必须确切,不能含混不清,且在有限步后必须得到问题的结
2、果. 辨析比较 算法与数学问题的解法既有联系又有区别.(1)联系:算法与解法是一般与特殊的关系,也是抽象与具体的关系.譬如,教材先从分析一个具体的二元一次方程组的求解过程(解法)出发,归纳出了二元一次方程组的求解步骤;并且指出,这样的求解步骤也适合有限制条件的二元一次方程组,这些步骤就构成了解二元一次方程组的算法;(2)区别:算法是解决某一类问题所需要的程序和步骤的统称,也可理解为数学中的“通法通解”;而解法是解决某一个具体问题的过程和步骤,是具体的解题过程.二、算法的特征及设计要求1.算法的特征 对于某一个问题,找到解决它的某种算法是指使用一系列运算规则能在有限步骤内求解某类问题,其中的每条
3、规则必须是明确定义的、可行的,不能含糊其辞、模棱两可,同时应对所有的初始数据(而不仅是指对某些特殊数值)有效. 算法从初始步骤开始每一个步骤只能有一个确定的后继步骤,从而组成一个步骤序列,这个序列必须是有限的,序列的终止表示问题得到解决或指出问题没有解答.我们过去学习过的许多数学公式都是算法,加、减、乘、除运算法则以及多项式的运算法则也是算法. 算法可以概括出以下几个特点:(1)概括性:写出的算法必须能解决这一类问题,并能重复使用.例如课本中关于二元一次方程组的求解问题,也适用于其他二元一次方程组的解法.(2)逻辑性:也就是算法应具有正确性和顺序性.算法从初始步骤开始,分为若干明确的步骤,前一
4、步是后一步的基础,只有执行完前一步才能进行下一步,并且每一步都有确切的含义,从而组成了一个具有很强逻辑性的序列.(3)有穷性:算法的步骤序列是有限的.一个算法对任何合法的输入值必须总是在执行有穷步之后结束,且每一步都可在有穷时间内完成.(4)不唯一性:求解某个问题的算法不是唯一的,对于一个问题可以有不同的算法,如课本关于二元一次方程组的求解问题可以用公式法,也可以用高斯消去法.(5)普遍性:很多具体的问题,都可以设计合理的算法去解决,例如心算、手算、计算器计算都要经过有限的、事先设计好的步骤去加以解决,同样一个工作计划、教学计划、生产流程都可以称为“算法”. 辨析比较 课本上有两种表示算法的语
5、言:自然语言和算法语言.对于这两种算法,用自然语言叙述的算法便于理解,但比较冗长,而且操作性不是十分明朗;用数学语言描述的算法十分简洁,而且清晰,操作性强,但较抽象.2.算法的设计要求 首先我们要知道,通常算法并不给出精确的解,而是说明如何得到解.算法由一系列加减乘除等运算以及顺序、判断、循环的操作指令完成.研究算法只是将研究解决一类问题的方法分解成一些合理的操作步骤.这些操作步骤必须明确有效并且能在有限步内完成. 如何设计一个算法呢?首先应该从头到尾将这个问题解决的思路,以及各种可能出现的情况都想到,并且进行抽象概括.然后对过程进行细分,把每一个操作概括为一个简洁的算法语句,最后将算法一步步
6、地写出来.一般情况下,一个问题对应很多不同的算法,我们在实际应用中可以选择一个效率最高的算法.算法设计的要求:(1)写出的算法必须能解决一类问题(如判断一个任意整数n是否为质数,求任意一个函数式的近似解等),并且能重复使用.(2)要使算法尽量简单,步骤尽量少,算法从初始步骤开始,每一个步骤只能有一个后继步骤,从而组成一个步骤序列,序列的终止表示问题得到解答或指出问题没有答案.(3)算法过程要能一步一步执行,每一步执行的操作,必须确切不能含糊不清,而且在有限步后能得出结果.(4)尽量地从步骤和思想上优化算法,使得算法效率最高. 深化升华 (1)算法实际上就是解决问题的一种程式化方法,它通常指向某
7、一个或某一类问题,而解决的过程具有程序性和构造性.算法又可看成是一种解决问题的特殊的有效方法,我们在学习的过程中应重点学习算法的构造过程.(2)算法与一般的解决问题的过程有联系,但算法是“傻瓜化”的,即算法要“面面俱到”,不能省略任何一个小小的步骤(只有这样做,人们才能在设计出算法后,把具体的执行过程交给计算机去完成).三、算法的描述 描述算法可以用不同的方式.例如:可以用自然语言和数学语言加以叙述,也可以借助形式语言(算法语言)给出精确的说明,还可以用程序框图直观地显示算法的全貌.1.自然语言 自然语言就是人们日常使用的语言,可以是人们之间用来交流的语言、术语等,它通过分步的方式表达解决问题
8、的过程.优点:好理解,当算法的执行都是先后顺序时比较容易理解.难点:表达冗长,且不易表达清楚步骤间的重复操作、分情况处理、先后顺序等问题.2.程序框图 程序框图是用规定的图形符号来表达算法的具体过程.优点:简捷形象、步骤的执行方向直观明了.3.程序语言 程序语言是将自然语言和框图所表达的解决问题的步骤用特定的计算机可识别的低级或高级语言编写而成的.特点:能在计算机上执行,但格式要求严格.四、程序框图1.程序框图的定义 程序框图又称流程图,是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形. 打个比方,写文章要先拟提纲,盖楼房要先设计图纸,而计算机解题要先考虑算法,然后编制程序框图
9、,程序框图是人们用来描述算法步骤的形象化的方法. 在程序框图中,每一个框都清楚地表示了这一步要做的事,框与框之间的箭头表示相邻两框所做事情的先后顺序,每一种不同形状的框表示不同的操作方法!若把程序框图画出来,对编者来说,思路清晰,逻辑关系一目了然,尤其是在一些较复杂的程序编制中更为实用.2.构成程序框图的图形符号及其作用 通常,程序框图由程序框和流程线来组成.一个或几个程序框的组合表示算法的一个步骤;流程线是方向箭头,按照算法进行的顺序将程序框连接起来. 程序框图表示算法用到的图形符号如下表:图形符号名称符号表示的意义起止框流程图的开始或者结束输入输出框数据的输入或者结果的输出处理框赋值、执行
10、计算语句、结果传送判断框根据给定的条件判断流程线流程进行的方向连结点连接另一页或另一部分程序框图 学法一得 作程序框图的规则及注意点:(1)每一种程序框图的符号都有自己的意义,不能混用,符号一定要规范.起始框只有一条流出线,终止框只有一条流入线,输入输出框和处理框只有一条流入线和流出线.判断框有一条流入线和两条流出线(True,False).(2)流程图的画法是从上而下、从左而右的方向画.一个算法的步骤到另一个算法的步骤,要用流程线连接.流程线要带箭头,表明流程执行的次序.(3)起止框是任何程序框图必不可少的,表明程序的开始和结束.(4)算法中间要处理的数据,一般分别写在不同的处理框内.(5)
11、当算法要对两个不同的结果进行判断时,判断条件写在判断框内.(6)程序框图符号框内的文字表述要简洁精炼.(7)一般情况下,我们先用自然语言编写算法,然后再画程序框图.3.程序框图的构成一个程序框图包括以下几部分:(1)实现不同算法功能的相对应的程序框图的图形符号;(2)带箭头的流程线;(3)程序框内必要的说明文字.五、顺序结构 算法含有两大因素:一是操作,主要包括算术运算、逻辑运算、函数运算等;二是逻辑结构.逻辑结构控制着算法的各操作的执行顺序.我们写出的或画出的程序框图,一定要使大家看得清楚、明白、容易阅读.如果写的算法毫无头绪,就让人很难阅读和理解.这就要求算法要有一个良好的结构. 通常一个
12、算法只能由三种基本逻辑结构组成,算法的三种基本逻辑结构分别为:顺序结构、条件结构、循环结构. 顺序结构是最简单的算法结构,语句与语句之间,框与框之间是按从上到下的顺序进行的. 它是由若干个依次执行的步骤组成的,是任何一个算法都离不开的一种基本算法结构.我们可以用图1-1-1表示,其中的A部分,B部分是依次执行的.只有在执行完A部分的操作后,才会顺次执行B部分的操作.图1-1-1 深化升华 顺序结构是从上而下依次执行命令,每步只执行一次,不会引起程序步骤的跳转.它只能解决一些简单的问题,步骤之间不能随便调换,调换会使算法不运行或出现错误.单独的顺序结构一般出现在这样几种题目中:根据公式求值、求一
13、般函数(非分段函数)的函数值等;再者顺序结构是其他结构的基础,会出现在其他结构的运行的前后,是算法必需的一个基本结构.六、条件结构 其实对于条件结构我们遇到的最早,我们遇到一个岔路口,你需要选择向哪走;“鱼和熊掌不能兼得”也只有一个选择;还有我们去坐出租车有3千米以内7元,3千米以外每千米3元的收费标准;等等.这些都是条件结构.显然,条件结构中有一个条件和两个分支,根据条件判断到底来选择哪个分支. 在一个算法中,通常会遇到一些条件的判断,算法的流程根据条件是否成立有不同的流向,这种先根据条件判断,再决定执行哪一种操作的结构称为条件结构. 图1-1-2所示的虚线框内是一种条件结构,此结构中包含一
14、个判断框,根据给定的条件P是否成立而选择A框或B框,请注意无论条件P是否成立,只能执行A框或B框之一,不可能既执行A框又执行B框,也不可能A框、B框都不执行,无论走哪一条路径,在执行完A或B之后,脱离本条件结构.当然A或B两个框中可以有一个是空的,即不执行任何操作,如图1-1-3也是条件结构的一种. 图1-1-2 图1-1-3 辨析比较 条件结构不同于顺序结构的地方是:它不是依次执行操作指令进行运算,而是依据条件作出逻辑判断,选择执行不同指令中的一个.一般地,这里的判断主要是判断“是”(即“Y”)或“否”(即“N”),即是否符合件的要求,因而它有一个入口和两个出口.七、循环结构 在一些算法中,
15、经常会出现从某处开始,按照一定的条件,反复执行某一处理步骤的情况,这就是循环结构.反复执行的处理步骤称为循环体.显然,循环结构中有关于条件的判断.因此,循环结构中必包含条件结构. 我们先看一个小例子,比如我们要计算1234100,该怎么办呢?我们知道最直接的办法:图1-1-4 只要一次一次地乘就是了,对我们来说这是一个烦琐而乏味的工作,可是计算机最适合这种工作了,因为计算机运算速度快,执行成千上万的重复操作只需要很短时间,却能保证每次的结果非常准确.首先我们知道一共要乘100次来设置一个变量i,它的用处是控制计算次数,我们要再设置一个变量m来积累一下我们前边得到的乘积的结果.算法如下: 第一步
16、,首先对变量赋值,=; 第二步,对变量赋值,=; 第三步,让累积,得到要求的值m=mi; 第四步,变量增加,=i+1; 第五步,判断一下,如果i100则输出,否则转至第三步.流程图如图1-1-4. 我们来仔细地看一下这个例子的程序框图,重点看一下虚线框里面的部分(结合下面的解释): 令i=1,m=1(注意不是0),赋完初值之后,循环就启动了.首先,m=11=1,然后i变为2,到判断框判断一下比100小,那么转回来再开始一遍刚才的过程.直到循环到i=100时,m=1234100,到下一步时,i=100+1=101,此时i=101100,便退出了循环结构. 如果一个计算结构要重复一系列的计算步骤若
17、干次,每次计算步骤完全相同,则这种算法结构叫做循环结构. 可看出里面有几个比较重要的部分:类似于例子中的用来控制循环次数的量称为循环变量(类似于例子中的用来存储循环问题的结果的变量叫做累积变量).由于m=m+1这个语句在每次循环时都运行,我们把它叫做循环体.并且还有一个控制循环是否退出的判断框称为循环终止条件.这三部分构成了一个完整的循环结构.一个循环结构可如图1-1-5所示.图1-1-5 学法一得 写循环结构的步骤及应注意的问题: 书写循环结构主要要找三个重点:循环变量及初始值;循环体的内容;循环终止的条件,只要找到这些问题就好办了.书写一个循环结构要检查一下下面几个方面:(1)只有一个入口
18、和一个出口(注意是看整个循环结构,不是看某一个部分);(2)结构的每一部分都可能被执行到(虽然每次只执行一条路线);(3)循环体内一定有一个选择结构来控制循环的流程;(4)结构体内的循环必须在有限次之内终止,不能出现死循环;(5)注意正确设置循环次数,不要多1或者少1.常见的循环结构有三种:计数型循环、当型循环和直到型循环.1.计数型循环结构一般用于预先知道重复的次数的循环结构.2.当型(While型)循环结构 当型循环一般用于预先难以知道循环次数的循环结构,通过设置某个条件,当条件满足时就重复操作,当条件不满足时就退出循环.如图1-1-6所示,它的功能主要是当给定条件q成立时,执行A框操作,
19、执行完A后,再判断条件q是否成立,如果仍然成立,再执行A框,如此反复执行A框,直到某一次条件不成立为止.此时不执行A框,从b点脱离循环结构.3.直到型(Until)循环结构 直到型循环结构一般用于预先难以知道循环次数的循环结构,通过设置某个条件,当条件不满足时退出循环. 如图1-1-7所示,它的功能是先执行A框,然后判断给定的条件q是否成立,如果条件q不成立,则执行A,然后再对条件q作判断,如果条件q仍然不成立,又执行A如此反复执行A,直到给定的条件q成立为止,此时不再执行A,从b点脱离本循环结构. 图1-1-6 图1-1-7 辨析比较 三种基本结构的关系如何?有哪些共同特点?顺序结构是最基本
20、的也是最简单的控制结构;条件结构则是需要通过先判断,再决定执行哪个程序的控制结构;循环结构则是需要反复执行同一程序的控制结构,循环结构一定包含顺序结构和条件结构.顺序结构、条件结构、循环结构的共同特点是:(1)只有一个入口.(2)只有一个出口(实际运行的程序).请注意:一个菱形判断框有两个出口,而一个条件结构只有一个出口,不要将菱形框的出口和条件结构的出口混为一谈.(3)结构内的每一部分都有机会被执行到,也就是说对每一个框来说都应当有一条从入口到出 口的路径通过它.像图1-1-8中的A,没有一条从入口到出口的路径通过它,是不符合要求的程序框图.(4)结构内不存在死循环,即无终止的循环,像图1-
21、1-9就是一个死循环,在流程图中是不允许有死循环出现的. 图1-1-8 图1-1-9八、计数变量与累加、累乘变量 在有关累加、累乘问题的循环结构中一般都有一个计数变量和累加、累乘变量.计数变量用于记录循环次数,累加变量用于输出结果.计数变量和累加变量一般是同步执行的,累加或累乘一次,同时又计数一次.1.计数变量可以统计执行循环的次数,它控制着循环的开始和结束;算法未执行循环结构时,就赋予计数变量初始值,预示着循环开始,每执行一次循环结构,计数变量的值发生变化,并在每一次重复执行完循环体时(直到型)或重新开始执行循环体时(当型),要判断循环体的条件是否已达到终止循环的目的.2.累加变量,它是我们
22、编写算法时至关重要的量,我们根据要求制定它的变化情况,通常情况下与计数变量有对应关系.每执行一次循环结构,累加变量的值变化一次,并在每一次重复执行完循环体时(直到型)或重新开始执行循环体时(当型),观察累加变量值的变化情况,并根据题意对累加变量设置使循环结构终止循环的条件.3.累乘变量同累加变量的设置目的一样,只不过分工不同.前者是用来计算很多项的和,后者是用来处理很多项的积. 累加、累乘变量是为最终输出的结果服务的,通常累加变量用来处理有通项公式或递推公式的数列的前n项和,累乘变量用来处理像阶乘一样有通项公式或递推公式的数列的前n项的积. 深化升华 在循环结构中,要求注意根据条件设计合理的计
23、数变量、循环变量.特别要求条件的表述要恰当、精确. 若求只含有一个关系式的解析式的函数值时,只用顺序结构就能解决;若是遇到分类讨论或执行时需要判断后才能执行后继步骤的,就必须引入条件结构;如果问题里涉及的运算进行了许多次重复,且每次重复时变量与变量之间有对应关系,就可引入变量,应用于循环结构.典题热题知识点一 算法设计例1 写出解方程x2-2x-3=0的一个算法.思路分析:本题考查一元二次方程的解法.对于本类题目关键是要先写出解方程或方程组的解题过程.解:算法一:第一步,移项,得x2-2x=3.第二步,式配方,得(x-1)2=4.第三步,式两边开方,得x-1=2.第四步,解得x=3或x=-1.
24、算法二:第一步,计算一元二次方程的判别式的值,并判断其符号.显然=22+43=160.第二步,将a=1,b=-2,c=-3代入求根公式x1,2=,得x1=3,x2=-1. 方法归纳 1.该题用了两种方法求解,一种是分解因式法,另一种是求根公式法.对于问题的求解过程,我们需要既强调对“通法通解”的掌握,又强调对所学过的知识的灵活应用.2.传统的数学问题的求解过程就是一个具体的算法.例2 100个和尚吃100个馒头.大和尚一人吃3个,小和尚3人吃一个,求大、小和尚各多少个?试用算法来解本题.思路分析:本题考查二元一次方程组的解法.对于二元一次方程组,我们可以直接套用高斯消元法.解:设有x个大和尚,
25、y个小和尚.算法如下:第一步,先列方程组可得a11=3,a12=,b1=100,a21=1,a22=1,b2=100.第二步,令D=a11a22-a21a12=3-0,方程组有解.第三步,套用公式可求得x=25,y=75. 巧解提示 可以看出只需给出问题的初始值a11=3,a12=,b1=100,a21=1,a22=1,b2=100,套用高斯消元法的算法,问题即可解决,并且步骤简洁,计算量少,且还可以看出该算法具有很强的普遍性.高斯消元法解一般的二元一次方程组的算法如下:第一步,计算D=a11a22-a21a12;第二步,如果D=0,则原方程组无解或有无穷多组解;否则(D0),x1=,x2=;
26、第三步,输出计算结果x1、x2或者无法求解的信息.知识点二 顺序结构例3 f(x)=x2-2x-3,求f(3)、f(5)、f(-5)并计算f(3)+f(5)+f(-5).设计一个解决该问题的算法,并画出流程图.思路分析:本题考查简单的求函数值的顺序结构的程序框图的作法.这是简单的求函数值问题,我们直接代入即可求得函数值.解:算法如下:第一步,输入x=3;第二步,输出y1=x2-2x-3;第三步,输入x=-5;第四步,输出y2=x2-2x-3;第五步,输入x=5;第六步,输出y3=x2-2x-3;第七步,输出y=y1+y2+y3.算法流程图如图1-1-10.图1-1-10 方法归纳 本题不是很特
27、殊,但说明了一般函数(非分段函数)的函数值的求法就是一个简单的顺序结构.但是要注意类似于拓展变式中关于迭代的函数思想的掌握.例4 求底面边长为,侧棱长为5的正四棱锥的体积.给出解决该问题的一个算法.思路分析:本题考查的是几何中的体积计算问题,要用顺序结构来作程序框图.要求正四棱锥的体积,根据体积公式必须先求出底面面积及高,再利用体积公式求出体积.解:算法设计如下:第一步,取a=,l=5;第二步,计算R=;第三步,计算h=;第四步,计算S=a2;第五步,计算V=Sh;第六步,输出计算结果.算法流程图如图1-1-11.图1-1-11 方法归纳 这个题目主要展现了如何来求一个锥体的体积的思维过程,体
28、现了顺序的特点,依次先求高,再求底面积,最后求体积.此题比以前的题目更为抽象,体现了从特殊到一般的转化,也体现了对知识的概括能力.例5 用尺规作图,确定线段AB的一个五等分点.思路分析:本题考查顺序结构作图的步骤及注意事项.确定线段AB的五等分点,是指在线段AB上确定一点M,使得AM=AB.解:算法如下:第一步,从A点出发作一条与原直线不重合的射线.第二步,任取射线上一点C,并在射线上作线段AD,使AD=5AC.第三步,连结DB,并过C点作BD的平行线交AB于M,M就是要找的一个5等分点.这个过程也需要一步一步来实现.作图步骤如下:1.从已知线段的左端点A出发,作一条射线AP.2.在射线上任取
29、一点C,得线段AC.3.在射线上作线段CE=AC.4.在射线上作线段EF=AC.5.在射线上作线段FG=AC.6.在射线上作线段GD=AC,那么线段AD=5AC.7.连结DB.8.过C作BD的平行线,交线段AB于M,这样点M就是线段AB的一个5等分点.图1-1-12 方法归纳 上面是解决这个作图问题的一个算法,我们只要依次执行这一系列步骤,就能确定线段的5等分点.这个算法具有一般性,对于任意自然数n,都可以按照这个算法的思想,设计出确定线段n等分点的步骤,得到解决这个问题的一般算法.知识点三 条件结构例6 有4个数a,b,c,d,要求按由大到小的顺序输出.思路分析:本题考查排序问题中应用条件结
30、构判断的问题.我们可以把a,b,c,d中最大的放在a中,然后将余下的三个数中最大的放在b中,再找出余下的两个数中较大的放在c中,最后输出a,b,c,d.解:算法步骤如下:第一步,找出a和b中的大者放在a中,小者放在b中.第二步,找出c和d中的大者放在c中,小者放在d中.第三步,找出a和c中的大者放在a中,小者放在c中.第四步,找出b和c中的大者放在b中,小者放在c中.第五步,找出b和d中的大者放在b中,小者放在d中.第六步,找出c和d中的大者放在c中,小者放在d中.程序框图如图1-1-13所示.图1-1-13 方法归纳 要比较两个数的大小,一般引入第三个变量,通过它可以实现两个变量的值的交换,
31、从而节约了大量的变量(即计算机中的单元),使算法简捷. 本例中,对a,b,c,d两两之间比较大小,需要比较六次,并且每次比较大小后,需要根据它们之间大小关系执行不同的指令,因而设计算法时需要多次用到条件分支结构,这六个条件分支结构之间的关系是并行的(即它们之间的地位是平等的),并且可以交换位置.由此可见,条件分支结构不仅可以嵌套使用,还可以并行使用.例7 写出求方程ax2+bx+c=0的根的算法,画出相应的程序框图,并要求输出它的实根.思路分析:主要考查含参问题的讨论方法及条件嵌套结构的应用.输入三个实数a,b,c,先判断a是否为零,当a0时,是一元二次方程,则通过判断判别式来求实根.当a=0,b0时,不是一元二次方程,可用一元一次方程的解法来解.解:当a0时,令=b2-4ac,当0时,方程无实数根;当0时,方程有两个实数根x1=,x2=.当a=0时,再考虑b:若b0,则方程的根为x=;
