算法初步知识点及题型归纳(共16页).doc

《算法初步知识点及题型归纳(共16页).doc》由会员分享，可在线阅读，更多相关《算法初步知识点及题型归纳(共16页).doc（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上算法初步知识点及题型归纳知识点精讲一、 算法与程序框图1.算法 算法通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是确定的和能执行的，并且能够在有限步之内完成2. 程序框图(1)定义：程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形（2）说明：在程序框图中，一个或几个程序框的组合表示算法中的一个步骤；带有方向的流程线将程序框连接起来，表示算法步骤的执行顺序33种基本逻辑结构 程序框图有3种基本的逻辑结构，如表11-1所示.表11-1名称内容 顺序结构条件结构循环结构定义顺序结构是由若顺序结构由若干个依次执行的步骤组成的，是任

2、何一个算法都离不开的基本结构算法的流程根据条件是否成立有不同的流向，条件结构就是处理这种过程的结构从某处开始，按照一定的条件反复执行某些步骤反复执行的步骤称为循环体程序框图步骤n+1步骤n否是满足条件？步骤B步骤A二、基本算法语句1.3中基本算法语句的一般格式和功能3中基本算法语句的一般格式和功能如表11-2所示.表11-2语句一般格式功能输入语句INPUT“提示内容”；变量输入信息输出语句PRINT“提示内容”；表达式输出结果赋值语句变量表达式将表达式的值赋给变量2.条件语句(1)算法中的条件结构由条件语句来表达(2)条件语句的格式及框图如图11-1和11-2所示.IFTHEN格式是满足条件

3、？语句体否图11-1IF条件THEN 语句体 ENDIFTHENELSE格式是否满足条件？语句体2语句体1图11-2IF条件THEN 语句体1ELSE 语句体2END 3循环语句(1)算法中的循环结构是由循环语句来实现(2)循环语句的格式及框图如图11-3和11-4所示UNTIL语句图11-3 DO 循环体LOOP UNTIL条件图11-4WHILE语句WHILE 条件循环体END（3）WHILE语句与UNTIL语句之间的区别与联系如表11-3所示.表11-3WHILE语句UNTIL语句区别执行循环体前测试条件，当条件为真时执行循环体，当条件为假时终止循环，可能不执行循环体执行循环体后测试语句

4、条件，当条件为假时执行循环体，当条件为真时终止循环，最少执行一次循环体联系可以相互转换，LOOP UNTIL(条件)相当于WHILE（反条件）三、算法案例 1.辗转相除法 辗转相除法又叫欧几里德算法，是一种求最大公约数的古老而有效的算法，其步骤如下：(1)用两数中较大的数除以较小的数，求得商和余数；(2)以除数和余数中较大的数除以较小的数；(3)重复上述两步，直到余数为0；(4)较小的数是两数的最大公约数.2.更相减损术 更相减损术是我国古代数学专著九章算术中介绍的一种求两数最大公约数的算法，其基本过程为：对于任意给定的两个正整数，以大数减小数，接着把所得的差与较小的数比较，并以大数减小数，继

5、续该操作，直到所得的数相等为止，这个数(等数)就是所求的最大公约数.3.秦九韶算法秦九韶算法是我国南宋数学家秦九韶在他的代表作数书九章中提出的一种用于计算一元n次多项式的值的方法。4.进位制进位制是人们为了计数和运算方便而约定的记数系统，“满k进1”就是k进制，k进制的基数是k.题型归纳及思路提示 根据考纲要求并结合高考中常见题型，程序框图主要用于数列、分段函数、大小比较等程序性问题的解决要求考生能读懂程序框图，理解所执行的程序题型155-160是针对程序框图中所解决的问题来分类，但从算法角度讲没有本质区别，因而解决它们的思路是一致的，具体是： (1)先通过程序框图宏观分析是解决什么样的(数学

6、)问题，并明确该问题解决的具体思路步骤；(2)将该问题的解决思路步骤与程序框图所执行的程序比较；是否开始 kN?输出SPPRU输入N结束图11-5(3)根据题目要求做答(可能是求输出结果或输入参量，也可能是填充判断框).题型1 程序框图中的数列求和问题思路提示 循环体是所求和的表达式，也是反复执行的步骤，需按变量取值依次进行.例11.1如果执行如图11-5所示的框图，输入N=5，则输出的数等于( )A. B. C. D.解析 解法一：将程序框图所执行的程序分步进行计算，如表11-4所示.表11-4步骤kSk8?第1次是2第2次否4否5第3次是6第4次否8否9第5次是10否12是根据表11-6的

7、模拟分析，程序输出的x值为12.变式1 (1)执行如图11-19所示的程序框图，若输出的n为4，则输入P的取值范围为（ ）.A. (0.75, 0.875) B. (0.75, 0.875C. 0.75, 0.875) D. 0.75, 0.875(2) 执行如图11-19所示的程序框图，若输出的n为4，则输入P可能为（ ）.A. 0.7 B. 0.75C. 0.8 D. 0.9(3) 执行如图11-19所示的程序框图，若P=0.8，则输出n= .图 11-19变式2 根据图11-20所示的程序框图，将输出的值依次记为x1，x2，xn，x2014；y1，y2，yn，y2014.(1) 求数列

8、xn 的通项公式；(2)写出y1，y2，y3，y4，由此猜想出 yn 的一个通项公式yn，并证明你的结论；(3)求.图11-20题型5 算法案例思路提示按照秦九韶算法计算多项式值是转化为一次式值反复计算，这体现了将高次多项式值转化为一次式值得计算.例11.6 用秦九韶算法求多项式 ，当时的值.解析，所以当时，多项式的值为241，即.评注 秦九韶算法的原理就是通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可.(1) 计算步骤如下：设将其改写为.第一步：计算最内层的值，将的值赋给一个变量（先把赋给变量）；第二步：计算的值，将的值赋给一个变量；依此类推，

9、第步：求得的值就是欲求多项式的值.(2)程序框图如图11-21所示.图11-21变式1用秦九韶算法求多项式 ，当 时的值的时候，第二步计算的结果为 .变式2 (1)把十进制数21转化为二进制数；(2)将八进制数31072(8)转化为十进制数有效训练题1. 执行如图11-22所示的程序框图，输出的S值为（ ）.A. 2 B. 4 C. 8 D. 162. 执行如图11-23所示的程序框图，若输入x=2，则输出的y的值为（ ）.A. 2 B. 5 C. 11 D. 233. 如图11-24所示给出的是计算 的一个程序框图.其中判断框内应填入的条件是（ ）.A. i50? C. i25?4. 执行如

10、图11-25所示的程序框图，输出S的值为（ ）.A.3 B. 6 C. 10 D. 15 图11-22 图11-23 图11-24 图11-255. 执行如图11-26所示的程序框图，输出S的值为( ).A. 1 B. -1 C. -2 D. 06. 执行如图11-27所示的程序框图，输出S的值为( ).A. -1 B. C. D. 4 图11-26 图11-277. 若某程序框图如图11-28所示，则该程序运行后输出k的值是 .8. 执行如图11-29所示的程序框图，输入，则输出的数S= . 图11-28 图11-299. 阅读如图11-30所示的程序框图，运行相应的程序，输出的结果是S=

11、.10. 执行如图11-31所示的程序框图，若输入的n值为8，则输出S的值为 . 图11-30 图11-31 11. 如图11-32所示是一个计算机装置示意图，J1，J2是数据入口处，C是计算机结果的出口，计算机过程是由J1，J2分别输入自然数m和n，经过计算机处理后将所得自然数由C输出，此种计算装置完成的计算机满足以下3个性质：若J1，J2分别输入1，则输出结果为1；若J1输入任何固定自然数m不变，J2输入自然数n增大1，则输出结果比原来大2；若J2输入1，J1输入自然数m增大1，则输出结果为原来的2倍.试问：(1)若J1输入1，J2输入自然数n，输出结果为多少？(2)若J2输入1，J1输入自然数m，输出结果为多少？ 图11-3212. 甲、乙两同学进行下棋比赛，约定每局胜者得1分，负者得0分（无平局），比赛进行到了一个人比对方多2分或满8局时停止.设甲在每局比赛中获胜的概率为 ，且各局比赛胜负相互独立.已知第二局比赛结束时比赛停止的概率为.(1)如图11-33所示为统计这次比赛的局数n和甲、乙的总分S，T的程序框图.其中如何甲获胜，输入a=1，b=0；如果乙获胜，则输入a=0，b=1.请问在，两个判断框中应分别填写什么条件？(2)求p的值；(3)设表示比赛停止时已比赛的局数，求随机变量的分布列及E. 图11-33专心-专注-专业