书山有路第十一章算法初步与框图 理 一 知识网络 算法初步 算法与程序框图 算法语句 算法概念 框图的逻辑结构 输入语句 循环语句 条件语句 输出语句赋值语句算法案例二 考纲要求算法的含义 程序框图了解算法的含义 了解算法的思想 理解程序框图的三种基本逻辑结构 顺序 条件分支 循环 基本算法语句理解几种基本算法语句 输入语句 输出语句 赋值语句 条件语句 循环语句的含义 三 复习指南本章是新增内容 多以选择题或填空题形式考查 常与数列 函数等知识联系密切 考查的重点是算法语句与程序框图 以基础知识为主 如给出程序框图或算法语句 求输出结果或说明算法的功能 或写出程序框图的算法语句 判断框内的填空等考查题型 难度层次属中偏低 第一节算法与程序框图 知识回顾算法的概念 算法通常是指按一定规则解决某一类问题的明确和有限的步骤 程序框图又称流程图 是一种用程序框 流程线及文字说明来表示算法的图形 程序框图的三种基本逻辑结构是顺序结构 条件结构 循环结构 算法的描述方式有 自然语言 程序框图 程序语言 算法的基本特征 明确性 算法的每一步执行什么是明确的 顺序性 算法的 前一步 是 后一步 的前提 后一步 是 前一步 的继续 有限性 算法必须在有限步内完成任务 不能无限制的持续进行 通用性 算法应能解决某一类问题 典例精析例1 如图所示是一个算法的程序框图 则该程序框图所表示的功能是 顺序结构 循环结构 条件结构 1 书山有路 解析 首先要理解各程序框的含义 输入a b c三个数之后 接着判断a b的大小 若b小 则把b赋给a 否则执行下一步 即判断a与c的大小 若c小 则把c赋给a 否则执行下一步 这样输出的a是a b c三个数中的最小值 所以该程序框图所表示的功能是求a b c三个数中的最小值 评注 求a b c三个数中的最小值的算法设计也可以用下面程序框图来表示 例2 下列程序框图表示的算法功能是 计算小于100的奇数的连乘积计算从1开始的连续奇数的连乘积计算从1开始的连续奇数的连乘积 当乘积大于100时 计算奇数的个数 4 计算1 3 5 n 100成立时n的最小值 解析 为了正确地理解程序框图表示的算法 可以将执行过程分解 分析每一步执行的结果 可以看出程序框图中含有当型的循环结构 故分析每一次循环的情况 列表如下 第一次 S 1 3 i 5 2 书山有路第二次 S 1 3 5 i 7 第三次 S 1 3 5 7 i 9 此时S 100不成立 输出结果是7 程序框图表示的算法功能是求使 1 3 5 n 100成立时n的最小值 选D yx 评注 通过列表 我们能清楚了解程序的每一步中的各个变量是怎样变化的 这正是程序运行的本质所在 本题若要求编写求使1 3 5 n 100成立时n的最小值的程序框图或程序时 很容易弄错输出的结果 应注意 例3 在音乐唱片超市里 每张唱片售价为25元 顾客如果购买5张以上 含5张 唱片 则按九折收费 如果购买10张以上 含10张 唱片 则按八折收费 请设计算法步骤并画出程序框图 要求输入张数x 输出实际收费y 元 x 5 25x y 22 5x 5 x 10 20 x x 10 再利用条件结构画程序框图 分析 先写出与之间的函数关系式 有解 算法步骤如下 第一步 输入购买的张数x 第二步 判断x是否小于5 若是 计算y 25x 否则 判断x是否小于10 若是 计算y 22 5x 否则 计算y 20 x 第三步 输出y 程序框图如下 评注 凡必须先根据条件做出判断 然后再决定进行哪一个步骤的问题 在画程序框图时 必须引入判断框 采用条件结构设计算法 如果变量分三级 或以上 时 就需要用到条件结构的嵌套 不能忽视结果中 是 否 的书写 否则不知道执行哪一条路径 一般地 分n段的分段函数 需要引入n 1个判断框 条件结构有以下两种基本类型 3 书山有路 1 2232 1002 1 1 1 的 例4 画出求 值的程序框图 分析 这是一个有规律的数列求和问题 每次都进行了相同的运算 故应用循环结构进行算法设计 解 程序框图如下 1 当型循环 2 直到型循环 评注 1 解题关键是选择好计数变量i和累加变量S的初始值 并写出用i表示的数列的通项公式是 2 循环结构主要用在一些有规律的重复计算的算法中 如累加求和 累乘求积等问题 在循环结构中 要注意根据条件 设计合理的计数变量 累加 积 变量以及它们的初始值等 特别要注意循环结构中条件的表述要恰当 精确 以免出现多一次或少一次循环 3 循环结构分为两类 一类是当型循环结构 如下左图所示 另一类是直到型循环结构 如下右图所示 变式训练画出求 1 4272 1 1 1 1002的值的程序框图 4 书山有路 解 程序框图如下 例5 某工厂2005年的生产总值为200万元 技术改进后预计以后后每年的年生产总值都比上一年增长5 设计一个程序框图 输出预期年生产总值超过300万元的最早年份及2005年到此年份之前 不包此年份 的年生产总值的和 分析 本例可用循环结构来实现 1 确定 循环体 设a为某年的年生产总值 n为年份 S为年产值的总和 则循环体为S S a a a 0 05a n n 1 初始化变量 n的初始值为2005 a的初始值为200 S的初始值为0 设定循环控制条件 a 300解 程序框图如下 5 书山有路 评注 本问题的关健是设计好循环体 注意S S a与n之间的对应关系 本题若将S S a放在n n 1之后 则输出时须重新赋值n n 1 否则n的值为超过300万的年份的下一年 本题也可用当型循环结构来表示 变式训练 设计一个程序框图 求使S 1 2 3 n 5000的最小n的值 并输出此时S的值 解 程序框图如下 6 书山有路 基础自测一 选择题1 下列说法正确的是 A 算法就是某个问题的解题过程 B 算法执行后可以产生不同的结果 解决某一个具体问题算法不同结果不同 算法执行步骤的次数不可以很大 否则无法实施 解析 选项A 算法不能等同于解法 选项B 例如 判断一个正整数是否为质数 结果为 是质数 和 不是质数 两种 选项C 解决某一个具体问题算法不同结果应该相同 否则算法构造的有问题 选项D 算法可以为很多次 但不可以无限次 选B 2 如图所示的程序框图中 则第3个输出的数是 32 A 1B C 2D 52 32 解析 前3个分别输出的数是1 2 2 故选C 开始 A 12 N 1 A A 12 N N 1 结束 N 4 是 否 输出A 7 书山有路 46 1 1 1 1 3 如图给出的是求220的值的一个程序框图 2 3 解析 通过列表 我们能清楚了解程序的每一步中的各个变量i 1 S 1 n 4 是怎样变化的 第一次 第二次 i 2 S 1 1 n 624 依此可知循环的条件是i 10 选 4 2007年高考山东卷 阅读右边的程序框图 若输入的n是100 则输出的变量S和T的值依次是 A 2550 2500B 2550 2550C 2500 2500D 2500 2550 其中判断框内应填入的条件是 A i 10 B i20 D i 20 开始 S 0 n 2 i 1 S S 1n n n 2 i i 1 否是输出S结束 8 书山有路 S 0 T 0 T T n S S n 结束4 解析 依据框图可得S 100 98 96 2 2550 T 99 97 95 1 2500 选A 5 2006年1月份开始实施的 个人所得税法 规定 全月总收入不超过1600元的免征个人工资 薪金所得税 超过1600元部分需征税 设全月总收入金额为x元 前三级税率如下左表所示 是 n 2 否输出S T 开始输入n n n 1 n n 1 9 书山有路 当工资薪金所得不超过3600元 计算个人所得税的一个算法框图如图 则输出 输出 分别为 A 0 05x 0 1xC 0 05x 80 0 1x B 0 05x 0 1x 185D 0 05x 80 0 1x 185 5 解析 设全月总收入金额为x元 所得税额为y元 则y与x之间的函数关系为 0 0 x 1600 y x 1600 5 1600 x 2100 25 x 2100 10 2100 x 3600 选D 二 填空题6 2008年高考山东卷 执行右边的程序框图 若p 0 8 则输出的n 6 解析 第一次循环后 S 1 0 82 此时n 2 第二次循环后 S 1 1 0 824 此时n 3 第三次循 开始输入x 输出0 输出 输出 0 x 1600 否 10 1600 x否 2100 x否结束 是 是 是 书山有路 环后 S 1 1 1 0 8248 此时n 4 输出 故填4 7 2008年高考江苏卷 某地区为了解70 80岁的老人的日平均睡眠时间 单位 h 随机选择了50位老人进行调查 下表是这50位老人睡眠时间的频率分布表 8 如果执行右面的程序框图 那么输出的S 在上述统计数据的分析中一部分计算见算法流程图 则输出的S的值为 解析 由流程图S G1F1 G2F2 G3F3 G4F4 G5F5 4 5 0 12 5 5 0 20 6 5 0 40 7 5 0 2 8 5 0 08 6 42故填6 42 开始 S 0 输入Gi Fi i 1 S S Gi Fi i i 1 NY输出S结束 11 书山有路 100 2550 8 解析 S 2 4 6 三 解答题 9 请阅读下面程序框图 说明此程序的功能 2 12 解 程序功能是求s的值 s 1 2 22 26 并输出s x 2 2 x 0 y 4 x 0 x 2 x 0 请画出程序框图 要求输入自变量x的值 10 已知函数输出函数值y 10 解 书山有路 100的程序框图 11 画出一个计算1 5 10 15 11解 程序框图如下 12 甲 乙两位同学为解决数列求和问题 试图编写一程序 两人各自编写的程序框图分别如图1和如图 13 i 0 S 0 i i 1 S S 2 输出S 结束 i n 否 是 图1 书山有路2 根据图1和图2 试判断甲 乙两位同学编写的程序框图输出的结果是否一致 当n 20时分别求它们输出的结果 若希望通过对图2虚框中某一步 或几步 的修改来实现 求首项为2 公比为3的等比数列的前n项和 请你给出修改后虚框部分的流程图 开始开始输入n输入n i 1 S 0 a 2 S S a a a 2 i i 1 i n 是 否 输出S结束图212 解 输出结果一致 当n 20时 图1的结果为2 4 6 38 40 2 1 2 3 20 420图2的结果为2 4 6 38 40 2 1 2 3 20 420 修改后虚框部分的流程图为S S aa 3 ai i 1 14 书山有路第二节算法的基本语句及算法案例 知识回顾1 任何一种程序设计语言都包含五种基本的算法语句 它们是输入语句 输出语句 赋值语句 条件语句 循环语句 THEN 2 输入语句的一般格式是INPUT 提示内容 变量 输出语句的一般格式是PRINT 提示内容 表达式 赋值语句的一般格式是变量 表达式 IF条件 语句体1IF条件THENELSE语句体语句体2条件语句的一般格式是ENDIF或ENDIF DO 循环体 WHILE条件循环体 循环语句的一般格式是LOOPUNTIL条件和 WEND 输入语句 输出语句 赋值语句基本对应于程序框图中的顺序结构 条件语句 循环语句分别用来表达程序框图中的条件结构和循环结构 3 常用符号运算符号 加 减 乘 除 乘方a b 整数取商 求余数MOD 逻辑符号 且AND 或OR 大于 等于 小于 小于等于 常用函数 绝对值ABS 平方根SQR 取整INT 4 算法案例 1 辗转相除法和更相减损术辗转相除法和更相减损术都是求两个正整数的最大公约数的方法 辗转相除法就是对于给定的两个正整数 用大数除以小数 若余数不为0 则将小数和余数构成新的一对数 继续上面的除法 反复执行此步骤 直到大数被小数除尽 则这时较小的数就是原来两个数的最大公约数 更相减损术就是