聚焦高考中的算法

算法初步，可以概括为一种思想、三种结构、五种语句及三个案例.具体而言，一种思想就是程序化的思想；三种结构就是顺序结构、条件结构和循环结构；五种语句就是输入语句、输出语句、赋值语句、条件语句和循环语句；三个案例就是辗转相除法与更相减损术、秦九韶算法以及进位制.

考点1 算法思想

算法实际上就是解决某一类问题的程序化方法，它通常以一系列明确有限的步骤的形式出现.算法的基本特征程序性、明确性和有限性.高中阶段，学习算法，主要在于体会算法思想. 高考对算法思想的考查往往结合程序框图、算法语句、算法案例或其他有关内容进行.

例1 （2014年湖北卷理13）设[a]是一个各位数字都不是0且没有重复数字的三位数.将组成[a]的3个数字按从小到大排成的三位数记为[I（a）]，按从大到小排成的三位数记为[D（a）]（例如[a=815]，则[I（a）=158]，[D（a）=851]）. 阅读如图所示的程序框图，运行相应的程序，任意输入一个[a]，输出的结果[b=] .

解析 输入[a=815]，按照程序框图，运行相应的程序即可.

当[a=815]时，则[b=851-158=693≠815]，从而进入循环，[a=693].

当[a=693]时，则[b=963-369=594≠693]，从而继续循环，[a=594].

当[a=594]时，则[b=945-459=495≠594]，从而继续循环，[a=495].

当[a=495]时，则[b=945-459=495=a]，从而终止循环，故输出[b=495].

点拨 本题是一道开放性试题，输入的[a]任意的，但输出的[b]是确定的.既然输入的[a]是任意的，我们不妨选择题设所给的例子[a=815]，按照程序框图，运行相应的程序即可得到[b=495].还可以选择[a=123]等. 本题的背景是“数字黑洞”问题，意蕴深厚，充满着数学的奇异美和统一美. 类似地，四位数的数字黑洞是6174.

考点2 程序框图

程序框图的题型主要有三类：计算输出结果、补充程序框图、计算输入数值.因为循环结构程序框图中必然包含顺序结构和条件结构，所以循环结构是考查的重点和热点.处理循环结构的程序框图时，循环次数容易出错，要特别注意程序终止的条件，即何时退出循环.必要时可以从开始和结尾处检验算法是否正确.循环结构中往往出现多个变量，在执行算法框图时，必须严格按照流程线箭头的方向来执行算法步骤，千万不要将循环体中算法的先后次序搞错.

例2 （2014年湖北卷文14）阅读如图所示的程序框图，运行相应的程序，若输入[n]的值为9，则输出[S]的值为 .

解析 第一次运行时，

[S=0+21+1=21+1]，[k=1+1].

第二次运行时，

[S=（21+1）+（22+2）]，[k=2+1].

……

所以框图运算的是

[S=（21+1）+（22+2）+…+（29+9）=1067].

点拨 程序框图含有循环结构且循环次数比较多时，不要盲目地重复运算，否则运算量会较大甚至会算不出来.可以先循环几次，再找出规律，规律往往涉及数列求和.这样，理解了循环结构的含义，往往会简化计算，起到事半功倍的效果.

考点3 算法语句

了解几种基本算法语句――输入语句、输出语句、赋值语句、条件语句、循环语句的含义.其中容易出错的是赋值语句.赋值语句的一般格式：变量=表达式.顾名思义，赋值语句就是将表达式所代表的值赋给变量.赋值语句中的“=”称作赋值号.执行赋值语句时，先计算“=”右边表达式的值，然后把这个值赋给“=”左边的变量.赋值号的左右两边不能对换，如“[A=B]”“[B=A]”的含义运行结果是不同的.

例3 （2013年陕西卷文4理3）根据下列算法语句，当输入[x]为60时，输出[y]的值为（ ）

[输入[x]：

IF [x

[y=0.5?x]

ELSE

[y=25+0.6?（x-50）]

END IF

输出[y]]

A. 25 B. 30

C. 31 D. 61

解析 当[x=60]时，[y=25+0.6（60-50）][=31].

答案 C

点拨 本题实际上是一个分段函数求值问题.分段函数问题可以通过条件语句来实现.

考点4 算法案例

辗转相除法与更相减损术都是求两个正整数的最大公约数的方法. 二者的算理却是相似的，有异曲同工之妙.主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，但实质都是一个不断递归的过程.

秦九韶算法是求一元多项式值的一种方法. 秦九韶算法的特点在于把求一个[n]次多项式的值转化为求[n]个一次多项式的值. 通过这种转化，把运算的次数由至多[n（n+1）2]次乘法运算和[n]次加法运算，减少为至多[n]次乘法运算和[n]次加法运算，大大提高了运算效率.

例4 已知[n]次多项式[Pn（x）=anxn+an-1xn-1+][…+a1x+a0].如果在一种算法中，计算[xk0]（[k=2，3，4，…，n]）的值需要[k-1]次乘法，计算[P3（x0）]的值共需要9次运算（6次乘法，3次加法），那么计算[Pn（x0）]的值共需要 次运算.

下面给出一种减少运算次数的算法：[P0（x）=a0]，[Pk+1（x）=xPk（x）+ak+1]（[k=0，1，2，…，n-1]）.利用该算法，计算[P3（x0）]的值共需要6次运算，计算[Pn（x0）]的值共需要 次运算.

解析 第一种算法中，计算[Pn（x0）]的值共需要[n（n+1）2]次乘法运算和[n]次加法运算，故总运算次数为[n（n+3）2].第二种算法中，计算[Pn（x0）]的值共需要[n]次乘法运算和[n]次加法运算，故总运算次数为[2n].

点拨 第一种算法为直接算法，其优点是简单、易懂，缺点是运算次数太多，运算效率不高.第二种算法是秦九韶算法，其特点是把求一个[n]次多项式的值转化为求[n]个一次多项式的值，避免了对自变量[x]单独作幂的运算，而与系数一起逐步增长幂次，从而减少运算次数，提高运算效率.