算法初步知识点及题型归纳

算法初步知识点及题型归纳知识点精讲一、算法与程序框图1.算法算法通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是确定的和能执行的，并且能够在有限步之内完成．2.程序框图(1)定义：程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形．（2）说明：在程序框图中，一个或几个程序框的组合表示算法中的一个步骤；带有方向的流程线将程序框连接起来，表示算法步骤的执行顺序．3．3种基本逻辑结构程序框图有3种基本的逻辑结构，如表11-1所示.表11-1名称内容顺序结构条件结构循环结构定义顺序结构是由若顺序结构由若干个依次执行的步骤组成的，是任何一个算法都离不开的基本结构算法的流程根据条件是否成立有不同的流向，条件结构就是处理这种过程的结构从某处开始，按照一定的条件反复执行某些步骤．反复执行的步骤称为循环体．程序框图二、基本算法语句1.3中基本算法语句的一般格式和功能3中基本算法语句的一般格式和功能如表11-2所示.表11-2语句一般格式功能输入语句INPUT“提示内容”；变量输入信息输出语句PRINT“提示内容”；表达式输出结果赋值语句变量＝表达式将表达式的值赋给变量2.条件语句(1)算法中的条件结构由条件语句来表达．(2)条件语句的格式及框图如图11-1和11-2所示.步骤n+1步骤n否是满足条件？步骤B步骤A①IF—THEN格式IF条件THEN语句体END②IF—THEN—ELSE格式IF条件THEN语句体1ELSE语句体2END3．循环语句(1)算法中的循环结构是由循环语句来实现．(2)循环语句的格式及框图如图11-3和11-4所示．①UNTIL语句DO循环体LOOPUNTIL条件②WHILE语句WHILE条件循环体END（3）WHILE语句与UNTIL语句之间的区别与联系如表11-3所示.表11-3WHILE语句UNTIL语句区别执行循环体前测试条件，当条件为真执行循环体后测试语句条件，当条件为假时图11-3图11-4是满足条件？语句体否图11-1是否满足条件？语句体2语句体1图11-2是否开始开始1,0kS1(1)SSkk1kkkN?输出SPPPRUP输入N结束开始图11-5时执行循环体，当条件为假时终止循环，可能不执行循环体执行循环体，当条件为真时终止循环，最少执行一次循环体联系可以相互转换，LOOPUNTIL(条件)相当于WHILE（反条件）三、算法案例1.辗转相除法辗转相除法又叫欧几里德算法，是一种求最大公约数的古老而有效的算法，其步骤如下：(1)用两数中较大的数除以较小的数，求得商和余数；(2)以除数和余数中较大的数除以较小的数；(3)重复上述两步，直到余数为0；(4)较小的数是两数的最大公约数.2.更相减损术更相减损术是我国古代数学专著《九章算术》中介绍的一种求两数最大公约数的算法，其基本过程为：对于任意给定的两个正整数，以大数减小数，接着把所得的差与较小的数比较，并以大数减小数，继续该操作，直到所得的数相等为止，这个数(等数)就是所求的最大公约数.3.秦九韶算法秦九韶算法是我国南宋数学家秦九韶在他的代表作《数书九章》中提出的一种用于计算一元n次多项式的值的方法。4.进位制进位制是人们为了计数和运算方便而约定的记数系统，“满k进1”就是k进制，k进制的基数是k.题型归纳及思路提示根据考纲要求并结合高考中常见题型，程序框图主要用于数列、分段函数、大小比较等程序性问题的解决．要求考生能读懂程序框图，理解所执行的程序．题型155-160是针对程序框图中所解决的问题来分类，但从算法角度讲没有本质区别，因而解决它们的思路是一致的，具体是：(1)先通过程序框图宏观分析是解决什么样的(数学)问题，并明确该问题解决的具体思路步骤；(2)将该问题的解决思路步骤与程序框图所执行的程序比较；(3)根据题目要求做答(可能是求输出结果或输入参量，也可能是填充判断框).题型1程序框图中的数列求和问题思路提示循环体是所求和的表达式，也是反复执行的步骤，需按变量取值依次进行.例11.1如果执行如图11-5所示的框图，输入N=5，则输出的数等于()A.54B.45C.65D.56解析解法一：将程序框图所执行的程序分步进行计算，如表11-4所示.表11-4否开始1S1n2nSS1nn33?S结束输出S是图11-6否开始1,0nS1nn输出SPPPRUP是结束图11-7①2nSS步骤kSkN?第1次112是第2次223是第3次334是第4次445是第5次556否根据表11-4的模拟分析，程序输出的数为56．故选D.解法二：本题实质上是求解511(1)kkk，故1110122356S1111151223566．故选D.评注解决这类算法问题时，一般有两种思路：一是把人看作计算机，程序执行哪一步，我们就计算哪一步，一直到程序终止，这类方法往往适用于步骤比较简单，循环次数不十分多的程序；二是原理分析法，即分析程序的原理，了解程序实质要完成的目标，将其还原为数学模型，从而对数学模型进行求解.本题的解法一与解法二就分别应用了这两种思路.变式1如图11-6所示是一个算法的流程图，则输出S的值是_______变式2如图11-7所示的程序框图，输出的S是126，则①应为().A.n≤5？B.n≤6？C.n≤7？D.n≤8？题型2程序框图中的分段函数求值的问题思路提示否是开始开始输出xPPPRUP输入xPPPRUP||1?x||1xx21xx结束图11-8否是开始开始输出yPPPRUP输入xPPPRUP①2yx②结束图11-9yx是否开始开始输出yPPPRUP输入xPPPRUP||1?yx112yx结束图11-10本类问题是对变量不同的范围有不同的表达式.对于输入的x的值应根据条件语句所确定的x的取值范围选择相应的解析式代入求值.例11.2阅读如图11-8所示的程序框图，运行相应的程序，当输入x的值为-25时，输出x的值为().A.-1B.1C.3D.9分析首先应理解该程序框图的实质是完成一个分段函数求值的问题，即已知||1,||1()21,||1xxfxxx,求{[(25)]}fff的值.解析该程序的模拟分析如表11-5所示：表11-5步骤||1x？||1xx21xx第1次是4第2次是1第3次否3当输入25x时，前两次执行||1xx，第3次执行21xx，故输出的3x．故选C.评注事实上每个程序框图都是为了解决某个(数学)问题而编写的.如果读者对待每个程序框图都能理解它是真正反映一个(数学)问题算法的程序，而不是生硬、机械地执行，这样既有利于解题又能切实理解算法的本质内涵.变式1已知函数2log,22,2xxyxx，如图11-9所示，表示的是给定x的值，求其对应的函数值y的程序框图.①处应填写______；②处应填写______.变式2执行如图11-10所示的程序框图，若输入10x，则输出y的值为______.是否是开始输出PPPPRUP221?xy1MM结束图11-110,0,1MNi产生0—1之间的两个随机数分别赋值11,xy1ii1NN?1000i否图11-12yxOCBA题型3程序框图中的概率统计问题思路提示计算机模拟产生随机数是计算概率的一种重要的方法.统计中数字特征计算如均值、方差等这些问题通过程序框图处理.例11.3如图11-11所示是用模拟方法估计圆周率π值的程序框图，P表示估计结果，则图中空白框应填入().A.1000NPB.41000NPC.1000MPD.41000MP分析采用几何概型解决本题.解析由程序框图可知，M表示落在单位圆在第一象限内的点的个数，N表示落在圆外的点的个数.如图11-12所示，正方形OABC中有1000个点，其中阴影部分内点的个数为N，其余点(个数为M)落在扇形OAC中，由圆的面积公式可知扇形OAC的面积为41000MS,即41000M，所以41000MP.故选D.变式1在可行域内任取一点，规则如图11-13所示(即程序框图)，则能输出数对(,)xy的概率为().A.14B.2C.4D.8.否是开始开始输出s输入12,,,,nnaaa?in221?xy0,1si结束图11-141ii(1)iisasi否是开始开始输出数对(,)xy输入可行域2222xyxy221?xy在可行域内任取有序数对(,)xy结束图11-13变式2：随机抽取某产品n件，测得其长度分别为12,,,naaa，则图11-14所示的程序框图输出的s，s表示的样本的数字特征是．变式3：如果执行如图11-15所示的程序框图，输入正整数n，m，满足nm，那么输出的p等于A.1mnCB.1mnAC.mnCD.mnA图11-15题型4程序框图中数的比较大小问题思路提示数的大小排序在程序框图中要注意的是“赋值号=”的含义，它不是数学中的符号，而是表明将右边的数赋给左边的数，这是解决这类题型的关键所在，即对数进行位置的变换。例11.4如果执行如图11-16所示的程序框图，输入正整数N(N≥2)和实数1a，2a，…，Na，输出A，B，则A.A+B为1a，2a，…，Na的和B.2AB为1a，2a，…，Na的算术平均数C.A和B分别为1a，2a，…，Na中的最大数和最小数D.A和B分别为1a，2a，…，Na中的最小数和最大数图11-16解析结合程序框图可知，xA时，有Ax，即A表示1a，2a，…，Na中最大的数；同理，B表示1a，2a，…，Na中最小的数，故选C变式1如图11-17所示，右图中，1x，2x，3x为某次考试三个评阅人对同一道题的独立评分，P为该题的最终得分。当126,9.xxp=8.5时，3x等于A．11B．10C．8D．7图11-17题型159程序框图在解决其他问题中的应用思路提示对于一些问题，我们可以根据它的要求编写程序框图，这里要注意其中判断框与循环体之间的关系.例11.5如图11-18所示，流程框图（算法流程图）的输出值x=.开开x=1x开开开开x=x+2x8开开开x=x+1开开开开开开开x图11-18解析程序框图模拟分析，如表11-6所示.表11-6步骤x是奇数xx8?第1次是2第2次否4否5第3次是6第4次否8否9第5次是10否12是根据表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.7B.0.75C.0.8D.0.9(3)执行如图11-19所示的程序框图，若P=0.8，则输出n=.开开SP开开开n=n+1开开n=1,S=0开开n开开P12nSS图11-19变式2根据图11-20所示的程序框图，将输出的,xy值依次记为x1，x2，…，xn，…，x2014；y1，y2，…，yn，…，y2014.(1)求数列{xn}的通项公式；(2)写出y1，y2，y3，y4，由此猜想出{yn}的一个通项公式yn，并证明你的结论；(3)求1122(*,2014)nnnzxyxyxynnN.开开x=1开y=2开n=1y=3y+2n2014开开开开开开开x,yx=x+2n=n+1图11-20题型5算法案例思路提示按照秦九韶算法计算多项式值是转化为一次式值反复计算，这体现了将高次多项式值转化为一次式值得计算.例11.6用秦九韶算法求多项式542()543fxxxx21x，当2x时的值.解析54254()54321540fxxxxxxx32321((((54)0)3)2)xxxxxxxx123451,14;