1、第 3 讲 算法初步、框图【学习目标】1了解算法的含义，了解算法的思想；理解程序框图的三种基本逻辑结构：顺序结构、条件结构、循环结构2理解几种基本算法语句输入语句、输出语句、赋值语句、条件语句、循环语句的含义3初步了解几个典型的算法案例【基础检测】1执行如图所示的程序框图，若输入 A 的值为 2，则输出的 P 值为()CA2 B3 C4 D5【解析】第一次运行，P2，S32，第二次运行，P3，S3213116；第三次运行，P4，S116 14116 162，此时结束循环，故输出的 P 值为 4.故选 C.2阅读如下程序 i1 S0WHILE i1 000 SSi ii1WENDPRINT SE
2、ND i1 000 S0DO SSi ii1LOOP UNTIL i6?Bn7?Cn 8?Dn 9?C【解析】(1)第一次运行，满足条件循环，s211，k2；第二次运行，满足条件循环，s2120，k3；第三次运行，满足条件循环，s2033，k4；第四次运行，满足条件循环，s2(3)410，k5；此时不满足条件，输出 s10，故选 A.(2)若 x37.5，则 x2x3，x1x217，即 p7.5，x1x3.由 x1x217 得 x38.(3)该 流 程 图 的 作 用 是 计 算 分 段 函 数 f(x)2x，x2，2，2，x（，2）（2，）的函数值又输出的函数值在区间14，12 内，x2，1
3、【点评】本题考查了循环结构的程序框图，考查了学生的识图能力以及观察、推理的能力 熟悉基本理论，能识别框图所体现和表述的算法是本例问题求解的关键和切入点同时也体现了“图与式”的转化能力的培养与提升的重要性(4)第一次循环，S1，n3，不满足条件，循环；第二次循环，S134，n5，不满足条件，循环；第三次循环，S459，n7，不满足条件，循环；第四次循环，S9716，n9，满足条件，输出所以判断框内的条件是 n 8，选 C.例2(1)下面方框中为一个求 20 个数的平均数的程序，则在横线上应填的语句为_ i1 S0DO INPUT x SSx ii1LOOP UNTIL_aS/20PRINT aE
4、ND【解析】该算法程序中，使用了 UNTIL 循环语句，按照该种循环特征，当某一次条件满足时，不再执行循环体，跳到 LOOP UNTIL 句的后面，执行其他的语句根据问题要求，应填 i20.i20(2)将下面的程序框图改写为算法语句；下面的算法语句改为程序框图【解析】由程序框图，可得算法语言；由算法语言，得程序框图.【点评】1.在用 WHILE 语句和 UNTIL 语句编写程序解决问题时，一定要注意它们的格式及条件的表述方法WHILE 语句中是当条件满足时执行循环体，而UNTIL 语句中是当条件不满足时执行循环体 2在解决一些需要反复执行的运算任务，如累加求和、累乘求积等问题中应主要考虑利用循
5、环语句来实现【解析】(1)用辗转相除法：37585435 8535215 351525 15350 375 与 85 的最大公约数为 5.三、算法案例例3(1)用辗转相除法或更相减损术求 375 和 85 的最大公约数；(2)用秦九韶算法计算 f(x)x 52 x 43 x 34 x 25 x6 在 x2 时的值；(3)将七进制数 235(7)转化为八进制数用更相减损术：37585290 29085205 20585120 1208535 853550 503515 351520 20155 15510 1055.375 与 85 的最大公约数为 5.(2)f(x)(x2)x3)x4)x5)x
6、6 v 01；v 1v 0 x21224；v 2v 1 x342311；v 3v 2 x4112426；v 4v 3 x5262557；v 5v 4 x65726120.多项式 f(x)在 x2 时的值 f(2)120.(3)先化成十进制，再化成八进制 235(7)272375124 124174(8)，即 235(7)174(8)【点评】掌握三种特殊算法的求解思想和方法是顺利解决问题的前提和必要条件 四、算法思想的实际应用例4某算法的程序框图如图所示，其中输入的变量x 在 1，2，3，24 这 24 个整数中等可能随机产生(1)分别求出按程序框图正确编程运行时输出 y 的值为 i 的概率 P
7、i(i1，2，3)；(2)甲、乙两同学依据自己对程序框图的理解，各自编写程序重复运行 n 次后，统计记录了输出 y 的值为i(i1，2，3)的频数以下是甲、乙所作频数统计表的部分数据甲的频数统计表(部分)运行次数 n输出 y 的值为 1 的频数输出 y 的值为 2 的频数输出 y 的值为3 的频数30146102 1001 027376697乙的频数统计表(部分)运行次数n输出 y 的值为 1 的频数输出 y 的值为 2 的频数输出 y 的值为 3 的频数30121172 1001 051696353当 n2 100 时，根据表中的数据，分别写出甲、乙所编程序各自输出 y 的值为 i(i1，2
8、，3)的频率(用分数表示)，并判断两位同学中哪一位所编写程序符合算法要求的可能性较大；(3)按程序框图正确编写的程序运行 3 次，求输出 y的值为 2 的次数 的分布列及数学期望【解析】(1)变量 x 是在 1，2，3，24 这 24 个整数中随机产生的一个数，共有 24 种可能 当 x 从 1，3，5，7，9，11，13，15，17，19，21，23 这 12 个数中产生时，输出 y 的值为 1，故 P112；当 x 从 2，4，8，10，14，16，20，22 这 8 个数中产生时，输出 y 的值为 2，故 P213；当 x 从 6，12，18，24 这 4 个数中产生时，输出 y的值为
9、3，故 P316，所以，输出 y 的值为 1 的概率为12，输出 y 的值为2 的概率为13，输出 y 的值为 3 的概率为16.(2)当 n2 100 时，甲、乙所编程序各自输出 y 的值为 i(i1，2，3)的频率如下：输出y的值为 1 的频数输出y的值为 2 的频数输出y的值为 3 的频数甲1 0272 1003762 1006972 100 乙1 0512 1006962 1003532 100 比较频率趋势与概率，可得乙同学所编程序符合算法要求的可能性较大(3)随机变量 可能的取值为 0，1，2，3.P(0)C03130233 827，P(1)C1313123249，P(2)C231
10、3223129，P(3)C33133230 127，故 的分布列为 0123P8274929127 所以，E0 8271492293 1271.即 的数学期望为 1.备选题例5根据如图所示的程序框图，将输出的 x，y 的值依次分别记为 x1，x2，x3，xk；y1，y2，y3，yk.(1)分别求数列xk和yk的通项公式；(2)令 zkxkyk，求数列zk的前 k 项和 Tk，其中kN*，k2 015.【解析】(1)由程序框图，知数列xk中，x11，xk1xk2，xk12(k1)2 k1(kN*，k2 015)由程序框图，知数列yk中，yk13yk2，yk113(yk1)yk11yk1 3，y1
11、13.数列yk1是以 3 为首项，3 为公比的等比数列，yk133k13k，yk3k1(kN*，k2 015)(2)Tkx1y1x2y2xkyk 1(31)3(321)(2k1)(3k1)13332(2k1)3k13(2k1)令 Sk13332(2k1)3k，则 3Sk132333(2k1)3k1，得 2Sk323223323k(2k1)3k1 2(3323k)3(2 k1)3 k1 23（13k）133(2k1)3 k1【点评】以程序框图或算法语句为题设条件常与统计问题、数列问题、函数问题综合，求解时关键是将程序框图或算法语句转化翻译3 k16(2k1)3 k1 2(1k)3 k16，Sk(
12、k1)3 k13.又13(2k1)k（12k1）2k 2，Tk(k1)3k13k2.1了解算法思想，理解算法含义的关键在于体现程序或步骤的明确性和有限性2深刻理解算法的三种逻辑结构特征，需通过实际例子体会算法流程的全过程，认清所解决问题的实质如解决分段函数的求值问题时，一般采用条件结构设计算法；如累加求和，累乘求积等问题，往往包含循环过程，非常适合计算机处理，这类问题很多程序框图都用循环结构进行设计，同时也要注意三种基本结构的共同特点3特别提醒的是，程序框图主要包括三个部分：(1)弄清相应操作框的内容；(2)带箭头的流程线及判断框的条件；(3)框内外必要的文字说明和算法功能读懂流程图要从这三方
13、面研究，流程线反映了流程执行的先后顺序，主要看箭头方向，框内外文字说明了操作内容以及流向4(1)辗转相除法与更相减损术是求两个正整数的最大公约数的两种方法，关键是掌握这两种算法的操作步骤，计算时应认真、细心，确保中间结果的准确性，因为下一次计算要用到上一次计算的结果(2)利用“除 k 取余法”将十进制数化为 k 进制数时，要把各步所得余数从下到上排，切莫把顺序弄错(3)利用秦九韶算法计算多项式的值的关键是正确地将多项式改写，然后由内向外逐次计算由于本次计算用到上一次计算的结果，同样应认真、细致地计算每一步，确保每一步结果的准确性1(2014 湖南)执行如图所示的程序框图，如果输入的 t2，2，
14、则输出的 S 属于()DA6，2 B5，1 C4，5 D3，6【命题立意】本题考查应用程序框图研究函数问题，属容易题【解析】当 t2 时，t2(2)219，S936，所以 D 正确 2(2014 江西)阅读如图所示的程序框图，运行相应的程序，则程序运行后输出的结果为()A7B9C10D11B【解析】由程序框图可知，运算过程如下表：SS1否3 Slg 3lg35 lg 51否5 Slg 5lg 57 lg 71否7 Slg 7lg79 lg 91否9 Slg 9lg 911 lg 1112Bs 35Cs 710Ds 45C【解析】第一次循环结束，得 s1 910 910，k8；第二次循环结束，得
15、 s 9108945，k7；第三次循环结束，得 s4578 710，k6，此时退出循环，输出 k6.故判断框内可填 s 710.【命题立意】本题考查程序框图判断框的意义及应用，属中档题 1执行如图所示的程序框图，若 m4，则输出的n 的值为()A9B10C11D12B【解析】程序框图的本质是判断首项为 1，公差为13的等差数列，从第几项开始不小于 m，易知 ann23，由 an4 解得 n10，故输出的 n 的值为 10.故选 B.2阅读如图所示的程序框图，运行相应的程序，当输入 x 的值为25 时，输出 x 的值为()A1B1C3D9C【解析】根据图给的算法程序可知：第一次 x4，第二次 x
16、1，则输出 x2113.3某同学设计下面的程序框图用以计算和式 122232202 的值，则在判断框中应填写()Ai19?Bi19?Ci20?Di21?【解析】由程序框图可知，判断框内填写 i20，这样当 i20 时，S122232202，当 i21 进入判断框后输出 S122232202.C4执行如图所示的程序后，输出的结果为()A13，7B7，4C9，7D9，5【解析】由程序知该算法循环两次 第一步：s2213，i4.第二步：s2519，i7.而 i7 时，循环结束输出 9，7.C5以下给出计算 246100 的值的四个程序，其中正确的是()S1 i2DO i100SS*iii1LOOP
17、UNTIL i100PRINT SEND DA.S1 i2WHILE i100 SS*i ii1WENDPRINT SEND B.S1 i2WHILE i100 SS*i ii1WENDPRINT SEND S1 i2WHILE i100 SS*i ii2WENDPRINT SENDC.D.6执行如图所示的程序框图，若是 i6 时，输出的 S 值为_；若是 i2 015 时，输出的 S 值为_52 014【解析】若是 i6 时当 i1 时，a1cos2 11，S1.当 i2 时，a2cos22 10，S1.当 i3时，a3cos32 11，S112.当 i4 时，a4cos42 12，S224
18、.当 i5 时，a5cos52 11，S415.当 i6 时，a6cos62 10，S5，此时不满足条件输出 S5.若是 i2 015 时因为 aicosi2 1 的周期是224，所以 a1a2a3a44.所以 Sa1a2a2 015503(a1a2a3a4)a2 013a2 014a2 0155034a1a2a32 014.7某人到银行办理个人异地汇款(不超过 100 万元)，银行收取一定的手续费，汇款额不超过 100 元，收取 1 元手续费；超过 100 元但不超过 5 000 元，按汇款额的 1%收取；超过 5 000 元，一律收取 50 元手续费，设计一个描述汇款额 x 元，银行收取手
19、续费 y 元的算法试画出程序框图【解析】要计算手续费，首先要建立汇款额与手续费之间的函数关系式，依题意知 y1，（0 x100）x0.01，（100 x5 000）50，（5 000 x1 000 000）流程图如下图所示【解析】第 1 次下落的高度 h1100 m；第 2 次下落的高度 h212h150 m；第 3 次下落的高度 h312h225 m；第 10 次下落的高度 h1012h9 所以递推关系式是 h1100，hn112hn(n1，2，3，9)8球从 100 m 的高度落下，每次落地后又返跳回原高度的一半，再落下，在第 10 次落地时，小球共经过多少路程？画出程序框图，并设计程序到第 10 次落地时，共经过的路程为 Sh12 h 22 h 32 h 102(h 1h 2h 10)h 1.故可将 S 作为累加变量，i 作为计数变量 程序框图如下 根据以上程序框图，可设计程序如下：S0 h100 i1 WHILE i10 SS2h hh/2 ii1 WEND SS100 PRINT S END