1、第3讲 算法初步、框图【学习目标】1了解算法的含义、了解算法的思想；理解程序框图的三种基本逻辑结构：顺序、条件分支、循环2理解几种基本算法语句输入语句、输出语句、赋值语句、循环语句的含义3初步了解几个典型算法案例4了解程序框图，了解工序流程图(即统筹图)，能绘制简单实际问题的流程图，了解流程图在解决实际问题中的作用；了解结构图，会用结构图梳理已学过的知识、整理收集到的资料信息【基础检测】1下列赋值语句正确的是()A6tBxy5CAB2 Dxx2D2下列图形符合描述正确的是()(1)圆角矩形(2)平行四边形(3)矩形(4)菱形终端框(起止框)计算框 输入、输出框 处理框(执行框)判断框A(1)，
2、(2)，(3)，(4)B(1)，(2)，(3)，(4)C(1)，(2)，(3)，(4)D(1)，(2)，(3)，(4)A3下列程序表示的算法是()A变换 m 和 n 的位置B辗转相除法C更相减损术D秦九韶算法INPUT m，nDO rm MOD n mn nrLOOP UNTIL r0PRINT mENDB4某算法的程序框图如图所示，则输出量 y 与输入实数 x 满足的关系式是y x2，x12x，x15根据如图所示，总经理的直接下属是()A总工程师和专家办公室B开发部C总工程师、专家办公室和开发部D总工程师、专家办公室和所有七个部C【知识要点】1算法与程序框图(1)算法通常指可以用计算机来解决
3、某一类问题的程序或步骤，这些程序或步骤必须是_的，而且能够在有限步之内完成(2)程序框图，又称_，是一种由程序框，流程线及文字说明来表示算法的图形明确和有效流程图2算法的基本逻辑结构(1)顺序结构：按照步骤依次执行的一个算法，如下左图：(2)条件结构：在一个算法中，经常会遇到一些条件的判断，_，条件结构就是处理这种过程的结构，如上右图.(3)循环结构：从某处开始，按一定的条件反复执行某一处理步骤的情况，这就是循环结构反复执行的处理步骤称为_根据给定的条件是否成立有不同的流向循环体循环结构的两种类型：_：在每次循环前进行条件判断，满足条件才循环，不满足则停止，故通常又叫做“是循环”，“while
4、 型循环”；_：在执行了一次循环后，对条件进行判断，不满足才执行循环，满足则停止，故又叫做“否循环”，“until 型循环”如图所示当型循环直到型循环当型循环结构 直到型循环结构3基本算法语句(1)输入、输出语句和赋值语句：输入语句格式：_；输出语句格式：_；赋值语句格式：_(2)条件语句：IFTHEN 格式对应框图IF条件 THEN语句体END IF INPUT“提示内容”；变量PRINT“提示内容”；表达式变量表达式IFTHENELSE 格式对应框图IF条件 THEN语句体1ELSE 语句体2END IF 条件语句的嵌套：条件语句主要用于实现算法中的条件结构，当出现 3 个或 3 个以上的
5、判断点时，就要用到程序嵌套，其一般格式为：IF 条件 1 THEN语句序列 1；ELSEIF 条件 2 THEN语句序列 2ELSE语句序列 3END IFEND IF(3)循环语句：WHILE 语句的格式及对应框图WHILE 条件循环体WEND UNTIL 语句的格式及对应框图DO循环体LOOP UNTIL 条件(4)教科书中出现的程序算术运算符及函数的意义算术运算符乘法：“3*x”表示代数式“3x”；乘方：“3 x”表示代数式“3x”；除法：“a/b”表示代数式“ab”；取商：“x10”表示“把数 x 的十位取出来”；取余：“x MOD 10”表示“x 除以 10 的余数”，即把 x 的个
6、位取出来；“ab”表示“ab”函数SQR()用来求某个非负数的算术平方根，即SQR(x)x；ABS()，用来求某个数的绝对值，即ABS(x)|x|.4算法案例(1)辗转相除法与更相减损术辗转相除法：求两个正整数的最大公约数的方法用较大的数 m 除以较小的数 n 得到余数 r，反复操作，直到余数为 0 为止，即 mntr(0rn)因此要用“后测试型”循环语句表示，其程序如下：INPUT m，nDO rm MOD n mn nrLOOP UNTIL r0PRINT mEND更相减损术是求两个正整数的最大公约数的算法用较大数减去较小数，把所得的差数和较小数构成一对新数，再用较大数减去较小数，以同样的
7、操作一直做下去，直到所得的数相等为止这一过程可由循环语句表达，其程序如下：INPUT a，bWHILE abIF ab THEN aabELSE bbaEND IFWENDPRINT a，bEND(2)秦九韶算法n 次多项式f(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxan1)xan2)xa1)xa0得到递推公式v0an 且 vkvk1xank，其中 k1，2，n其算法可用循环语句来实现(3)进位制将十进制数化为二进制数的算法称为_；将十进制数化为 k 进制数的算法称为除 k 取余法将 k 进制数化为十进制数的算法步骤为：第一步：从左到右依次取 k 进制数
8、anan1a1a0(k)各位上的数字乘以 k 的幂，k 的幂从 n 开始取值，每次递减1，递减到 0，即 ankn，an1kn1，a1k，a0k0；第二步：把所有积加起来，就得到十进制数除2取余法5流程图(1)由一些图形符号和文字说明构成的图示，称为流程图，常用来表示一些动态过程，通常含有一个“起点”，一个或多个“终点”(2)结构图描述系统结构的图示，叫结构图结构图一般由构成系统的若干要素和表达各要素之间关系的连线(或方向箭头)构成，连线通常按照从上到下，从左到右的方向表示要素的从属关系或逻辑的先后关系一、程序框图的识别与应用例1(1)要解决下面的四个问题，只用顺序结构画不出其流程图的是()A
9、利用公式 12nn（n1）2，计算 1210 的值B当圆面积已知时，求圆的周长C当给定一个数 x 时，求其绝对值D求函数 f(x)x24x5 的函数值C【解析】(1)因为求一个数的绝对值需要判断正负，所以必须有判断，故只有顺序结构不行(2)直到型循环结构为()B【解析】(2)直到型循环在执行了一次循环体之后，对控制循环条件进行判断，当条件不满足时执行循环体，满足则停止(3)阅读如图所示的程序框图，若输入的 a、b、c 分别是 21、32、75，则输出的 a、b、c 分别是()A75、21、32B21、32、75C32、21、75D75、32、21A【解析】(3)由程序框图中的各个赋值语句可得x
10、21，a75，c32，b21，故a、b、c分别是75、21、32.【点评】(1)算法与程序框图是算法初步的核心，其中条件结构与循环结构是高考命题的重点，尤其是循环结构的程序框图是历年命题的热点要注意初始值的变化，分清计数变量与累加(乘)变量，掌握循环体等关键环节(2)识别程序框图和完善程序框图是高考的重点和热点解决这类问题：首先，要明确框图中的顺序结构、条件结构和循环结构；第二，要识别运行程序框图，理解框图解决的实际问题；第三，按照题目的要求完成解答对框图的考查常与函数和数列等结合，进一步强化框图问题的实际背景二、基本算法及应用例2(1)执行如图所示的程序框图，若输出的结果是 8，则判断框内
11、m 的取值范围是()A(30，42 B(42，56C(56，72 D(30，72)B【解析】(1)由题知，当输出结果 k8 时，S2(1237)56；当输出结果 k7，S2(1236)42，综合程序框图知，选 B.(2)若下面框图所给的程序运行结果为 S35，那么判断框中应填入的关于 k 的条件是()Ak7?Bk6?Ck6?D【解析】(2)第一次循环，S11，k9；第二次循环，S20，k8；第三次循环；S28，k7；第四次循环，S35，k6，结束循环，输出S35，因此判断框中应填k6.(3)阅读下面的程序，当分别输入 x2、x1、x0 时，输出的 y 值分别为_、_、_INPUT“x”；xIF
12、 x1 THENy1/(x1)ELSEIF x1 THENyx2ELSEyx21/(x1)END IFEND IFPRINT yEND11-1【解析】(3)本题是求分段函数值的问题，由程序可以画出程序框图如所示，所以分别输入 2，1，0 时，输出的 y 值分别为 1，1，1.(4)计算式子 1222232n110 000，求满足上述式子的最小正整数 n 的程序设计如下列三种，试补全下面的程序S1i0WHILE S10 000 ii1 SS2iWENDPRINT1ENDiS0i0WHILE S10 000 SS2i ii1WENDPRINT_ENDi1S0i1WHILE S10 000，所以条件
13、判断后，需执行 SS2i1，ii1，输出的是 i1.【点评】(1)解决算法语句有三个步骤，首先通读全部语句，把它翻译成数学问题；其次领悟该语句的功能；最后根据语句的功能运行程序，解决问题(2)使用循环语句时，要注意循环变量的取值当型(WHILE 型)循环与直到型(UNTIL 型)循环的控制条件是互否的 三、算法案例例3(1)下列关于利用更相减损术求 156 和 72 的最大公约数的说法中正确的是()A都是偶数必须约简B可以约简，也可以不约简C第一步作差为 1567284第二步作差为 728412D以上都不对B【解析】(1)约简是为了使运算更加简捷，故并不一定要约简，故 A 错C 中第二步应为
14、847212.(2)用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果；【解析】(2)用辗转相除法：803628，36844，8420，故80和36的最大公约数是4.用更相减损术检验：80与36均为偶数，先用2约简，约简2次后为20和9，20911，1192，927，725，523，321，211.故80和36的最大公约数为2214，80和36的最大公约数是4.【解析】(3)f(x)x55x410 x310 x25x1(x5)x10)x10)x5)x1，而 x2，所以有 v01，v1v0 xa41(2)53，v2v1xa33(2)104，v3v2xa24(2)102，v4v3xa
15、12(2)51，v5v4xa01(2)11，f(2)1.(3)用秦九韶算法求多项式f(x)x55x410 x310 x25x1当x2时的值；(4)将十进制数2 015转化为八进制的数【解析】(4)2 0153 737(8)【点评】秦九韶算法是多项式求值的优秀算法，其特点是：化高次多项式求值为一次多项式求值；减少了运算次数，提高了效率；步骤重复执行，容易用计算机实现利用秦九韵算法计算多项式的值关键是能正确地将所给多项式改写，然后由内向外逐次计算，由于后项计算用到前项的结果，故应认真、细心，确保中间结果的准确性，若在多项式中有几项不存在，可将这些项的系数看成 0，即把这些项看做0 xn.(5)将八
16、进制数2 015转化为十进制的数【解析】(5)2 015(8)2830821815801 037.四、流程图、结构图的应用例4(1)如图是某教材中集合一章的知识结构图，如果要加入“子集”，则应该放在()A“集合的概念”的下位B“集合的表示”的下位C“基本关系”的下位D“基本运算”的下位C(2)按照如图的工序流程，从零件到成品最少要经过_道加工和检验程序，导致废品的产生有_种不同的情形()A四，三B四，二C三，三D三，二A备选题例5图中的四个图是为计算 2242621002 而绘画制的程序框图根据程序框图回答后面的问题：(1)其中正确的程序框图有哪几个？错误的程序框图有哪几个？错误的要指出错在哪
17、里(2)在错误的程序框图中，按该程序框图所蕴含的算法，能执行到底吗？若能执行到底，最后输出的结果是什么？(3)根据上面的回答总结出应用循环结构绘制程序框图应该注意哪几方面的问题【解析】(1)正确的程序框图只有图，错误的有图.图所示的程序框图中有三处错误 第一处错误，第三个图框中 i42，应该是 i4，因为本程序框图中的累计变量是 i2，不是 i，22，42，1002 中，指数都是 2，而底数 2，4，6，8，100是变化的，但前后两项的底数相差 2，因此计数变量是顺加 2.第二处错误，第四个图框中的内容错误，累加的是 i2 而不是 i，故应改为 ppt2.第三处错误，第五个图框中的内容错误，其
18、中的指令 ii1，应改为 ii2，原因是底数前后两项相差 2.图所示的程序框图中共有四处错误 第一处错误，流程线没有箭头，无法显示程序的执行顺序 第二处错误，第四个图框中的内容 ppi 错，应改为 ppi2.第三处错误，判断框的流程线上没有标明标志是或否的字终 Y 和 N.应在向下的流程线上标注 Y，在向右的流程线上标注 N.第四处错误，在第四个图框和判断框之间漏掉了在循环体中起主要作用的框图，内容即为 ii2，使程序无法退出循环，应在第四个图框和判断框间添加图框 ii2.图所示的程序框图中有一处错误即判断框中的内容错误，应将框内的内容“i100？”且判断框右面和下面的流程线上标注的 Y 和
19、N 互换(2)图虽然能执行到底，但执行的结果不是所期望的结果按照这个程序框图进行运算，最终输出的结果是 p2242(421)(422)(4284)图的程序框图所蕴含的算法无法执行到底 图所示程序虽然能执行到底，但最终输出的结果不是所期望的结果，而是 224262982，少了 1002.(3)应用循环结构解决问题时，特别注意两个变量(累计变量和计数变量)的初始值，及计数变量到底是什么，它递加的值是多大；还要特别注意判断框中计数变量的取值限制，不等号含等号还是不含等号，用大于还是用小于，还是用小于等于1了解算法思想，理解算法含义的关键在于体现程序或步骤的明确性和有效性2深刻理解三种程序框图的属性与
20、特征，需通过实际例子体会算法流程的全过程，认清所解决问题的实质如解决分段函数的求值问题时，一般采用条件结构设计算法；如累加求和，累乘求积等问题，往往包含循环过程，非常适合计算机处理，这类问题很多程序框图都用循环结构进行设计，同时也要注意三种基本结构的共同特点3阅读程序框图应注意：(1)弄清相应操作框的内容；(2)带箭头的流程线及判断框的条件；(3)框内外必要的文字说明和算法功能4编写程序的关键是搞清问题的算法，特别是算法结构，然后确定采用哪一种算法语句注意：在一个赋值语句中，只能给一个变量赋值，赋值号“”的左边只能是变量名，不能是表达式；运用条件语句表示算法时要注意准确判断以及其格式的完整性；
21、循环语句的使用需要明确反复重复的任务，如迭代数列问题；对直到型循环语句要注意把握循环结束的条件5对于实际问题，应先建立函数模型，然后设计算法；解决一些反复执行的有规律的运算任务，如累加求和，累乘求积问题时，可考虑用循环语句编程，也要注意结合其他语句6(1)辗转相除法与更相减损术是求两个正整数的最大公约数的两种方法，关键是掌握这两种算法的操作步骤，计算时应认真、细心，确保中间结果的准确性，因为下一次计算要用到上一次计算的结果(2)利用“除 k 取余法”将十进制数化为 k 进制数时，要把各步所得余数从下到上排，切莫把顺序弄错(3)利用秦九韶算法计算多项式的值的关键是正确地将多项式改写，然后由内向外
22、逐次计算由于下一次计算要用到上一次计算的结果，同样应认真、细致地计算每一步，确保每一步结果的准确性1(2014 全国新课标)执行如图所示的程序框图，如果输入的 x，t 均为 2，则输出的 S()A4 B5 C6 D7D【解析】按照框图中的要求，不断给变量 M，S，k 赋值，直到不满足条件 x2，t2，M1，S3，k1.kt，M1122，S235，k2；kt，M2222，S257，k3；32，不满足条件，输出 S7.2(2014 四川)执行如图所示的程序框图，如果输入的 x，yR，那么输出的 S 的最大值为()A0 B1 C2 D3C【解析】根据程序框图给出的流程求解当条件 x0，y0，xy1不
23、成立时输出 S 的值为 1，当条件x0，y0，xy1 成立时 S2xy，下面用线性规划的方法求此时S 的最大值作出不等式组x0，y0，xy1表示的平面区域如图中阴影部分，由图可知当直线 S2xy 经过点 M(1，0)时 S 最大，其最大值为 2102，故输出 S 的最大值为 2.【点评】算法思想的一种表述形式为程序框图，而具体“算”的过程往往是数列求和“看图说话”看似简单，却需要理解“求和”的实质1以下各数中有可能是五进制数的是()A55 B106 C732 D2 134D【解析】根据五进制数的特点，知五进制数只含有数字 0，1，2，3，4，所以只有 D 中的数有可能是五进制数2下列结构图中要
24、素之间表示从属关系的是()C【解析】A、B、D均为逻辑关系，只有C是从属关系3用秦九韶算法求多项式 f(x)3x64x55x46x37x28x1 在 x0.4 时的值时，需要做的乘法和加法的次数分别是()A6，6 B5，6 C5，5 D6，5【解析】f(x)(3x4)x5)x6)x7)x8)x1，由内向外计算可知，共有 6 次乘法、6 次加法A4用“辗转相除法”求得 168 和 486 的最大公约数是()A3 B4 C6 D16【解析】4862168150，168115018，1508186，1836，6 是 168 与 486 的最大公约数C5用更相减损术求 80 和 36 的最大公约数，需
25、要进行减法的次数为()A8 B7 C6 D5【解析】803644，44368，36828，28820，20812，1284，844.故选 B.B6秦九韶算法求多项式f(x)1235x8x279x36x45x53x6在x4时的值时，v4的值为()A57B220C845D3 392B【解析】v03，v1v0 x57，v2v1x634，v3v2x7957，v4v3x8220.7四位二进制数能表示的最大十进制数是()A4 B15 C64 D127B【解析】1 111(2)123122121120842115.8把“二进制”数1 011 001(2)化为“五进制”数是()A224(5)B234(5)C3
26、24(5)D423(5)C【解析】1 011 001(2)126025124123022021189，891754，17352，3053，89324(5)9若 k 进制数 123(k)与十进制数 38(10)相等，则 k_【解析】解得 k7 或 k5，k 取正整数，k5.510计算机中常用的十六进制逢 16 进 1 的计数制，采用数字 09 和字母 AF 共 16 个计数符号，这些符号写十进制数的对应关系如表：例如，用十六进制表示，EF10(16)，则 AB十六进制0123456789ABCDEF十进制01234567891011121314156E(16)【解析】AB1011110，AB11
27、06E(16)1任何一个算法都必须有的基本结构是()A顺序结构B条件结构C循环结构 D三个都有2在算法的逻辑结构中，要求进行逻辑判断，并根据结果进行不同处理的是哪种结构()A顺序结构B条件结构和循环结构C顺序结构和条件结构D没有任何结构AB3给出以下四个问题，输入一个数 x，输出它的绝对值；求面积为 6 的正方形的周长；求三个数 a，b，c 中 的 最 大 数；求 函 数 f(x)3x1（x0），x21（x0）的函数值其中需要用条件结构来描述算法的有()A1 个B2 个C3 个 D4 个【解析】其中都需要对条件作出判断，都需要用条件结构，用顺序结构即可C4根据下列算法语句，当输入 x 为 60
28、 时，输出y 的值为()输入 xIf x50Then y0.5*xElse y250.6*(x50)End If输出 yA25 B30 C31 D61C【解析】本题考查了算法语句中的选择语句 x6050，y250.6(6050)31，选C，本算法其实是“分段函数求值”问题5根据下边框图，对大于 2 的整数 N，输出的数列的通项公式是()Aan2nBan2(n1)Can2nDan2n1【解析】本题考查了程序框图的相关概念 由循环结构知 a12，a24，a38，代入选项知 C 正确 解题关键是“Sai1”后，“ai2S”即 ai2ai1.C6某程序框图如图所示，现输入如下四个函数，则可以输出的函数
29、是()Af(x)|x|xBf(x)1xCf(x)exexexex Df(x)lgsin xC【解析】由程序框图可知，输出的函数应是奇函数且是有零点的函数A 中 f(x)为奇函数而无零点；B中 f(x)为奇函数无零点；C 中 f(x)为奇函数且零点为 0，符合题意；D 中 f(x)不是奇函数7如图是计算某年级 500 名学生期末考试(满分为 100 分)及格率 q 的程序框图，则图中空白框内应填入()AqNMBqMNCqNMNDqMMND8在工商管理学中，MRP 指的是物资需求计划基本 MRP 的体系结构如图所示从图中你能看出影响基本 MRP 的因主要有库存状态、产品结构、主生产计划9下图是一个
30、算法流程图，其功能为求不等式2n20的最小整数解10国家教育部、体育总局和共青团中央曾共同号召在全国各级各类学校要广泛、深入地开展全国亿万大中小学生阳光体育运动为此某网站于2014年1月18日至24日在全国范围内进行了持续一周的在线调查，随机抽取其中200名大中小学生的调查情况，就每天的睡眠时间分组整理如表所示：序号(i)每天睡眠时间(小时)组中值(mi)频数频率(fi)14，5)4.580.0425，6)5.5520.2636，7)6.5600.3047，8)7.5560.2858，9)8.5200.1069，10)9.540.02(1)估计每天睡眠时间小于8小时的学生所占的百分比约是多少？(2)该网站利用算法流程图(如图)对样本数据作进一步统计分析，求输出的S的值，并说明S的统计意义【解析】(1)由样本数据可知，每天睡眠时间小于8 小时的频率是 P1(0.100.02)0.8888%.由此估计每天睡眠时间小于 8 小时的学生约占88%.(2)输入 m1，f1 的值后，由赋值语句 SSmifi可知，流程图进入一个求和状态 设 aimifi(i1，2，6)，则数列ai的前 i项和为 Ti，则 T64.50.045.50.266.50.307.50.288.50.109.50.026.7，故输出的 S 值为 6.7.S 的统计意义是指被调查者每天的平均睡眠时间，估计为 6.7 小时