2018年高考数学总复习 算法初步

第十一章 算法初步

本章知识结构图 算法的特征 算 法 程序性、明确性、有限性、普适性、不唯一性 顺序结构输入语句输出语句 语程序框图条件（分支）结构基本算 赋值语句 言法语句 循环结构条件语句 算法案例辗转相除法、更相减损术、陈九韶算法、进位制循环语句 考纲解读

1. 了解算法的含义和思想.

2. 理解程序框图的3中基本逻辑结构：顺序、条件分支、循环.

3. 理解5种基本算法语句——输入、输出、赋值、条件和循环语句的含义. 命题趋势探究

预测在2019年高考中，本章知识仍为考查的热点，内容以程序框图为主.从形式上看，以选择题和填空题为主，或以实际问题为背景，侧重知识应用能力的考查，要求考生具备一定的逻辑推理能力.

本专题主要考察算法的逻辑结构，要求能够写出程序的运行结果、指明算法的功能、补充程序框图，求输入参量，并常将算法与其他板块知识（尤其是数列）进行综合考查.一般来说，有关算法的试题属中档题目，分值稳定在5分. 知识点精讲 一、 算法与程序框图

1.算法 算法通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是确定的和能执行的，并且能够在有限步之内完成．

2. 程序框图

(1)定义：程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形． （2）说明：在程序框图中，一个或几个程序框的组合表示算法中的一个步骤；带有方向的流程线将程序框连接起来，表示算法步骤的执行顺序．

3．3种基本逻辑结构 程序框图有3种基本的逻辑结构，如表11-1所示.

表11-1 名称 内容 顺序结构 顺序结构是由若定义 顺序结构由若干个依次执行的步骤组成的，是任何条件结构 算法的流程根据条件是否成立有不同的流向，条件结构就是处理这种过程的结构 循环结构 从某处开始，按照一定的条件反复执行某些步骤．反复执行的步骤称为循环体． 一个算法都离不开的基本结构 步骤n 程序框图 步骤n+1 满足条件？ 是 步骤A 步骤B 否 二、基本算法语句

1.3中基本算法语句的一般格式和功能

3中基本算法语句的一般格式和功能如表11-2所示.

表11-2 语句 输入语句 输出语句 赋值语句 2.条件语句

(1)算法中的条件结构由条件语句来表达． (2)条件语句的格式及框图如图11-1和11-2所示. ①IF—THEN格式 IF 条件 THEN 语句体 END

②IF—THEN—ELSE格式 IF 条件 THEN 语句体1 ELSE 语句体2

END

图11-2

满足条件？ 是 语句体1 语句体2 否 图11-1 否 满足条件？ 是 语句体 一般格式 INPUT“提示内容”；变量 PRINT“提示内容”；表达式 变量＝表达式 功能 输入信息 输出结果 将表达式的值赋给变量 3．循环语句

(1)算法中的循环结构是由循环语句来实现． (2)循环语句的格式及框图如图11-3和11-4所示． ①UNTIL语句

DO

循环体

LOOP UNTIL条件

②WHILE语句 WHILE 条件

循环体

END

图11-3

图11-4

（3）WHILE语句与UNTIL语句之间的区别与联系如表11-3所示.

表11-3 WHILE语句 执行循环体前测试条件，当条件为真区别 时执行循环体，当条件为假时终止循环，可能不执行循环体 UNTIL语句 执行循环体后测试语句条件，当条件为假时执行循环体，当条件为真时终止循环，最少执行一次循环体 联系 可以相互转换，LOOP UNTIL(条件)相当于WHILE（反条件） 三、算法案例 1.辗转相除法

辗转相除法又叫欧几里德算法，是一种求最大公约数的古老而有效的算法，其步骤如下： (1)用两数中较大的数除以较小的数，求得商和余数； (2)以除数和余数中较大的数除以较小的数； (3)重复上述两步，直到余数为0； (4)较小的数是两数的最大公约数. 2.更相减损术

更相减损术是我国古代数学专著《九章算术》中介绍的一种求两数最大公约数的算法，其基本过程为：对于任意给定的两个正整数，以大数减小数，接着把所得的差与较小的数比较，并以大数减小数，继续该操作，直到所得的数相等为止，这个数(等数)就是所求的最大

公约数.

3.秦九韶算法

秦九韶算法是我国南宋数学家秦九韶在他的代表作《数书九章》中提出的一种用于计算一元n次多项式的值的方法。

4.进位制

进位制是人们为了计数和运算方便而约定的记数系统，“满k进1”就是k进制，k进制的基数是k.

题型归纳及思路提示

根据考纲要求并结合高考中常见题型，程序框图主要用于数列、分段函数、大小比较等程序性问题的解决．要求考生能读懂程序框图，理解所执行的程序．题型155-160是针对程序框图中所解决的问题来分类，但从算法角度讲没有本质区别，因而解决它们的思路是一致的，具体是：

(1)先通过程序框图宏观分析是解决什么样的(数学)问题，并明确该问题解决的具体思路步骤；

(2)将该问题的解决思路步骤与程序框图所执行的程序比较； (3)根据题目要求做答(可能是求输出结果或输入参量， 也可能是填充判断框).

开始 题型155 程序框图中的数列求和问题

思路提示

循环体是所求和的表达式，也是反复执行的步骤，需按变量取值依次进行.

例11.1如果执行如图11-5所示的框图，输入N=5，则输出的数等于( )

S?S?输入N k?1,S?01k(k?1) k?k?1是 5465A. B. C. D.

5645解析 解法一：将程序框图所执行的程序分步进行计算， 如表11-4所示.

表11-4 步骤 k

是 否 5．故选D. 65111??解法二：本题实质上是求解?，故S?0?1?22?3k(k?1)k?1111115?1??????? ．故选D.

223566根据表11-4的模拟分析，程序输出的数为

?1 5?6评注 解决这类算法问题时，一般有两种思路：一是把人看作计算机，程序执行哪一步，我们就计算哪一步，一直到程序终止，这类方法往往适用于步骤比较简单，循环次数不十分多的程序；二是原理分析法，即分析程序的原理，了解程序实质要完成的目标，将其还原为数学模型，从而对数学模型进行求解.本题的解法一与解法二就分别应用了这两种思路. 变式1 如图11-6所示是一个算法的流程图，则输出S的值是_______

开始 S?1 n?1 S?S?2 nS?33?是 输出S

变式2 如图11-7所示的程序框图，输出的S是126， 则①应为( ).

A.n≤5？ B.n≤6？ C.n≤7？ D.n≤8？

n?n?1 否 结束 开始 图11-6

n?1,S?0 ① 否 是 S?S?2n n?n?1 输出S PP 结束题型156 程序框图中的分段函数求值的问题

思路提示

图11-7

本类问题是对变量不同的范围有不同的表达式.对于输入的x的值应根据条件语句所确定的x的取值范围选择相应的解析式代入求值.

例11.2 阅读如图11-8所示的程序框图，运行相应的程序， 当输入x的值为-25时，输出x的值为( ).

A.-1 B.1 C.3 D.9

分析 首先应理解该程序框图的实质是完成一个分段函数求值的问题，即已知

?|x|?1,|x|?1?f(x)??,求f{f[f(?25)]}的值.

??2x?1,|x|?1解析 该程序的模拟分析如表11-5所示：

表11-5 步骤 开始 输入x P|x|?1?否 |x|?1？ x?|x|?1 4 1 x?2x?1 是 x?|x|?1 3 第1次 是 第2次 是 第3次 否 x?2x?1 输出当输入x??25时，前两次执行x?|x|?1 ，第3次执行x 的.如果法的程

x?2x?1，故输出的x?3．故选C.

评注 事实上每个程序框图都是为了解决某个(数学)问题而编写读者对待每个程序框图都能理解它是真正反映一个(数学)问题算P结束 图11-8 序，而不是生硬、机械地执行，这样既有利于解题又能切实理解算法的本质内涵.

?log2x,x?2变式 1 已知函数y?? ，如图11-9所示，表示的是给定x的值，求其对应

2?x,x?2?的函数值y的程序框图.①处应填写______；②处应填写______.

变式 2 执行如图11-10所示的程序框图，若输入x?10，则输出y的值为______.

输出开始 开始 输入x 输入x PP① 否 是 P1y?x?1 2②x?y 否 y?2?x |y?x|?1? 输出

y 是 PP 结束y P结束 图11-9 图11-10

题型157 程序框图中的概率统计问题

思路提示

计算机模拟产生随机数是计算概率的一种重要的方法.统计中数字特征计算如均值、方差等这些问题通过程序框图处理.

例11.3 如图11-11所示是用模拟方法估计圆周率 π值的程序框图，P表示估计结果， 则图中空白框应填入( ).

开始 M?0,N?0,i?1 产生0—1之间的两个随机数分别赋值x1,y1 否 N4N B. P? 10001000M4MC. P? D. P?

10001000A. P?分析 采用几何概型解决本题.

解析 由程序框图可知，M表示落在单位圆 在第一象限内的点的个数，N表示落在圆 外的点的个数.如图11-12所示，正方形 x2?y2?1?是 M?M?1 i?i?1 否 N?N?1 OABC中有1000个点，其中阴影部分内点 的个数为N，其余点(个数为M)落在扇形 i?1000?是 输出P OAC中，由圆的面积公式可知扇形OAC的面积为 S?

?4?M4M4M,即??，所以P?.故选D. 100010001000PP结束 变式1 在可行域内任取一点，规则如图11-13所示(即程输出数对(x,y)的概率为( ). A.

.

图11-11 yCB序框图)，则能

1??? B. C . D. 4248OA图11-12x

开始 开始 输入可行域 ???2?x?y?2 ????2?x?y?2 在可行域内任取有序数对(x,y) 输入n,a1,a2,,an s?0,i?1

i?i?1 是 s?(i?1)?s?ai ix?y?1?是 输出数对(x,22否 i?n?x?y?1?否 y) 输出s 结束

结束 图11-14

图11-13

变式2：随机抽取某产品n件，测得其长度分别为a1,a2,,an，则图11-14所示的程序框图

输出的s? ，s表示的样本的数字特征是 ．

变式3：如果执行如图11-15所示的程序框图，输入正整数n，m，满足n?m，那么输出的p等于

m?1m?1mmA. Cn B. An C. Cn D. An

图 11-15

题型158 程序框图中数的比较大小问题

思路提示

数的大小排序在程序框图中要注意的是“赋值号=”的含义，它不是数学中的符号，而是表明将右边的数赋给左边的数，这是解决这类题型的关键所在，即对数进行位置的变换。 例11.4如果执行如图11-16所示的程序框图，输入正整数N(N≥2)和实数a1，…，a2，aN，输出A，B，则

A.A+B为a1，a2，…，aN的和

A?B为a1，a2，…，aN的算术平均数 2C.A和B分别为a1，a2，…，aN中的最大数和最小数

B.

D.A和B分别为a1，a2，…，aN中的最小数和最大数

图11-16

解析 结合程序框图可知，x?A时，有A?x，即A表示a1，a2，…，aN中最大的数；同理，B表示a1，a2，…，aN中最小的数，故选C

变式1 如图11-17所示，右图中，x1，x2，x3为某次考试三个评阅人对同一道题的独立评分，P为该题的最终得分。当x1?6,x2?9.p=8.5时，x3等于

A．11 B．10 C．8 D．7

图11-17

题型159 程序框图在解决其他问题中的应用 思路提示

对于一些问题，我们可以根据它的要求编写程序框图，这里要注意其中判断框与循环体之间的关系.

例11.5 如图11-18所示，流程框图（算法流程图）的输出值x= .

开开x=1开x开开开开开开x=x+1x=x+2开x > 8开开开开x开开

图 11-18

解析 程序框图模拟分析，如表11-6所示.

表11-6 步骤 第1次 第2次 第3次 第4次 第5次 x是奇数 是 否 是 否 是 否 x 2 4 5 6 8 9 10 12 x>8? 否 否 是 根据表11-6的模拟分析，程序输出的x值为12.

变式1 (1)执行如图11-19所示的程序框图，若输出的n为4，则输入P的取值范围为（ ）. A. (0.75, 0.875) B. (0.75, 0.875] C. [0.75, 0.875) D. [0.75, 0.875]

(2) 执行如图11-19所示的程序框图，若输出的n为4，则输入P可能为（ ）. A. 0.7 B. 0.75 C. 0.8 D. 0.9

(3) 执行如图11-19所示的程序框图，若P=0.8，则输出n= .

开开开开Pn=1,S=0S

变式2 根据图11-20所示的程序框图，将输出的x,y值依次记为x1，x2，…，xn，…，x2014；y1，y2，…，yn，…，y2014.

(1) 求数列{ xn }的通项公式；(2)写出y1，y2，y3，y4，由此猜想出{ yn }的一个通项公式yn，并证明你的结论；(3)求zn?x1y1?x2y2?????xnyn(n?N*,n?2014).

开开x=1开y=2开n=1开开x, yn=n+1x=x+2y=3y+2n <2014开开开开开

图11-20

题型160 算法案例

思路提示

按照秦九韶算法计算多项式值是转化为一次式值反复计算，这体现了将高次多项式值转化为一次式值得计算.

例11.6 用秦九韶算法求多项式f(x)?5x5?4x4?3x2 ?2x?1，当x?2时的值. 解析f(x)?5x5?4x4?3x2?2x?1?5x5?4x4?0

x3?3x2?2x?1?((((5x?4)x?0)x?3)x?2)x

?1,v1?14;v2?28;v3?59;v4?120;v5?241，所以当x?2时，多项式的值为241，即f(2)?241.

评注 秦九韶算法的原理就是通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可.

nn?1(1) 计算步骤如下：设P?????a1x?a0将其改写为n(x)?anx?an?1xn?2n?3n?1n?2?a)x?a?((ax?ax?????a2)x?a1)xP(x)?(ax?ax????10nn?1nnn?1?a0????????(???((anx?an?1)x?an?2)x?????a1)x?a0.

第一步：计算最内层anx?an?1的值，将anx?an?1的值赋给一个变量v1（先把an赋给变量

； v0）

第二步：计算v1x?an?2的值，将v1x?an?2的值赋给一个变量v2； 依此类推，第n步：求得的值vn?vn?1x?a0就是欲求多项式的值.

(2)程序框图如图11-21所示.

开开开开Pn(x)开开开开a0,a1,a2,…,an开开x开开x0i=1v=ani=i+1v=v-x0+an-ii ≤ n开开开开v开开开

图11-21

764变式1用秦九韶算法求多项式f(x)?8x?5x?3x? 2x?1，当x?3 时的值的时候，

第二步计算的结果为 .

变式2 (1)把十进制数21转化为二进制数；(2)将八进制数31072(8)转化为十进制数

最有效训练题48（限时45分钟）

1. 执行如图11-22所示的程序框图，输出的S值为（ ）. A. 2 B. 4 C. 8 D. 16

2. 执行如图11-23所示的程序框图，若输入x=2，则输出的y的值为（ ）. A. 2 B. 5 C. 11 D. 23 3. 如图11-24所示给出的是计算入的条件是（ ）.

A. i<50? B. i >50? C. i<25? D. i >25?

4. 执行如图11-25所示的程序框图，输出S的值为（ ）. A.3 B. ? 6 C. 10 D. ?15

1111??????? 的一个程序框图.其中判断框内应填246100开开开开k=0,S=1开开xk=k+1y=2x+1S=S×2kk < 3开开开开S开开x=y开|x-y| > 8开开开开x开

开开 图11-22 图11-23

开开开开S=0,n=2,i=1开开开i=1,S=0i<5开开开开i开开开开S?S?1n开开S开开S=S-i2i=i+1S=S+i2n=n+2开开Si=i+1

5. 执行如图11-26所示的程序框图，输出S的值为( ). A. 1 B. -1 C. -2 D. 0

6. 执行如图11-27所示的程序框图，输出S的值为( ). A. -1 B.

开开

图11-24 图11-25

23 C. D. 4 32

开开开始S=4,i=1T=0,S=1S=S-Ti < 9？是否T=T+ST ≥0开开开开S开开开S?22?Si=i+1输出S

结束

图11-26 图11-27

7. 若某程序框图如图11-28所示，则该程序运行后输出k的值是 . 8. 执行如图11-29所示的程序框图，输入x??1,n?3，则输出的数S= .

开开开开开开x,nk=2k=k+1a=4kb=k4a > b开开开开k开开开S=6i=n-1i=i-1S=S·x+i+i ≥ 0开开开开开1S

开开 图11-28 图11-29

9. 阅读如图11-30所示的程序框图，运行相应的程序，输出的结果是S= . 10. 执行如图11-31所示的程序框图，若输入的n值为8，则输出S的值为 .

开开开开n开开i=2,k=1,S=1开a=1,S=0,n=1i < n开开1?S?i?kS=S+aa=a+2n < 3开开开S?i=i+2k=k+1n=n+1开开S开开开开S开开

图11-30 图11-31

11. 如图11-32所示是一个计算机装置示意图，J1，J2是数据入口处，C是计算机结果的出口，计算机过程是由J1，J2分别输入自然数m和n，经过计算机处理后将所得自然数由C输出，此种计算装置完成的计算机满足以下3个性质： 1若J1，J2分别输入1，则输出结果为1； ○

2若J1输入任何固定自然数m不变，J2输入自然数n增大1，则输出结果比原来大2； ○

3若J2输入1，J1输入自然数m增大1，则输出结果为原来的2倍. ○

试问：

(1)若J1输入1，J2输入自然数n，输出结果为多少？ (2)若J2输入1，J1输入自然数m，输出结果为多少？

mJ1nJ2C

图11-32

12. 甲、乙两同学进行下棋比赛，约定每局胜者得1分，负者得0分（无平局），比赛进行到了一个人比对方多2分或满8局时停止.设甲在每局比赛中获胜的概率为p?p?各局比赛胜负相互独立.已知第二局比赛结束时比赛停止的概率为

??1?且? ，2?5. 8(1)如图11-33所示为统计这次比赛的局数n和甲、乙的总分S，T的程序框图.其中如何甲获

1，○2两个判断框中应分别填写胜，输入a=1，b=0；如果乙获胜，则输入a=0，b=1.请问在○

什么条件？ (2)求p的值；

(3)设ξ表示比赛停止时已比赛的局数，求随机变量ξ的分布列及Eξ.

开开n=0,S=0,T=0开开a,bS=S+a,T=T+bM=|S-T|n=n+1开1开开开n,S,T开开开2开

图11-33

本文来源：https://www.bwwdw.com/article/qusx.html