专题26 算法-2021届新高考数学一轮复习知识点总结与题型归纳面面全

这是一份专题26 算法-2021届新高考数学一轮复习知识点总结与题型归纳面面全，文件包含专题26算法原卷版docx、专题26算法解析版docx等2份学案配套教学资源，其中学案共36页， 欢迎下载使用。

1.算法的概念：由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照一定规则解决某一类问题的明确的和有限的步骤，称为算法（algrithm）．通常可以编成计算机程序，让计算机执行并解决问题．
2.算法的特征：
1）有穷性：算法必须在执行有限步后结束，通常还理解为实际上能够容忍的合理限度；
2）确定性：算法的每一个步骤必须有确定的含义；
3）可行性：组成算法的每个步骤和操作必须是相当基本的，原则上都是能精确地执行的；
4）输入：有零个或多个输入：
5）输出：有一个或多个输出．
3.算法的描述：
①用自然语言；②用数学语言；③用算法语言（程序设计语言）；④用程序框图（流程图）．
4.算法的三种基本逻辑结构：
1）顺序结构：最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的．如下图，只有在执行完A框指定的操作后，才能接着执行B框指定的操作；
2）条件（分支）结构：在一个算法中，用来处理需要根据条件是否成立有不同的流向的结构．
常见的条件结构的程序框图有下面两种形式：

3）循环结构：从某处开始，按照一定的条件反复执行某些步骤的情况，就是循环结构，其中反复执行的步骤称为循环体．
常见的循环结构的框图对应为：
注意事项：
在画程序框图时，从开始框沿箭头必须能到达结束框，特别是条件分支结构应沿每条支路都能到达结束框，流程线必须加箭头表示顺序．
2.对于循环结构有如下需要注意的情况：
1）循环结构非常适合计算机处理，因为计算机的运算速度非常快，执行成千上万次的重复计算，只不过是一瞬间的事，且能保证每次的结果都正确；
2）循环结构要有中止循环体的条件，不能无休止的运算下去，循环结构中一定包含条件结构，如i≤n就是中止循环的条件；
3）循环结构的关键是，要理解“累加变量”和“用i+1代替i”，S是一个累加变量，i 是计数变量，每循环一次，S和i都要发生变化，这两步要重复计算若干次；
4）一种循环结构是先判断i≤n是否成立，若是，执行循环体；若否，则中止循环，像这样，每次执行循环体前对控制循环条件进行判断，条件满足时执行循环体，不满足则停止，称为当型循环．除了当型循环外，常用的循环结构还有直到型循环．
(二)程序框图
程序框图的概念：用一些通用的图形符号构成的一张图来表示算法，称为程序框图（简称框图）．
常用图形符号：
注意事项：
画程序框图的规则：
①使用标准的框图的符号；
②框图一般按从上到下、从左到右的方向画；
③除判断框外，大多数框图符号只有一个进入点和一个退出点．判断框是具有超过一个退出点的惟一符号；
④一种判断框是“是”与“不是”两分支的判断，而且有且仅有两个结果；另一种是多分支判断，有几种不同的结果；
⑤在图形符号内描述的语言要非常简练清楚．
2）画程序框图要注意的几点：
①起、止框是任何流程不可少的，表示程序的开始和结束；
②输入、输出框可以用在算法中任何需要输入、输出的位置；
③算法中间要处理数据或计算，可分别写在不同的处理框内；
④当算法要求你对两个不同的结果进行判断时，要写在判断框内；
⑤一个算法步骤到另一个算法步骤用流程线连结；
⑥如果一个框图需要分开来画，要在断开处画上连结点，并标出连结的号码．
如：用海伦公式求任意三角形的面积的程序框图，其中断开处画上连结点，并标出连结的号码．
(三)算法语句
1.程序语言的基本语句结构：输入语句、输出语句、赋值语句、条件语句、循环语句．
2.赋值语句：表明赋给某一个变量一个具体的确定值的语句．
一般格式：变量名=表达式；其中“=”叫做赋值号．
作用：先计算出赋值号右边表达式的值，然后将它赋给左边的变量，使该变量的值等于表达式的值．
3.输入语句：在每次程序运行时，用于输入相应的初始数据的语句，我们主要介绍键盘输入语句．
Scilab中的输入语句常用的是：“input”；
一般格式：变量名=input（“提示内容”）
例：a=input（“x1”）；b=input（“x2”）；aver=（a+b）/2
表示输入x1，x2的值，求它们的算术平均数，
在Scilab界面内运行结果如下：
-->a=input（"x1"）；b=input（"x2"）；aver=（a+b）/2
x1-->
此时通过键盘输入x1的值，如4，再按“Enter”键，界面出现：
x2-->
输入x2的值，如6，再按“Enter”键，这时界面出现：
aver = 5．
4.输出语句：以某种形式把求解结果输出的语句．
Scilab中有：print，write，frmat，printf，disp等输出语句，主要介绍print语句：
一般格式：print（%i（2），表达式）；其中参数%i（2）表示在屏幕上输出．
5.条件语句：处理条件分支结构的算法语句．
Scilab程序语言中常用的条件语句为if语句．
一般格式：if 表达式
语句序列1；
else
语句序列2；
end
最简格式：if 表达式
语句序列1；
end
6.循环语句：处理算法中的循环结构的语句；
Scilab有两种循环语句：fr循环和while循环．
fr循环的格式：fr 循环变量=初值：步长：终值
循环体；
end
while语句的一般格式：while 表达式（即条件）
循环体；
end
注意事项：
1.计算机能够直接或间接理解的程序语言有很多种，比如C语言，Basic语言，以及一些应用数学软件：Matlab，Mathsmatics，Scilab对应的计算机语言．这里的基本语句结构在这些语言中都是存在的，但是对应不同的程序语言，都会有自己的输入指令与方法．这里是以一种语言为例，让大家理解程序语句的含义，为以后深入学习程序设计打下基础．
2.赋值语句：
1）赋值号左边只能是变量名，而不是表达式；如3=m是错误的；
2）赋值号左右不能对换，是将赋值号右边的表达式的值赋给左边的变量；如x=y表示用y的值替代变量x原先的值，与y=x不同；
3）不能利用赋值语句进行代数式（或符号）的演算；如y=x2−1=(x+1)(x−1)是不能实现的；并且在一个赋值语句中，只能给一个变量赋值；
3）赋值号与数学中的等号的意义不同，执行赋值语句后，右面表达式的值会赋给左边，如果左边变量原来有一个值，会自动被冲掉，如N=N+1表示将N的原值加1再赋给N，即N的值加1．
3.输入语句：在某些算法中，变量的初值要根据情况经常地改变，一般我们把程序与初始数据分开，每次算题时，即使初始数据改变，也不必改变程序部分，只要程序运行时，输入相应的数据即可，这个过程在程序语言中，用“输入语句”来控制．输入语句中还有read输入语句等．
输入语句要求输入的一般都是具体的常数，也可输入单个或多个字符，格式为：变量名=input（“提示内容”，“string”），string表示输入字符型变量．
4.循环语句：
fr语句：先把初值赋给循环变量，记下终值和步长，循环变量增值到超过终值时，执行end后面的语句，不超过时，执行fr后面的语句；循环变量起计数作用，控制算法中循环次数，有初值与终值，步长是指循环变量每次增加的值，步长为1时，可以省略；
while语句：先判断条件是否成立，并在符合条件时，执行循环体；直到某次不符合时，跳到end后面的语句．
对应的基本框图是：
5.在程序语言中，乘、除、乘方、求平方根、绝对值，分别用下列符号表示：*、/、^、sqrt（）、abs（）．程序语言中，一般“＝”为赋值号，“＝＝”表示等号．≥、≤、≠分别写成：>​=、<​=、<​>．在程序中，如果赋值语句后面用分号隔开，则被赋值的变量不会输出，一般不随便使用逗号或句号，而是直接使用回车或空格．
(四)算法案例
1.更相减损术：求两个整数的最大公约数的算法
更相减损术的步骤：
以两个数中较大的数减去较小的数，以差数和较小的数构成一对新的数，对这一对数再用大数减小数，以同样的操作一直做下去，直到产生一对相等的数，此数就是这两个数的最大公约数．
等值算法：用“更相减损术”设计出来的算法求最大公约数的算法称为“等值算法”，用等值算法可以求任意两个正整数的最大公约数．
2.辗转相除法：又称欧几里得算法，是由欧几里得在公元前300年左右首先提出来的求两个数的最大公约数的算法。
辗转相除法的步骤：
对于给定的两个数，以其中较大的数除以较小的数得到一个余数，将较小的数与余数看成一对新的数，重复上面的步骤，直到余数为零为止，此时上一步中较小的数即为所求的最大公约数。
以求117和182的最大公约数为例：
(117​​​，​​​​182)→(117​​​，​​​​65)→(65​​​，​​​​52)→(52​​​，​​​​13)→(13​​​，​​​​0),故13即为所求。
3.秦九韶算法：求多项式的值的算法
具体如下：
对任意一个n元多项式f(x)=anxn+an−1xn−1+⋯+a1x+a0，
改写成如下形式：f(x)=(anxn−1+an−1xn−2+⋯+a1)x+a0
=((anxn−2+an−1xn−3+⋯+a2)x+a1)x+a0
=⋯=(⋯((anx+an−1)x+an−2)x+⋯+a1)x+a0，
求多项式的值时，先计算最内层括号内的一次多项式的值，即v1=anx+an−1，
然后由内向外逐层计算一次多项式的值，即v2=v1x+an−2，v3=v2x+an−3，⋯，vn=vn−1x+a0．
这样，求一个n次多项式的值，就转化为求n个一次多项式的值．
令vk=(⋯(anx+an−1)x+⋯+an−(k−1))x+an−k，则递推公式为&v0=an&vk=vk−1x+an−k，其中k=1​​​，​​​​2​​​，​​​​⋯​​​，​​​​n．
到目前为止，此算法仍然是世界上多项式求值的最先进的算法．
秦九韶算法与其它算法在计算量上面的比较：f(x)=anxn+an−1xn−1+⋯+a1x+a0，
1）直接求和法：先计算各个单项式的值，再把它们相加，乘法次数为n+(n−1)+⋯+2+1=n(n+1)2，加法次数n；
2）逐项求和法：先计算x的各项幂的值，再分别相乘，计算幂值需要乘法n−1次，将幂值与多项式系数ak相乘需要乘法n次，故共需要乘法2n−1次，加法n次．此方法对直接求和法有所改进，但仍然比秦九韶算法计算量大很多．
3）秦九韶算法：计算量仅为乘法n次，加法n次．
典例精讲
1．阅读如图所示的程序框图，运行相应的程序，若输出的S为1112，则判断框中填写的内容可以是（ ）
A．n＜5B．n＜6C．n≤6D．n＜9
2．执行如图所示的程序框图，若输出的S＝1022，则判断框内应填入的条件是（ ）
A．n＞7？B．n＞8？C．n＞9？D．n＞10？
3．我国古代数学典籍《九章算术》第七章“盈不足”中有一问题：“今有蒲生一日，长三尺，莞生一日，长一尺．蒲生日自半．莞生日自倍．问几何日而长等？”（蒲常指一种多年生草本植物，莞指水葱一类的植物）现欲知几日后，莞高超过蒲高一倍．为了解决这个新问题，设计如图所示的程序框图，输入A＝3，a＝1．那么在①处应填_______和输出i的值为（ ）
A．S＞2T？4B．S＜2T？4C．T＞2S？3D．T＜2S？3
4．中国古代数学著作《孙子算经》中有这样一道算术题：“今有物不知其数，三三数之余二，五五数之余三，问物几何？”人们把此类题目称为“中国剩余定理”，若正整数除以正整数后的余数为，则记为，例如．现将该问题以程序框图的算法给出，执行该程序框图，则输出的等于
A．39B．38C．37D．36
5．阅读程序框图，运行相应的程序，则输出的值为 ．
6．如图所示的一个算法的程序框图，则输出的最大值为
A．B．2C．D．
综合练习
一．选择题（共4小题）
1．定义：如果一条直线同时与n个圆相切，则称这条直线为这n个圆的公切线．已知有2018个圆∁n：（x﹣an）2+（y﹣bn）2＝rn2（n＝1，2，3，…，2018），其中an，bn，rn的值由以下程序给出，则这2018个圆的公切线条数（ ）
A．没有公切线B．只有一条C．恰好有两条D．有超过两条
2．执行如图所示的程序框图，输出S的值等于（ ）
A．−23tanπ9−21B．tan25π9−3tanπ9−22
C．−23tanπ9−22D．tan25π9−3tanπ9−21
3．已知某算法的程序框图如图所示，则该算法的功能是（ ）
A．求首项为1，公差为2 的等差数列前2017项和
B．求首项为1，公差为2 的等差数列前2018项和
C．求首项为1，公差为4 的等差数列前1009项和
D．求首项为1，公差为4 的等差数列前1010项和
4．定义运算a⊗b为执行如图所示的程序框图输出的S值，则式子(tanπ4)⊗(cs2π3)的值是（ ）
A．﹣1B．12C．1D．32
二．填空题（共2小题）
5．将“杨辉三角”中的数从左到右、从上到下排成一数列：1，1，1，1，2，1，1，3，3，1，1，4，6，4，1，…，如图所示程序框图用来输出此数列的前若干项并求其和，若输入m＝4则相应最后的输出S的值是 ．
6．若运行如图所示的程序框图，输出的n的值为127，则输入的正整数n的所有可能取值的个数为
图形符号
名称
符号表示的意义
起、止框
框图的开始或结束
输入、输出框
数据的输入或者结果的输出
处理框
赋值、执行计算语句、结果的传送
判断框
根据给定条件判断
流程线
流程进行的方向
连结点
连结另一页或另一部分的框图