高三数学：直击之第十四章算法初步

第十四章 算法初步知识网络算法与框图算法与程序框图算法程序框图算法的逻辑基本结构顺序结构条件分支结构循环结构基本算法语句输入语句，输出语句，赋值语句，条件语句，循环语句算法案例辗转相除法与更相减损术秦九韶算法进位制第1讲 算法的概念与程序框图知识梳理1.算法：可以用计算机来解决的某一类问题的程序或步骤2.算法中的程序和步骤必须是明确和有效的，而且能够在有限步之内完成.3.算法具有概括性（能解决一类问题），确切性（每一步操作的内容和顺序必须是明确的），有穷性（必须在有限步内结束并返回一个结果），不唯一性（一个问题可以有多个算法，算法有优劣之分），普遍性（很多具体的问题，都可以设计合理的算法去解决）.4.程序框图又称流程图，是一种用规定的图形，指向线及文字说明来准确地、直观地表示算法的图形；5.算法的基本逻辑结构（顺序结构、条件结构和循环结构）顺序结构表示语句和语句之间，框与框之间是按顺序进行的；条件结构是需要先根据条件作出判断，再决定执行哪一种操作的结构；循环结构是需要反复执行某一处理步骤的结构，分为当型（WHILE型）和直到型（UNTIL型），当型（WHILE型）循环是指在每次执行循环体前对控制循环条件进行判断，当条件满足时执行循环体，不满足时停止，直到型（UNTIL型）循环是先执行一次循环体，然后对控制循环条件进行判断，当条件不满足时执行循环体，满足则停止.重难点突破1.重点：理解程序框图的三种基本逻辑结构，掌握三种逻辑结构在程序框图中的体现和特点2.难点：绘制简单实际问题的流程图，正确理解各种算法语句的实际意义3.重难点：设计算法时要综合考虑问题中可能涉及的各种情况：必须能解决一类问题，并且能重复使用；算法过程要一步一步执行，每一步执行的操作，必须确切，不能含糊不清，而且在有限步后得出结果条件结构主要用在一些需要依据条件进行判断的算法中，如分段函数的求值、参数的讨论等循环结构主要用在一些有规律的重复计算的算法中，如累加求和、累乘求积等热点考点题型探析考点一 算法与程序框图题型1 对算法阅读能力的考查【例1】一个算法如下：第一步：计算； 第二步：若，输出最小值；第三步：若，输出最大值已知，则运行以上步骤输出的结果为 【解题思路】只要按照算法的含义有步骤地描述解决的过程，便可得到该题的结果开始b=4输出Sa=2结束（1）【解析】本题算法用于求二次函数的最值故输出最小值2【名师指引】把解决该问题的步骤进行呈现就是算法的思想题型2 对程序框图阅读能力的考查【例2】写出图的程序框图的运行结果 【解题思路】只要按照程序框图的箭头有步骤地计算，可得该题的结果【解析】本题程序框图用于求【名师指引】正确理解程序框图及算法是解题的关键 题型3 算法和程序框图的设计Y开始P=0i=0i=i+1p=p+ip1000?输出i结束N图(2)【例3】试写出寻找满足条件的最小正整数的算法，并画出相应的算法程序框图【解题思路】由于是一个较大的数，用猜的办法不可取，可采用循环结构设计算法【解析】算法如下：第一步：取值；第二步：取值；第三步：用的值代替；第四步：用的结果代替；第五步：如果，则输出；否则执行第六步第六步：回到第三步，重新执行第三步，第四步，第五步相应的算法程序框图如图所示【名师指引】把解决该问题的步骤进行呈现，设计算法，按要求画出相应的程序框图 【新题导练】1.一个算法如下：第一步：取值取值；第二步：若不大于，则执行下一步；否则执行第六步；第三步：计算且将结果代替；第四步：用结果代替；第五步：转去执行第二步；第六步：输出则运行以上步骤输出的结果为 【解析】25此算法用于计算2.写出图的程序框图的运行结果：若，则 图(4)开始输出N结束开始输入Ra=2b输出a结束（3）【解析】3.某工厂2008年的生产总值100万元，技术革新后预计以后每年的生产总值比上一年增加5%，问最早需要哪一年年生产总值超过200万元.写出计算的一个算法并画出相应的程序框图.【解析】依题意知第年后生产总值的计算公式为,此时为年.算法如下: 第一步:；第二步:(计算年增量)；第三步: (计算年产值)；第四步:如果,那么,重复执行第二步；第五步:；第六步:输出 程序框图如图所示考点2 基本逻辑结构的运用题型1 条件分支结构的运用【例4】已知，写出该函数函数值的算法及程序框图【解题思路】求分段函数的函数值问题，可用条件分支结构【解析】算法如下：第一步：输入； 第二步：如果，那么使，如果，那么使；第三步：输出函数值程序框图如图（5）所示：开始输出y结束（6）是否【名师指引】条件分支结构的运用与数学中的分类讨论有关设计算法时，哪一步要分类讨论，哪一步就需要用条件分支结构 开始输出y输入x结束y=2y=0y= -2（5）题型2 循环结构的运用【例5】已知，将区间10等分，画出求各等分点及端点函数值的程序框图【解题思路】将区间10等分，得11个数：引入变量，从0开始，每算一个函数值，的值就增加1，直到为止故可用循环结构设计算法开始结束输出（7）【解析】程序框图如图所示：【名师指引】对于这种有规律的计算问题，一般可采用循环结构设计算法题型3 顺序结构的运用【例6】阅读如图流程图，则输出的结果是 【解题思路】顺序结构表示语句和语句之间，框与框之间是按顺序进行的【解析】，结果是【名师指引】对于这种顺序结构的计算问题，算法过程要一步一步按顺序执行【新题导练】4.阅读图8的流程图，若输入的分别是，则输出的分别是 【解析】5.阅读如图流程图，若输入，则输出的结果是 【解析】结果是6.如图的程序框图，则输出的数是 开始结束输入a,b,cx=aa=cc=bb=x输出a,b,c（8）【解析】(9)开始输入x输出p开始否是开始结束输出sumi=2,sum=0sum=sum+ii=i+2（10） 抢 分 频 道 基础巩固训练1.下列结论正确的是（ ） A一个程序的算法步骤是可逆的 B一个算法可以无止境地运算下去 C完成一件事情的算法有且只有一种 D设计算法要本着简单方便的原则【解析】D2.下面对算法描述正确的一项是（ ）A算法只能用自然语言来描述 B算法只能用图形方式来表示C同一问题可以有不同的算法 D同一问题的算法不同，结果必然不同【解析】C算法的特点：有穷性，确定性，顺序性与正确性，不唯一性，普遍性3.下列说法不正确的是（ ） A任何一个算法一定含有顺序结构 B任何一个算法都可能由顺序结构、条件结构、循环结构构成 C循环结构中一定包含条件结构 D条件结构中一定包含循环结构【解析】D4.计算下列各式中的值，能设计算法求解的是（ ） ； ； A B C D【解析】B. 为求无限项的和，而算法要求必须在有限步之内完成5. 程序框图5中，若时，输出的结果为 .【解析】6.已知，以下程序框图6表示的是给定的值，求其函数值的算法.请将该程序框图补充完整.其中处应填 ，处应填 .开始输入x输出y结束y=6-x是否第6题结束输出x输入y开始第5题【解析】 综合拔高训练7.设计算法求的值，要求画出程序框图【解析】这是一个累加求和问题，共99项相加，可设计一个计数变量，一个累加变量，用循环结构实现这一算法程序框图如图7所示：否是开始输出S 结束第7题8.设计一个计算100个数的平均数的算法的程序框图【解析】解法一：用当型循环（如图8）：解法二：用直到型（如图9）： 结束否是开始输入Gi=1sum=0i=i+1sum=sum+GM=输出M图9是图8结束否开始输入Gi=1sum=0i=i+1sum=sum+GM=输出M第2讲 基本算法语句知识梳理1.基本算法语句的格式要求：任何一种程序设计语言中都包含五种基本的算法语句，它们分别是输入语句、输出语句、赋值语句、条件语句、循环语句 输入语句的一般格式是：INPUT “提示内容”；变量；输出语句的一般格式是PRINT “提示内容”； 表达式；赋值语句的一般格式是：变量=表达式 条件语句有两种：一种是IFTHENELSE语句；另一种是IFTHEN语句循环语句分WHILE语句和UNTIL语句2.基本算法语句的含义及用法基本算法语句的含义及用法输入、输出语句和赋值语句是任何算法程序必不可少的基本算法语句；当算法程序按条件进行分析、比较、判断，并按判断后的不同情况进行不同处理时，需用条件语句来实现；当处理一些需要反复执行的运算任务，如累加求和、累乘求积等问题时，常用到循环语句，若先考虑判断，再进行循环，则使用当型（WHILE型）循环；若先进行循环，再判断，可使用直到型（UNTIL型）循环，直到型循环语句至少执行一次循环体，而当型循环语句则可能一次也不执行循环体，二者本质上是相同的，可以相互转化重难点突破1.重点：理解五种基本算法语句及其表达方式、结构、用法2.难点：理解两种循环语句的使用技巧3.重难点：输入语句要求输入的值只能是具体的常数；输出语句可以输出常量、变量、表达式的值及字符；注意赋值语句的格式；在使用条件语句时，要注意IF与ELSE的配对关系；在使用循环语句，要注意对循环变量的控制，避免多一次或少一次循环热点考点题型探析INPUT a,b,ca=bb=cc=aPRINT图1考点1 赋值语句的运用【例1】右面的算法程序，若输入，则输出结果是（ ）A. B. C. D. 【解题思路】理解赋值语句的一般格式：变量=表达式【解析】先把的值赋给，；再把的值赋给，；最后把的值赋给，选C.【名师指引】在赋值语句中，理解或或的含义是：把的值赋给.INPUT IF THENELSEEND IFPRINT END图2考点2 条件语句的运用【例2】阅读右面的算法程序，写出程序运行的结果.该程序中使用的是 格式的条件语句若，则 ；若，则 .【解题思路】本题算法程序中使用了条件语句，该语句被执行时，首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句1，若条件不符合，就执行ELSE后的语句2【解析】“IFTHENELSE”当时，则，故；当时，则，此时【名师指引】在使用条件语句的嵌套时要注意IF和ELSE的配对关系.考点3 循环语句的运用【例3】求成立的的最大整数值，用程序语言表示其算法【解题思路】这是一个累加求和问题，可用循环语句来实现，可用两种语句实施【解析】这是一个累加求和问题，可用循环语句来实现，注意累加和如图3、图4WHILE语句 UNTIL语句s=1i=2DO s=s+a i=i+1LOOP PUNTIL s=50i=i-2PRINT“的最大整数为”；iEND图4s=1i=2WHILE s=s+a i=i+1WEND i=i-2PRINT“的最大整数为”；iEND图3A=10B=A-8A=A-BPRINT AEND图5【名师指引】使用循环语句时，要注意循环变量的取值当型（WHILE型）循环与直到型（UNTIL型）循环的控制条件是互否的【新题导练】1.如图5的程序运行结果是 【解析】82.如图6的程序段结果是 【解析】15分别代入计算，得时，3.如图7的程序：程序（一）的运行结果是 ；若程序（一）、（二）的运行结果相同，则程序（二）输入的值为 INPUT xIF x=0THEN y=xELSE y= -xEND IFPRINT yEND图8x=1x=xix=x3PRINT xEND(一)INPUT xy=yx+6PRINT yEND（二）图7图6i=1s=0WHILE i=4s=sx+1i=i+1WENDPRINT sENDs=0k=1DOs=s+1/(k*(k+1)k=k+1LOOP UNTIL PRINT”s=”;sEND图9【解析】；4.如图8的程序，若程序执行的结果是3，则输入的值为 【解析】3或-3本题是计算的一个算法程序，由，得5.利用计算机计算:,某同学编写的图9程序语句中，处应填_ _.【解析】. 循环体执行到. 抢 分 频 道 基础巩固训练1. (2006广州模拟）下列赋值能使的值为的是（ ） A B C D【解析】D. 赋值时把“=”右边的值赋给左边的变量，故选D2. (2005广州模拟)当时，下面的程序段结果是（ ）A B C D【解析】C.当时，故选C3. (2007深圳模拟)下图程序执行后输出的结果是( )A、 B、0 C、1 D、2【解析】C. 当时跳出循环体4（2007南海模拟）计算机执行如下图的程序段后，输出的结果是（ ） A B C D【解析】B.执行程序得，故选B5.(2006惠州模拟)当时，执行完如下图一段程序后的值是（ ）A1 B3 C4 D【解析】C. 故选CIF THEN ELSEEND IF第5题图a=1b=3a=a+bb=abPRINT a,b第4题图n=5s=0WHILE s14s=s+nn=n-1WENDPRINT nEND第3题图i=1s=0WHILE i10PRINT xEND第6题图6.如图程序A.不能执行 B.能执行一次 C.能执行十次 D.有语法错误【解析】D.应为LOOP UNTIL，考查程序语句的严密性.7. 如图所示的程序，若程序执行的结果是3，则输入的值可能为 INPUT “x=”；xy=xx+2xPRINT yEND第7题图【解析】由，得，或8. 9.以下属于基本算法语句的是 INPUT语句；PRINT语句； IF-THEN语句；DO语句；END语句； WHILE语句；END IF语句【解析】9.给出以下四个问题：输入一个数, 输出它的相反数；求面积为的正方形的周长；求三个数中的最大数； 求函数的函数值. 其中不需要用条件语句来描述其算法的有 【解析】仅不需要分情况讨论，即不需要用条件语句综合拔高训练10. 12.用二分法求方程在上的近似解，精确到，写出算法画出流程图，并写出算法语句.INPUT DO IF THEN PRINT ELSE IF THEN ELSE END IFEND IFLOOP UNTILPRINT END第10题图【解析】算法如下：第一步：取中点，将区间一分为二；第二步：若，则就是方程的根；否则所求根在的左侧或右侧；若，则，以代替；若，则，以代替；第三步：若，计算终止 此时，否则转到第一步算法语句和流程图如图所示:第3讲 算法案例知识梳理1.辗转相除法是用于求最大公约数的一种方法，这种算法由欧几里得在公元前年左右首先提出，因而又叫欧几里得算法. 2.所谓辗转相法，就是对于给定的两个数，用较大的数除以较小的数.若余数不为零，则将较小的数和余数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时的除数就是原来两个数的最大公约数. 3.更相减损术是一种求两数最大公约数的方法.其基本过程是：对于给定的两数， 用较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数就是所求的最大公约数. 4.秦九韶算法是一种用于计算一元二次多项式的值的方法. 5.常用的排序方法是直接插入排序和冒泡排序. 6.进位制是人们为了计数和运算方便而约定的记数系统.“满进一”，就是k进制， 进制的基数是k. 7.将进制的数化为十进制数的方法是：先将进制数写成用各位上的数字与k的幂的乘积之和的形式，再按照十进制数的运算规则计算出结果. 8.将十进制数化为进制数的方法是：除k取余法.即用k连续去除该十进制数或所得的商， 直到商为零为止，然后把每次所得的余数倒着排成一个数就是相应的进制数.重难点突破1.重点：理解辗转相除法与更相减损术的原理,会求两个数的最大公约数；理解秦九韶算法原理，会求一元多项式的值；会对一组数据按照一定的规则进行排序；理解进位制，能进行各种进位制之间的转化2.难点：秦九韶算法求一元多项式的值及各种进位制之间的转化3.重难点：理解辗转相除法与更相减损术、秦九韶算法原理、排序方法、进位制之间的转化方法热点考点题型探析考点1 求最大公约数 【例1】用辗转相除法求和的最大公约数，并用更相减损术检验所得结果.【解题思路】将80作为大数，36作为小数，执行辗转相除法和更相减损术的步骤均可.【解析】用辗转相除法： ， ， ， 故和的最大公约数是 用更相减损术检验： 和的最大公约数是， ，【名师指引】辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数；更相减损术是当大数减去小数的差时等于小数时停止减法，较小的数就是最大公约数.【新题导练】1. 试求288和123的最大公约数. 【解析】， ， ， .和的最大公约数考点2 进制间的转化 【例2】(1)把二进制数化为十进制数；(2)把化为二进制数.【解题思路】(1)先把二进制数写成不同位上数字与2的幂的乘积之和的形式，再按照十进制的运算规则计算出结果；(2)根据二进制数“满二进一”的原则，可以用连续去除或所得商，然后取余数.【解析】(1) (2) ，.所以.这种算法叫做除2余法，还可以用下面的除法算式表示；把上式中各步所得的余数从下到上排列，得到【名师指引】直接插入排序和冒泡排序是两种常用的排序方法，通过该例，我们对比可以发现， 直接插入排序比冒泡排序更有效一些，执行的操作步骤更少一些.【新题导练】2. 把化为进制的数. 【解析】，.所以，.考点3 用秦九韶算法求多项式的值 【例3】用秦九韶算法求多项式在的值.【解题思路】可根据秦九韶算法原理，将所给多项式改写，然后由内到外逐次计算即可.【解析】 而，所以有，.即.【名师指引】利用秦九韶算法计算多项式值关键是能正确地将所给多项式改写，然后由内到外逐次计算，由于后项计算需用到前项的结果，故应认真、细心，确保中间结果的准确性.【新题导练】3.求多项式当时的值. 【解析】而，所以有.，. 抢 分 频 道 基础巩固训练1.下面关于算法的说法正确的是 ( )A. 秦九韶算法是求两个数的最大公约数 B. 更相减损术是求多项式的值的方法C. 辗转相除法是求多项式的值的方法 D. 以上结论皆错【解析】D.2.下列关于利用更相减损术求156和72的最大公约数的说法，正确的是( )A. 都是偶数必须约简 B. 可以约简，也可以不约简C. 第一步作差为，第二步作差为 D. 以上皆错【解析】B.3.168和486的最大公约数是( )A. 3 B. 4 C. 6 D. 16【解析】C.4.利用秦九韶算法求当时，的值时， 下列说法正确的是( )A.先求B.先求， 第二步求C.直接运算求解D. 以上皆错【解析】B.5.用秦九韶算法求多项式时，求需要算乘方、乘法、加法的次数分别为( )A. B. C. D. 【解析】D.6.用冒泡法对数据从小到大排序，第二趟得到的数列为：_.【解析】 第一趟：；第二趟：.7.二进制数的十进制数：_；十进制数的二进制数为：_.【解析】.余数1 011505252156331126731222222222201100111111综合拔高训练8.用秦九韶算法求多项式当时的值.【解析】而，所以有； .第十六章综合检测（120分钟，150分）一、选择题（每小题5分，共40分在每小题给出的四个选项中，只有一项是符合题目要求的）1下列运算不属于我们所讨论算法范畴的是（）已知圆的半径求圆的面积 随意抽张扑克牌算到二十四点的可能性已知坐标平面内两点求直线方程 加减乘除法运算法则【解析】B A、C、D均可以按照一定的步骤完成2早上从起床到出门需要洗脸刷牙(5 min)、刷水壶(2 min)、烧水(8 min)、泡面(3 min)、吃饭(10 min)、听广播(8 min)几个步骤、从下列选项中选最好的一种算法（）AS1 洗脸刷牙、S2刷水壶、S3 烧水、S4 泡面、S5 吃饭、S6 听广播B刷水壶 、S2烧水同时洗脸刷牙、S3泡面、S4吃饭、S5 听广播C刷水壶 、S2烧水同时洗脸刷牙、S3泡面、S4吃饭 同时 听广播D吃饭 同时 听广播、S2泡面、S3烧水同时洗脸刷牙、S4刷水壶【解析】C3以下关于排序的说法中，正确的是（ ）A排序就是将数按从小到大的顺序排序B排序只有两种方法，即直接插入排序和冒泡排序C用冒泡排序把一列数从小到大排序时，最小的数逐趟向上漂浮D用冒泡排序把一列数从小到大排序时，最大的数逐趟向上漂浮【解析】C由冒泡排序的特点知C正确.4下列语句中： 其中是赋值语句的个数为（ ） A6 B5 C4 D3【解析】C 为赋值语句S=0 i=1DO INPUT x S=S+x i=i+1LOOP UNTIL _a=S/20PRINT aEND第7题图5把“二进制”数化为“五进制”数是（ ）A B C D【解析】C先转化成“十进制”，再转化为“五进制”数.6840和1764的最大公约数是（ ）A84 B12 C168 D252【解析】A用辗转相除法或更相减损术可求得.7下面为一个求20个数的平均数的程序,在横线上应填充的语句为 ( )Ai20 Bi=20 Di=20【解析】A依题意须循环20次8为了在运行下面的程序之后得到输出y16，键盘输入x应该是（ ）A或 B C或 D或【解析】C令得：或（舍），令得：或（舍）二、填空题：(本大题共7小题，其中1315小题是选做题；每小题5分，共30分)INPUT xIF x0 THENy=(x+1)*(x+1) ELSEy=(x-1)*(x-1) End ifPrint yend 第8题图9已知有下面程序，如果程序执行后输出的结果是11880，那么在程序UNTIL后面的“条件”应为 【解析】（或） 10给出下面的程序框图，那么其循环体执行的次数是 【解析】 从运行到步长为，运行次数为499i=12s=1DO s = s * i i = i1LOOP UNTIL 条 件 PRINT sEND（第9题）程序否是开始i2，sum0sumsumiii2i1000？结束（第10题图）11比较大小： 【解析】 由于，所以，而，所以12用等值算法求294和84的最大公约数时，需要做 次减法.【解析】4由等值算法可求得选做题（从13题、14题、15题中任选2题）13下列四个有关算法的说法中，正确的是 . ( 要求只填写序号 )INPUT xIf x0THEN else Print yend 14题 算法的某些步骤可以不明确或有歧义，以便使算法能解决更多问题； 正确的算法执行后一定得到确定的结果； 解决某类问题的算法不一定是唯一的；正确的算法一定