算法部分章质量检测本章知识结 构程序框图辗转相除法与更相减损术秦九韶算法算法算法语句排序进位制一、知识点剖析1．算法的定义和特点掌握要点：算法定义：在数学中指按照一定规则解决某一类问题的明确和有限的步骤算法特点：①有穷性：一个算法的步骤是有限的，它应在有限步操作之后停止②确定性，算法的每一步操作必须是明确的，不能有歧义或模糊且算法执行后一定产生确定的结果，不能模棱两可③可行性：算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个明确的后继步骤，前一步是后一步的前提,只有执行完前一步才能进行下一步，并且每一（步都要准确无误才能解决问题④不惟一性：求解某一类问题的算法是不惟一的，对于一个问题可以有不同的算法⑤普遍性，很多具体的问题都可以设计合理的算法解决易混易错： 1）算法一般是机械的，有时要进行大量重复的运算，只要按部就班的做总能算出结果，通常把算法过程称为“数学机械化”“数学机械化”的最大优点是它可以让计算机来完成2）实际上，处理任何问题都需要算法如，邮购物品有其相应的手续购买飞机票也有一定的手续等3）求解某个问题的算法不惟一2．（1）程序框图表示算法步骤的一些常用的图形和符号图形符号名称终端框（起止框）输入、输出框处理框功能程序的开始和结束，表示数据的输入或结果的输出赋值,计算判断框 判断某一条件是否成立，成立时在出口处标明： “是”或“YES”；不成立时在出口处标明“否”或”NO”流程线连接点连接程序框连接程序框图的两部分易混易错：在所给的上述符号之中只有判断框有一个入口和两个出口，它是唯一有两个退出点的符号。
2）三种基本逻辑结构①顺序结构②条件结构③循环结构顺序结构：顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的这是任何一个算法都离不开的基本结构条件结构：在一个算法中，经常会遇到一些条件的判断，算法的流程根据条件是否成立会有不同的流向，条件结构就是处理这种过程的结构易混易错：在条件结构中无论条件是否成立，都只能执行两框之一，两框不可能同时执行，也不可能两框都不执行循环结构：算法结构中经常会遇到从某处开始，按照一定条件反复执 行某些步骤的情况，这就是循环结构，反复执行的步骤成为循环体循环结构分为两种：当性循环结构和直到性循环结构当性循环结构：在每次执行循环体前，对条件进行判断，当条件满足时，执行循环体，否则终止循环先判断”直到性循环结构：在执行了一次循环体后，对条件进行判断，如果条件不满足就继续执行循环体，直到条件满足时终止循环先循环”注意：循环结构中一定包含着条件结构3．基本算法语句（1）输入语句①输入语句的一般形式是：INPUT “提示内容”；变量②输入语句的作用是实现算法的输入信息功能③“提示内容”提示用户输入什么样的信息④输入语句可以给变量提供初值⑤提示内容与变量之间用分号隔开，若输入多个变量，变量之间用逗号隔开。
例如：I NPUT “提示内容 1，提示内容 2，提示内容 3，„”；变量 1，变量 2，变量（2）输出语句①输出语句的一般形式是：PRINT “提示内容”；表达式②输出语句的作用是实现算法的输出结果功能③“提示内容”提示用户输入什么样的信息，如 PRINT “S=；S 是提示输出的结果是 S 的值④PRINT 语句可以在屏幕上出现常量、变量以及系统信息注意：任何求解问题的算法，都要把求解问题的结果输出3）赋值语句①赋值语句是最基本的语句②赋值语句的一般格式为：变量=表达式③“=”叫做赋值号易混易错: ①赋值号做变只能是变量而不能使表达式②赋值号的左右两边不能调换③不能利用赋值语句进行代数式的演算（如化简、因式分解、解方程等）④赋值号与数学中的符号意义不同注意:输入语句、输出语句、赋值语句基本上对应程序框图中的顺序结构；一个算法有 0 个或者多个输入，有一个或多个输出；输出语句和赋值语句具有运算功能而输入语句不具有运算功能4）条件语句共分为两种形式 IF-THEN-ELSE 格式(1)语句 1IF 条件 THEN 满足条件？是否语句 1 语句 2ELSE语句 2当计算机执行上述语句时，首先对 IF 后的条件进行判断，如果条件符合，就执行 THEN 后的语句 1，否则执行 ELSE 后的语句 2。
其对应的程序框图为：（如上右图）② IF-THEN 格式是IF 条件 THEN语句满足条件？否语句计算机执行这种形式的条件语句时，也是首先对 IF 后的条件进行判断，如果条件符合，就执行 THEN 后的语句，如果条件不符合，则直接结束该条件语句，转而执行其他语句其对应的程序框图为：（如上右图）条件语句的作用：在程序执行过程中，根据判断是否满足约定的条件而决定是否需要转换到何处去需要计算机按条件进行分析、比较、判断，并按判断后的不同情况进行不同的处理5）循环语句算法中的循环结构是由循环语句来实现的对应于程序框图中的两种循环结构一般程序设计语言中也有当型（WHILE 型）和直到型（UNTIL 型）两种语句结构即 WHILE语句和 UNTIL 语句①WHILE 语句的一般格式是：WHILE 条件循环体循环体满足条件？是否其中循环体是由计算机反复执行的一组语句构成的WHLIE 后面的“条件”是用于控制计算机执行循环体或跳出循环体的当计算机遇到 WHILE 语句时，先判断条件的真假，如果条件符合，就执行 WHILE 与 WEND之间的循环体；然后再检查上述条件，如果条件仍符合，再次执行循环体，这个过程反复进行，直到某一次条件不符合为止。
这时，计算机将不执行循环体，直接跳到WEND 语句后，接着执行 WEND 之后的语句因此，当型循环有时也称为“前测试型”循环其对应的程序结构框图为：（如上右图）②UNTIL 语句的一般格式是：DO循环体循环体 否LOOP UNTIL 条件满足条件？是其对应的程序结构框图为：（如上右图）从 UNTIL 型循环结构分析，计算机执行该语句时，先执行一次循环体，然后进行条件的判断，如果条件不满足，继续返回执行循环体，然后再进行条件的判断，这个过程反复进行，直到某一次条件满足时，不再执行循环体，跳到 LOOP UNTIL 语句后执行其他语句，是先执行循环体后进行条件判断的循环语句区别：在 WHILE 语句中，是当条件满足时执行循环体，而在 UNTIL 语句中，是当条件不满足时执行循环体4．算法案例辗转相除法算法：第一步：用较大的数 m 除以较小的数 n 得到一个商 q0 和一个余数 r0；第二步：若 r0＝0，则 n 为 m，n 的最大公约数；若 r0≠0，则用除数 n 除以余数 r0 得到一个商 q1 和一个余数 r1；第三步：若 r1＝0，则 r1 为 m，n 的最大公约数；若 r1≠0，则用除数 r0 除以余数 r1 得到一个商 q2 和一个余数 r2；„„1依次计算直至 rn ＝0，此时所得到的 rn－ 即为所求的最大公约数。
开始输入两个正整数m，nm>n?否是 x=nn=mm=xr=m MOD n n=rm=nr=0? 否是输出n程序框图程序：INPUT “m=”;m结束INPUT “n=”;nIF m0r=m MOD nm=nn=rWENDPRINT mEND更相减损术更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母·子之数，以少减多，更相减损，求其等也，以等数约之翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数若是，用2 约简；若不是，执行第二步第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数1） 辗转相除法与更相减损术区别联系①都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显②从结果体现形式来看，辗转相除法体现结果是以相除余数为 0 则得到，而更相减损术则以减数与差相等而得到(2)秦九韶算法与排序掌握秦九韶算法的原理=anvk=vk-1+an-k (k=1,2,3,……n)(3)进位制进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。
可使用数字符号的个数称为基数，基数为 n，即可称 n 进位制，简称 n 进制现在最常用的是十进制，通常使用10 个阿拉伯数字 0-9 进行记数易混易错：表示各种进位制数一般在数字右下脚加注来表示, 如 111001(2)表示二进制数,34(5)表示 5 进制数.二、典型例题剖析1．判断某一事情是否为算法方法归纳：（1） 判断某一问题是否为算法要把握算法的五个特征：①有穷性②确定性③可行性④不惟一性⑤普遍性例 1．下列关于算法的说法中正确的个数有( )例 2．设计算法求 1①求解某一类问题的算法是唯一的 ②算法必须在有限步操作之后停止③算法的每一步操作必须是明确的，不能有歧义或模糊④算法执行后一定产生确定的结果A. 1 B. 2 C. 3 D. 4主要过程：由算法的五个特征可以解得只有①是错误的，解答某一类问题的算法时不惟一的强调内容：把握好算法的五个特征2．就某一问题画出程序框图并写出算法（方法归纳： 1）画程序框图时一定要明确图中各个符号的作用并能正确使用三种基本逻辑结构2）用程序设计语言描述算法时一定要注意有些符号与框图之中书写的不同1 1 1+ + + ××× + 的值.要求画出程序框图，写出用基1´ 2 2 ´ 3 3 ´ 4 99 ´ 100本语句编写的程序.主要过程：i=1开始s=0i=1 DOs=0 s=s+1/(i*(i+1))s=s+1/(i*(i+1)) i=i+1i=i+1 LOOP UNTIL i>99i>99???PRINT sEND输出 s结束强调内容：解答此题目是一定要注意循环终止的条件是 i>99而不是i>100,因为这个数列共有99项3．讨论法画程序框图写程序方法归纳：先通过解决数学题的思想进行讨论，再画图写程序。
例3、画出解关于x的不等式ax+b<0 (a，b∈R)的流程图及程序INPUT a,bIF a= 0 THENIF b＞0 THENPRINT 无解ELSEPRINT x 为全体实数ELSE IF a＞0 THENPRINT x＜-ELSEba主要过程：如上强调内容：注意讨论时要全面，不但要讨论 a 还要讨论 b.4．实际应用：方法归纳：先通过解决数学题的思想进行讨论，再画图写程序例 4、某城市现有人口总数为 100 万人，如果年自然增长率为 1.2%，试解答下列问题：（1）写出该城市人口数 y（万人）与年份 x（年）的函数关系式；（2）用程序表示计算 10 年以后该城市人口总数的算法；（3）用流程图表示计算大约多少年以后该城市人口将达到 120 万人的算法主要过程：（1） y = 100 ´1.012 x（2)程序如下：S=100I=1.2X=0WHILE S<120S=S*IX=X+1WENDPRINT XENDN开始S=100I=1.2X=0S<120??YS=S*IX= X +1输出 X结束5． 求高次多项式的值方法归纳：能够 熟练利用秦九韶算法原理求高次多项式的值v =a0v =vknk -1 +an)n-k (k=1,2,3,……用秦九韶算法计算 f (x ) = 5x5 + 4 x4 + 3x3 + 2 x2 + x + 1主要过程：a5 =5, a 4 =4,a 3 =3,a 2 =2,a1 =1,a0 =1v = a =50 5v = v *2+ a =5*2+4=141 0 4v = v *2+ a =14*2+3=312 1 3v = v *2+ a =31*2+2=643 2 2v = v *2+ a =64*2+1=1294 3 1v = v *2+ a =129*2+1=2595 4 0所以 f(2)=259n-k (k=1,2, 3,…… 的正确应用强调内容：注意在运算过程之中 v =vkk -1 +an)三、高考链接1 n i（2008 广东 ） ．阅读右上的程序框图。
若输入 m = 4， = 3，则输出 a = __12__， =_3____ 注：框图中的赋值符号“=”也可以写成“←”或“：=”）开始输入 n（2007 山东）2．阅读如上右边的程序框图，若输入的 n是 100，则输出的变量 S 和 T 的 （ D ）A．2500，2500 B．2550，2550C．2500，2550 D．2550，2500`巩固练习1 、 给 出 一 个 算 法 的 流 程 图 （ 如 图 ）， 若, a n , (a = s iq nb = , q c =o s q q Î pt p ， 则 输 出 结果 ,a 为)4 2（ ）A、sinθ B、 cos q C、tanθ D、不确定= 0，T = 0Sn < 2?否s = s + nn = n - 1T = T + nn = n -1输入 a,b,ca>b是输出 S，T结束Y2．x=5Na>cYa=bN输出 aa=c第 1 题y=6PRINT x+y=11END上面程序运行时输出的结果是( )A.xy=11 B.11 C.x+y=11 D.出错信息3.如果下边程序执行后输出的结果是 990，那么在程序中 UNTIL 后面的“条件”应为( )A. i>10B. i<8C. i<=9i=11s=1DOs=s*ii=i－1LOOP UNTIL “条件”（第 3题图）D. i<9 PRINT SEND （第 10 题）4.如右图所示的程序是用来( )程序：S=1A．计算 3×10 的值 B．计算 3 的值 WHILE I<=10C．计算 3 的值 D．计算 1×2×3ׄ×10 的 值 I=I+1I=19S=3*S105.计算机中常用十六进制，采用数字 0～9 和字母 A～F 共 16 个计数符号与十进制得对应关系如下表：WENDPRINT SEND（第 4 题）16 进制10 进制00112233445566778899A B C D E F10 11 12 13 14 15(6) 化为十进数为 4934 ，则 m =例如用十六进制表示有 D+E＝1B，则 A×B=( )A 6E B 7C C 5F D B0二、填空题6. 若六进数 3m5027. 二进制数111.11 转换成十进制数是_________________.8. 右边程序输出的 n 的值是_____________________.j=1n=0WHILE j<=11j=j+1IF j MOD 4=0 THENn=n+1END IFj=j+1WENDPRINT nEND9．下图给出的是计算 1 + 1 + 1 + × × × + 1 的值的一个程序框图，其中判断框内应填入的2 4 6 20条件是 .12．已知 y = í x + 2 ，x Î (-2 ，2) ， 请设计程序框图，î2 ， x Î[2 + ¥)．10．计算 f ( x) = 2 x 4 + 3x 3 + 5x - 4当x = 3 时多项式的值，需要次加法运算，（ ） 次乘法运算,此多项式写成算法语句为（ ）。
三．解答题11.执行右图中程序，回答下面问题1）若输入：m=888,n=1147，则输出的结果为：________（2）画出该程序的程序框图x -ì-2 x - 4 ， Î (-¥ ， 2] ，ïï x-1要求从键盘输入 x，输出 y并写出计算机程序13． 已知 S=12－22＋32－42＋„„＋(n－1)2－n2，请设计程序框图，算法要求从键盘输入 n，输出 S并写出计算机程序14. 按如图所示的流程图操作．（Ⅰ）操作结果得到的数集是什么？如果把依次产生的数第 9 题INPUT“m=”;mINPUT“n=”;nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND第 11 题图开始看成是数列{a } 的项，试写出其通项公式．n（Ⅱ）如何变更 A 框，能使操作流程图产生的数分别是数列 {2n - 2} 的前 10 项？AB写下 1对前一个数加 2写下结果你已写下了10 个数吗？Y结束N15.到银行办理个人异地汇款（不超过 100 万元）时， 银行要收取一定的手续费汇款额不超过 100 元，收取 1 元手续费；超过 100 元但不超过 5000 元，按汇款额的 1% 收取；超过 5000 元，一律收取 50 元手续费。
设计算法求汇款额为 x 元时，银行收取的手续费 y 元画出流程图并写出程序16．求122 232n 21000 成立的 n 的最大整数值，画出程序框图，并写程序17.某城市现有人口总数为 100 万人，如果年自然增长率为 1.2%，试解答下列问题：（1）写出该城市人口数 y（万人）与年份 x（年）的函数关系式（2）用程序表示计算 10 年以后该城市人口总数的算法；（3）用流程图表示计算大约多少年以后该城市人口将达到 120 万人的算法参考答案一、 选择题 BDDCA或二、 6. 4 7. 7.75 8. 3 9. n>20( 者 i>10)x-410. 4,4,f(x)=2*x^4+3*x^3+5*三、11． 37开始输入两个正整数m ，nm>n?否是 x=nn=mm=xr=m MOD n n=rm=nr=0? 否是输出n结束开始输入 xx £ -2Y2．3 ．解：input xif x<=-2 Theny=-2*x-4elseif -2 < x < 2 Theny=SQR(x+1)Yy= x + 1 xN-2 < x < 2Ny=2 x-1y=-2x-4由表达式规律可知，输入的 nelsey=2^(x-1)end ifend ifprint yend输出 y必须为偶数。
结束程序框图为：13.开始i =1，S =0输入 n否n mod 2 =0 ？是i <= n ？否i = i＋1S = S＋ i是输出错误信息输出 S结束14．解：（Ⅰ）{1,3,5,7,9,11,13,15,17,19} ，通项公式为 a = 2n - 1， n ÎN*，且 n≤10．注：程序框图也可以不对 n 进行奇数和偶数的讨论，直接进入循环n（Ⅱ）变更 A 框为：写下 0，这时操作流程图，可依次得：0，2，4，„，18，恰好为数列通项公式为{2n - 2} 的前 10 项．15．先写出函数，此题为一分段函数程序略开始输入 x0