人教A版2020届高考数学一轮复习讲义：算法与程序框图

1、算法与程序框图知识讲解一、算法1.算法的概念：由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照一定规则解决某一类问题的明确的和有限的步骤，称为算法（algorithm）通常可以编成计算机程序，让计算机执行并解决问题2.算法的特征：1）有穷性：算法必须在执行有限步后结束，通常还理解为实际上能够容忍的合理限度；2）确定性：算法的每一个步骤必须有确定的含义；3）可行性：组成算法的每个步骤和操作必须是相当基本的，原则上都是能精确地执行的；4）输入：有零个或多个输入：5）输出：有一个或多个输出3.算法的描述：用自然语言；用数学语言；用算法语言（程序设计语言）；用程序框图（流程图）4.算法的

2、三种基本逻辑结构：1）顺序结构：最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的如下图，只有在执行完a框指定的操作后，才能接着执行b框指定的操作；2）条件（分支）结构：在一个算法中，用来处理需要根据条件是否成立有不同的流向的结构常见的条件结构的程序框图有下面两种形式： 3）循环结构：从某处开始，按照一定的条件反复执行某些步骤的情况，就是循环结构，其中反复执行的步骤称为循环体常见的循环结构的框图对应为：注意事项：1.在画程序框图时，从开始框沿箭头必须能到达结束框，特别是条件分支结构应沿每条支路都能到达结束框，流程线必须加箭头表示顺序2.对于循环结构有如下需要注意的情况：1）循

3、环结构非常适合计算机处理，因为计算机的运算速度非常快，执行成千上万次的重复计算，只不过是一瞬间的事，且能保证每次的结果都正确；2）循环结构要有中止循环体的条件，不能无休止的运算下去，循环结构中一定包含条件结构，如就是中止循环的条件；3）循环结构的关键是，要理解“累加变量”和“用代替”，是一个累加变量， 是计数变量，每循环一次，和都要发生变化，这两步要重复计算若干次；4）一种循环结构是先判断是否成立，若是，执行循环体；若否，则中止循环，像这样，每次执行循环体前对控制循环条件进行判断，条件满足时执行循环体，不满足则停止，称为当型循环除了当型循环外，常用的循环结构还有直到型循环二、程序框图程序框图的

4、概念：用一些通用的图形符号构成的一张图来表示算法，称为程序框图（简称框图）常用图形符号：图形符号名称符号表示的意义起、止框框图的开始或结束输入、输出框数据的输入或者结果的输出处理框赋值、执行计算语句、结果的传送判断框根据给定条件判断流程线流程进行的方向连结点连结另一页或另一部分的框图注意事项：1） 画程序框图的规则：使用标准的框图的符号；框图一般按从上到下、从左到右的方向画；除判断框外，大多数框图符号只有一个进入点和一个退出点判断框是具有超过一个退出点的惟一符号；一种判断框是“是”与“不是”两分支的判断，而且有且仅有两个结果；另一种是多分支判断，有几种不同的结果；在图形符号内描述的语言要非常简

5、练清楚2）画程序框图要注意的几点：起、止框是任何流程不可少的，表示程序的开始和结束；输入、输出框可以用在算法中任何需要输入、输出的位置；算法中间要处理数据或计算，可分别写在不同的处理框内；当算法要求你对两个不同的结果进行判断时，要写在判断框内；一个算法步骤到另一个算法步骤用流程线连结；如果一个框图需要分开来画，要在断开处画上连结点，并标出连结的号码如：用海伦公式求任意三角形的面积的程序框图，其中断开处画上连结点，并标出连结的号码三、算法语句1.程序语言的基本语句结构：输入语句、输出语句、赋值语句、条件语句、循环语句2.赋值语句：表明赋给某一个变量一个具体的确定值的语句一般格式：变量名表达式；其

6、中“”叫做赋值号作用：先计算出赋值号右边表达式的值，然后将它赋给左边的变量，使该变量的值等于表达式的值3.输入语句：在每次程序运行时，用于输入相应的初始数据的语句，我们主要介绍键盘输入语句scilab中的输入语句常用的是：“input”；一般格式：变量名=input（“提示内容”）例：a=input（“x1”）；b=input（“x2”）；aver=（a+b）/2表示输入，的值，求它们的算术平均数，在scilab界面内运行结果如下：->a=input（"x1"）；b=input（"x2"）；aver=（a+b）/2x1->此时通过键盘输入x1

7、的值，如，再按“enter”键，界面出现：x2->输入x2的值，如，再按“enter”键，这时界面出现：aver = 54.输出语句：以某种形式把求解结果输出的语句scilab中有：print，write，format，printf，disp等输出语句，主要介绍print语句：一般格式：print（%io（2），表达式）；其中参数%io（2）表示在屏幕上输出5.条件语句：处理条件分支结构的算法语句scilab程序语言中常用的条件语句为if语句一般格式：if 表达式语句序列1；else语句序列2；end最简格式：if 表达式语句序列1；end6.循环语句：处理算法中的循环结构的语句；sci

8、lab有两种循环语句：for循环和while循环for循环的格式：for 循环变量=初值：步长：终值循环体；endwhile语句的一般格式：while 表达式（即条件）循环体；end注意事项：1.计算机能够直接或间接理解的程序语言有很多种，比如c语言，basic语言，以及一些应用数学软件：matlab，mathsmatics，scilab对应的计算机语言这里的基本语句结构在这些语言中都是存在的，但是对应不同的程序语言，都会有自己的输入指令与方法这里是以一种语言为例，让大家理解程序语句的含义，为以后深入学习程序设计打下基础2.赋值语句：1）赋值号左边只能是变量名，而不是表达式；如是错误的；2）赋

9、值号左右不能对换，是将赋值号右边的表达式的值赋给左边的变量；如表示用的值替代变量原先的值，与不同；3）不能利用赋值语句进行代数式（或符号）的演算；如是不能实现的；并且在一个赋值语句中，只能给一个变量赋值；3）赋值号与数学中的等号的意义不同，执行赋值语句后，右面表达式的值会赋给左边，如果左边变量原来有一个值，会自动被冲掉，如表示将的原值加再赋给，即的值加3.输入语句：在某些算法中，变量的初值要根据情况经常地改变，一般我们把程序与初始数据分开，每次算题时，即使初始数据改变，也不必改变程序部分，只要程序运行时，输入相应的数据即可，这个过程在程序语言中，用“输入语句”来控制输入语句中还有read输入语

10、句等输入语句要求输入的一般都是具体的常数，也可输入单个或多个字符，格式为：变量名=input（“提示内容”，“string”），string表示输入字符型变量4.循环语句：for语句：先把初值赋给循环变量，记下终值和步长，循环变量增值到超过终值时，执行end后面的语句，不超过时，执行for后面的语句；循环变量起计数作用，控制算法中循环次数，有初值与终值，步长是指循环变量每次增加的值，步长为时，可以省略；while语句：先判断条件是否成立，并在符合条件时，执行循环体；直到某次不符合时，跳到end后面的语句对应的基本框图是：5.在程序语言中，乘、除、乘方、求平方根、绝对值，分别用下列符号表示：*、

11、/、sqrt（）、abs（）程序语言中，一般“”为赋值号，“”表示等号、分别写成：、在程序中，如果赋值语句后面用分号隔开，则被赋值的变量不会输出，一般不随便使用逗号或句号，而是直接使用回车或空格四、算法案例1.更相减损术：求两个整数的最大公约数的算法更相减损术的步骤：以两个数中较大的数减去较小的数，以差数和较小的数构成一对新的数，对这一对数再用大数减小数，以同样的操作一直做下去，直到产生一对相等的数，此数就是这两个数的最大公约数等值算法：用“更相减损术”设计出来的算法求最大公约数的算法称为“等值算法”，用等值算法可以求任意两个正整数的最大公约数2.辗转相除法：又称欧几里得算法，是由欧几里得在公

12、元前300年左右首先提出来的求两个数的最大公约数的算法。辗转相除法的步骤：对于给定的两个数，以其中较大的数除以较小的数得到一个余数，将较小的数与余数看成一对新的数，重复上面的步骤，直到余数为零为止，此时上一步中较小的数即为所求的最大公约数。以求和的最大公约数为例：,故即为所求。3.秦九韶算法：求多项式的值的算法具体如下：对任意一个元多项式，改写成如下形式：，求多项式的值时，先计算最内层括号内的一次多项式的值，即，然后由内向外逐层计算一次多项式的值，即，这样，求一个次多项式的值，就转化为求个一次多项式的值令，则递推公式为，其中到目前为止，此算法仍然是世界上多项式求值的最先进的算法秦九韶算法与其它

13、算法在计算量上面的比较：，1）直接求和法：先计算各个单项式的值，再把它们相加，乘法次数为，加法次数；2）逐项求和法：先计算的各项幂的值，再分别相乘，计算幂值需要乘法次，将幂值与多项式系数相乘需要乘法次，故共需要乘法次，加法次此方法对直接求和法有所改进，但仍然比秦九韶算法计算量大很多3）秦九韶算法：计算量仅为乘法次，加法次经典例题一选择题（共16小题）1某程序框图如图所示，该程序运行后输出k的值是（）a5b6c7d8【解答】解：当s=0时，满足执行循环的条件，执行循环体后s=1，k=2，当s=1时，满足执行循环的条件，执行循环体后s=5，k=3，当s=5时，满足执行循环的条件，执行循环体后s=1

14、3，k=4，当s=13时，满足执行循环的条件，执行循环体后s=29，k=5，当s=29时，满足执行循环的条件，执行循环体后s=61，k=6，当s=61时，满足执行循环的条件，执行循环体后s=125，k=7，当s=125时，满足执行循环的条件，执行循环体后s=253，k=8，当s=253时，不满足执行循环的条件，故输出的k值为8，故选：d2执行如图的程序框图，若输入a=5，b=2，则输出的i=（）a3b4c5d6【解答】解：第一次执行循环体后，a=152，b=4，满足继续循环的条件，i=1；第二次执行循环体后，a=454，b=8，满足继续循环的条件，i=2；第三次执行循环体后，a=1358，b=

15、16，满足继续循环的条件，i=3；第四次执行循环体后，a=40516，b=32，不满足继续循环的条件，故输出的i=3，故选：a3执行如图程序框图，若输入的n等于10，则输出的结果是（）a2b3c-12d13【解答】解：若输入的n等于10，则当i=1时，满足进行循环的条件，a=3，i=2；当i=2时，满足进行循环的条件，a=12，i=3；当i=3时，满足进行循环的条件，a=13，i=4；当i=4时，满足进行循环的条件，a=2，i=5；当i=5时，满足进行循环的条件，a=3，i=6；当i=6时，满足进行循环的条件，a=12，i=7；当i=7时，满足进行循环的条件，a=13，i=8；当i=8时，满足

16、进行循环的条件，a=2，i=9；当i=9时，满足进行循环的条件，a=3，i=10；当i=10时，满足进行循环的条件，a=12，i=11；当i=11时，不满足进行循环的条件，故输出的a=12，故选：c4执行如图所示的程序框图，则输出的s的值为（）a91b91c21d21【解答】解：当n=1时，f（x）=6exx，f（x）=6ex1，当x（0，+）时，f（x）0恒成立，满足f（x）在（0，+）为递增函数，故s=1，n=2；当n=2时，f（x）=6ex2x，f（x）=6ex2，当x（0，+）时，f（x）0恒成立，满足f（x）在（0，+）为递增函数，故s=3，n=3；当n=3时，f（x）=6ex3x，

17、f（x）=6ex3，当x（0，+）时，f（x）0恒成立，满足f（x）在（0，+）为递增函数，故s=6，n=4；当n=4时，f（x）=6ex4x，f（x）=6ex4，当x（0，+）时，f（x）0恒成立，满足f（x）在（0，+）为递增函数，故s=10，n=5；当n=5时，f（x）=6ex5x，f（x）=6ex5，当x（0，+）时，f（x）0恒成立，满足f（x）在（0，+）为递增函数，故s=15，n=6；当n=6时，f（x）=6ex6x，f（x）=6ex6，当x（0，+）时，f（x）0恒成立，满足f（x）在（0，+）为递增函数，故s=21，n=7；当n=7时，f（x）=6ex7x，f（x）=6ex7

18、，当x（0，+）时，f（x）0不恒成立，不满足f（x）在（0，+）为递增函数，故输出的s=21，故选：d5执行如图所示的程序框图，若输入t1，3，则输出s的取值范围是（）ae2，1b1，ec0，1de2，e【解答】解：由已知可得：程序框图的功能是计算并输出s=&et-1，t-1，1)&log3t，t1，3的值域，当t1，1）时，s=et1e2，1），当t1，3时，s=log3t0，1，故输出s的取值范围是0，1，故选：c6执行如图所示的程序框图，则输出的n值为（）a3b4c5d6【解答】解：当m=16时，不满足cosm0，执行循环体后，m=8，n=2；当m=8时，不满足cosm

19、0，执行循环体后，m=4，n=3；当m=4时，不满足cosm0，执行循环体后，m=2，n=4；当m=2时，不满足cosm0，执行循环体后，m=1，n=5；当m=1时，满足cosm0，故输出的n=5，故选：c7如图所示的一个算法的程序框图，则输出d的最大值为（）a2b2c1+2d1+22【解答】解：模拟程序的运行，可得程序框图的功能是求半圆y=1-x2上的点到直线xy2=0的距离的最大值，如图：可得：d的最大值为op+r=2+1故选：c8中国古代有计算多项式的秦九韶算法，如图是实现该算法的程序框图执行该程序框图，若输入的x=2，n=2，依次输入的a为2，3，7，则输出的s等于（）a7b8c21d

20、49【解答】解：根据程序框图的算法，执行该程序框图，若输入的x=2，n=2，依次输入的a为2，3，7，则输出的s：根据判断框：得s=21，故选：c9中国古代数学著作孙子算经中有这样一道算术题：“今有物不知其数，三三数之余二，五五数之余三，问物几何？”人们把此类题目称为“中国剩余定理”，若正整数n除以正整数m后的余数为n，则记为n=nmodm，例如2=11mod3现将该问题以程序框图的算法给出，执行该程序框图，则输出的n等于（）a39b38c37d36【解答】解：由已知中的程序框图可知：该程序的功能是利用循环结构计算并输出同时满足条件：被3除余2，被5除余3，由已知中四个答案中的数据可得，故输出

21、的n为38，故选：b10某校为了解高一年级300名学生对历史、地理学科的选课情况，对学生进行编号，用1，2，300表示，并用（xi，yi）表示第i名学生的选课情况，其中根据如图所示的程序框图，下列说法错误的是xi=&0，第i名学生不选历史&1，第i名学生选历史yi=&0，第i名学生不选地理&1，第i名学生选地理（）am为选择历史的学生人数bn为选择地理的学生人数cs为至少选择历史、地理一门学科的学生人数ds为选择历史的学生人数与选择地理的学生人数之和【解答】解：由已知中的程序框图可知：该程序的功能是利用循环结构计算并输出变量s，m，n的值，根据xi=1时，执行m

22、=m+1，故m为选择历史的学生人数，故a正确；根据yi=1时，执行n=n+1，故n为选择地理的学生人数，故b正确；根据s=m+n，故s为选择历史的学生人数与选择地理的学生人数之和，故d正确，c错误，故选：c11执行如图所示的程序框图，则输出d的最大值为（）a2-1b2c2d2+1【解答】解：模拟程序的运行，可得程序框图的功能是求半圆y=1-x2上的点到直线xy2=0的距离的最大值，如图：可得：d的最大值为op+r=2+1故选：d12执行如图所示的程序框图，如果输入的a=1.8，则输出的s=（）（其中a表示不超过a的最大整数，如0.3=0，2.3=3）a8b6c15d32【解答】解：如果输入的a

23、=1.8，则s=0，i=1执行第一次循环时：s=0+1=1，a=13.6=2.6，i=2，执行第二次循环时：s=1+（2）=1，a=1+5.2=6.2，i=3，当i=6时，输出s=15故选：c13执行如图所示的程序框图，如果输入的是n=0，s=0，输出的结果是7，则判断框中“”应填入（）as56bs67cs78ds89【解答】解：输入的是n=0，s=0，执行循环体后，s=12，不满足输出的条件，故应不满足判断框中的条件，故n=1，s=23，不满足输出的条件，故应不满足判断框中的条件，故n=2，s=34，不满足输出的条件，故应不满足判断框中的条件，故n=3，s=45，不满足输出的条件，故应不满足判断框中的条件，故n=4，s=56，不满足输出的条件，故应不满足判断框中的条件，故n=5，s=67，不满足输出的条件，故应不满足判断框中的条