高中数学 1.1.1算法与程序框图课件 新人教A版必修3.ppt

1 1算法与程序框图 问题的提出 有一个农夫带一条狼狗 一只羊和一筐白菜过河 如果没有农夫看管 则狼狗要吃羊 羊要吃白菜 但是船很小 只够农夫带一样东西过河 问农夫该如何解此难题 方法和过程 1 带羊到对岸 返回 2 带菜到对岸 并把羊带回 3 带狼狗到对岸 返回 4 带羊到对岸 问题1 请你写出解二元一次方程组的详细求解过程 解方程 第一步 由 1 得 第二步 将 3 代入 2 得 第三步 解 4 得 第四步 将 5 代入 3 得 第五步 得到方程组的解得 解方程 第一步 第二步 第三步 第四步 第五步 得到方程组的解得 广义地说 为了解决某一问题而采取的方法和步骤 就称之为算法 在数学中 按照一定规则解决某一类问题的明确和有限的步骤 称为算法 现在 算法通常可以编成计算机程序 让计算机执行并解决问题 这些程序或步骤必须是明确和有效的 而且能够在有限步之内完成 算法的概念 没有软件的支持 计算机只是一堆废铁而已 软件的核心就是算法 算法的特征 一 确定性 每一步必须有确切的定义 二 有效性 原则上必须能够精确的运行 三 有穷性 一个算法必须保证执行有限步后结束 算法的优缺点 一 缺点 算法一般是机械的 有时需要进行大量重复的计算 二 优点 算法是一种通法 只要按照步骤去做 总能得到结果 广播操图解是广播操的算法 菜谱是做菜的算法 歌谱是一首歌曲的算法 空调说明书是空调使用的算法等 我们身边的算法 算法学的发展 随着科学技术的日新月异 算法学也得到了前所未有的发展 现在已经发展到了各个领域 有遗传算法 排序算法 加密算法 蚁群算法等 与生物学 计算机科学等有着很广泛的联系 尤其是在现在的航空航天中 更是有着更广泛的应用 很多复杂的运算都是借助计算机和算法来完成的 在高端科学技术中有着很重要的地位 科学家王小云主导破解两大密码算法获百万大奖 杨振宁教授为获得 求是杰出科学家奖 的山东大学特聘教授王小云颁发了获奖证书和奖金100万元人民币 表彰其密码学领域的杰出成就 应用举例 例1 1 设计一个算法判断7是否为质数 第一步 用2除7 得到余数1 因为余数不为0 所以2不能整除7 第二步 用3除7 得到余数1 因为余数不为0 所以3不能整除7 第三步 用4除7 得到余数3 因为余数不为0 所以4不能整除7 第四步 用5除7 得到余数2 因为余数不为0 所以5不能整除7 第五步 用6除7 得到余数1 因为余数不为0 所以6不能整除7 因此 7是质数 应用举例 例1 2 设计一个算法判断35是否为质数 第一步 用2除35 得到余数1 因为余数不为0 所以2不能整除35 第二步 用3除35 得到余数2 因为余数不为0 所以3不能整除35 第三步 用4除35 得到余数3 因为余数不为0 所以4不能整除7 第四步 用5除35 得到余数0 因为余数为0 所以5能整除35 因此 35不是质数 任意给定一个大于1的整数n 试设计一个程序或步骤对n是否为质数做出判定 第一步 判断n是否等于2 若n 2 则n是质数 若n 2 则执行第二步 第二步 依次从2 n 1 检验是不是n的因数 即整除n的数 若有这样的数 则n不是质数 若没有这样的数 则n是质数 这是判断一个大于1的整数n是否为质数的最基本算法 用语言描述一个算法 最便捷的方式就是按解决问题的步骤进行描述 每一步做一件事情 应用举例 探究解决 对于区间 a b 上连续不断 且f a f b 0的函数y f x 通过不断地把函数f x 的零点所在的区间一分为二 使区间的两个端点逐步逼近零点 进而得到零点近似值的方法叫做二分法 解决问题 第四步 若f a f m 0 则含零点的区间为 a m 第一步 令 给定精确度d 第二步 给定区间 a b 满足f a f b 0 第三步 取中间点 第五步 判断 a b 的长度是否小于d或者f m 是否等于 将新得到的含零点的仍然记为 a b 否则 含零点的区间为 m b 若是 则m是方程的近似解 否则 返回第三步 解决问题 当d 0 05时 评析 实际上 上述步骤就是在求的近似值 与一般的解决问题的过程比较 算法有以下特征 设计一个具体问题的算法时 与过去熟悉地解数学题的过程有直接的联系 但这个过程必须被分解成若干个明确的步骤 而且这些步骤必须是有效的 算法要 面面俱到 不能省略任何一个细小的步骤 只有这样 才能在人设计出算法后 把具体的执行过程交给计算机完成 练习一 任意给定一个正实数 设计一个算法求以这个数为半径的圆的面积 算法分析 第一步 输入任意一个正实数r 第二步 计算以r为半径的圆的面积S r2 第三步 输出圆的面积 课本5页1 练习二 任意给定一个大于1的正整数n 设计一个算法求出n的所有因数 算法分析 第一步 依次以2 n 1 为除数去除n 判断余数是否为0 若是 则是n的因数 若不是 则不是n的因数 第二步 在n的因数中加入1和n 第三步 输出n的所有因数 课本5页2 练习三 为了加强居民的节水意识 某市制订了以下生活用水收费标准 每户每月用水未超过7m3时 每立方米收费1 0元 并加收0 2元的城市污水处理费 超过7m3的部分 每立方米收费1 5元 并加收0 4元的城市污水处理费 请你写出某户居民每月应交纳的水费y 元 与用水量x m3 之间的函数关系 然后设计一个求该函数值的算法 解 y与x之间的函数关系为 当0 x 7时 当x 7时 解 y与x之间的函数关系为 当0 x 7时 当x 7时 求该函数值的算法分析 第一步 输入每月用水量x 第二步 判断x是否不超过7 若是 则y 1 2x 若否 则y 1 9x 4 9 第三步 输出应交纳的水费y 计算机解决任何问题都要依赖于算法 只有将解决问题的过程分解为若干个明确的步骤 即算法 并用计算机能够接受的 语言 准确地描述出来 计算机才能够解决问题 1 1 2程序框图 问题提出 1 算法的含义是什么 在数学中 按照一定规则解决某一类问题的明确和有限的步骤称为算法 2 算法是由一系列明确和有限的计算步骤组成的 我们可以用自然语言表述一个算法 但往往过程复杂 缺乏简洁性 因此 我们有必要探究使算法表达得更加直观 准确的方法 这个想法可以通过程序框图来实现 知识探究 一 算法的程序框图 思考1 判断整数n n 2 是否为质数 的算法步骤如何 第一步 给定一个大于2的整数n 第二步 令i 2 第三步 用i除n 得到余数r 第四步 判断 r 0 是否成立 若是 则n不是质数 结束算法 否则 将i的值增加1 仍用i表示 第五步 判断 i n 1 是否成立 若是 则n是质数 结束算法 否则 返回第三步 i i 1 思考2 为了使算法的程序或步骤表达得更为直观 我们更经常地用图形方式来表示它 程序框图又称流程图 是一种用规定的图形 指向线及文字说明来准确 直观地表示算法的图形 通常 程序框图由程序框和流程线组成 一个或几个程序框的组合表示算法中的一个步骤 流程线是方向箭头 按照算法进行的顺序将程序框连接起来 思考3 基本的程序框和它们各自表示的功能 终端框 起止框 表示一个算法的起始和结束 输入 输出框 表示一个算法输入和输出的信息 处理框 执行框 判断某一条件是否成立 成立时在出口处标明 是 或 Y 不 成立时标明 否 或 N 判断框 赋值 计算 流程线 连接程序框 连接点 连接程序框图的两部分 设n是一个大于2的整数 一般用i i 1表示 i i 1 说明 i表示从2 n 1 的所有正整数 用以判断例1步骤2是否终止 i是一个计数变量 有了这个变量 算法才能依次执行 逐步考察从2 n 1 的所有正整数中是否有n的因数存在 思考4 通过上述算法的两种不同表达方式的比较 你觉得用程序框图来表达算法有哪些特点 用程序框图表示的算法更加简练 直观 流向清楚 顺序结构 思考 5 用程序框图来表示算法 有几种不同的基本逻辑结构 条件结构 循环结构 知识探究 二 算法的顺序结构 思考1 任何一个算法各步骤之间都有明确的顺序性 在算法的程序框图中 由若干个依次执行的步骤组成的逻辑结构 称为顺序结构 用程序框图可以表示为 思考2 若一个三角形的三条边长分别为a b c 令 则三角形的面积 你能利用这个公式设计一个计算三角形面积的算法步骤吗 第一步 输入三角形三条边的边长a b c 第二步 计算 第三步 计算 第四步 输出S 思考3 上述算法的程序框图如何表示 例1一个笼子里装有鸡和兔共m只 且鸡和兔共n只脚 设计一个计算鸡和兔各有多少只的算法 并画出程序框图表示 顺序结构 理论迁移 算法分析 第一步 输入m n 第二步 计算鸡的只数 第三步 计算兔的只数y m x 第四步 输出x y 程序框图 例2已知下图是 求一个正奇数的平方加5的值 的程序框图 若输出的数是30 求输入的数n的值 练习 1 就 1 2 两种逻辑结构 说出各自的算法功能 2 答案 1 求直角三角形斜边长 2 求两个数的和 2 已知梯形上底为2 下底为4 高为5 求其面积 设计出该问题的流程图 开始 结束 顺序结构的程序框图的基本特征 顺序结构知识小结 2 各程序框从上到下用流程线依次连接 1 必须有两个起止框 穿插输入 输出框和处理框 没有判断框 3 处理框按计算机执行顺序沿流程线依次排列 条件结构 r 0 N不是质数 n是质数 是 否 知识探究 三 算法的条件结构 条件结构 在一个算法中 经常会遇到一些条件的判断 算法的流向根据条件是否成立有不同的流向 条件结构就是处理这种过程的结构 课本例4 任意给定3个正实数 设计一个算法 判断分别以这3个数为三边边长的三角形是否存在 画出这个算法的程序框图 算法分析 第一步 输入3个正实数a b c 第二步 判断a b c a c b b c a是否同时成立 若是 则能组成三角形 若否 则组不成三角形 程序框图 开始 输入a b c a b c a c b b c a是否同时成立 是 存在这样的三角形 不存在这样的三角形 否 结束 练习1 城区一中学生数学模块学分认定由模块成绩决定 模块成绩由模块考试成绩和平时成绩构成 各占50 若模块成绩大于或等于60分 获得2学分 否则不能获得学分 为0分 设计一算法 通过考试成绩和平时成绩计算学分 并画出程序框图 算法步骤如下 课本例5 开始 输入a b c X1 p q X2 p q 输出x1 x2 输出 方程没有实数根 输出p 结束 否 是 否 是 是 练习2 设计一个求任意数的绝对值的算法 并画出程序框图 算法分析 第一步 输入数x 第二步 判断x 0是否成立 若是 则 x x 若否 则 x x 程序框图 开始 输入x x 0 输出x 否 输出 x 结束 练习3 画程序框图 对于输入的x值 输出相应的y值 开始 程序框图 x 0 是 y 0 否 0 x 1 是 y 1 否 y x 输出y 结束 输入x 练习4 为了加强居民的节水意识 某市制订了以下生活用水收费标准 每户每月用水未超过7m3时 每立方米收费1 0元 并加收0 2元的城市污水处理费 超过7m3的部分 每立方米收费1 5元 并加收0 4元的城市污水处理费 请你写出某户居民每月应交纳的水费y 元 与用水量x m3 之间的函数关系 然后设计一个求该函数值的算法 并画出程序框图 解 y与x之间的函数关系为 当0 x 7时 当x 7时 解 y与x之间的函数关系为 当0 x 7时 当x 7时 算法分析 第一步 输入每月用水量x 第二步 判断x是否不超过7 若是 则y 1 2x 若否 则y 1 9x 4 9 第三步 输出应交纳的水费y 开始 输入x 0 x 7 是 y 1 2x 否 y 1 9x 4 9 输出y 结束 程序框图 练习5 1 就逻辑结构 说出其算法功能 2 此为某一函数的求值程序图 则满足该流程图的函数解析式为 不能写成分段函数 3 求函数的值的算法流程图 开始 输入x X 2 y 2 输出y 结束 是 答案 1 求两个数中的最大值 答案 2 y x 3 1 作业 P20页A组1 画出程序框图 作业 设计房租收费的算法 其要求是 住房面积80平方米以内 每平方米收费3元 住房面积超过80平方米时 超过部分 每平方米收费5元 输入住房面积数 输出应付的房租 作业 设计房租收费的算法 其要求是 住房面积80平方米以内 每平方米收费3元 住房面积超过80平方米时 超过部分 每平方米收费5元 输入住房面积数 输出应付的房租 算法分析 第一步 输入住房面积S 第二步 根据面积选择计费方式 如果S小于或等于80 则租金为M s 3 否则为M 240 S 80 5 第三步 输出房租M的值 课本50页1 1 课堂讲评 开始 程序框图 x 0 是 y 0 否 0 x 1 是 y 1 否 y x 输出y 结束 输入x 上交作业 课本P50页A组1 2 画出程序框图 P 50页A组T1 2 开始 程序框图 x 0 是 y x 2 2 否 x 0 是 y 4 否 输出y 结束 输入x y x 2 2 循环结构 i i 1 i n 1 或r 0 否 是 求n除以i的余数r 循环结构 在一些算法中 也经常会出现从某处开始 按照一定条件 反复执行某一步骤的情况 这就是循环结构 知识探究 四 算法的循环结构 引例 设计一算法 求和 1 2 3 100 第一步 确定首数a 尾数b 项数n 第二步 利用公式 总和 首数 尾数 项数 2 求和 第三步 输出求和结果 算法1 课本例6 设计一个计算1 2 3 100的值的算法 并画出程序框图 算法分析 第1步 0 1 1 第2步 1 2 3 第3步 3 3 6 第4步 6 4 10 第100步 4950 100 5050 第 i 1 步的结果 i 第i步的结果 各步骤有共同的结构 为了方便有效地表示上述过程 我们引进一个变量S来表示每一步的计算结果 从而把第i步表示为S S i S 0S S 1S S 2S S 3 S S 100 求和 1 2 3 100 S S i 怎么用程序框图表示呢 思考1 i有什么作用 S呢 S 0S S 1S S 2S S 3 S S 100 累加变量S来表示每一步的计算结果 从而把第i步表示为S S i S的初始值为0 i依次取1 2 100 由于i同时记录了循环的次数 所以i称为计数变量 解决方法就是加上一个判断 判断是否已经加到了100 如果加到了则退出 否则继续加 试分析两种流程的异同点 直到型结构 当型结构 i 100 i 100 请填上判断的条件 程序框图 开始 i 1 S 0 S S i i i 1 i 100 是 输出S 结束 否 直到型循环结构 开始 i 1 S 0 i 100 是 S S i i i 1 否 输出S 结束 当型循环结构 思考2 若将 i 1 改成 i 0 则程序框图怎么改 直到型循环结构 当型循环结构 思考 3 将步骤A和步骤B交换位置 结果会怎样 能达到预期结果吗 为什么 要达到预期结果 还需要做怎样的修改 答 达不到预期结果 当i 100时 没有退出循环 i的值为101加入到S中 修改的方法是将判断条件改为i 100 Until 直到型 循环 说明 1 循环结构分为两种 当型和直到型 当型循环在每次执行循环体前对循环条件进行判断 当条件满足时执行循环体 不满足则停止 当条件满足时反复执行循环体 直到型循环在执行了一次循环体之后 对控制循环条件进行判断 当条件不满足时执行循环体 满足则停止 反复执行循环体 直到条件满足 2 注意 循环结构不能是永无终止的 死循环 一定要在某个条件下终止循环 这就需要条件结构来作出判断 因此 循环结构中一定包含条件结构 说明 一般地 循环结构中都有一个计数变量和累加变量 计数变量用于记录循环次数 同时它的取值还用于判断循环是否终止 这个变量的取值一般都含在执行或终止循环体的条件中 累加变量用于输出结果 累加变量和计数变量一般是同步执行的 累加一次 记数一次 结束 输出S i 0 S 0 开始 i i 1 S S i i n 否 是 输入n 改进上面的算法 表示输出1 1 2 1 2 3 1 2 3 n 1 n 的过程 练习巩固 1 设计一算法 求积 1 2 3 100 画出流程图 思考 该流程图与前面的课本例6中求和的流程图有何不同 课本例7 某工厂2005年的年生产总值为200万 技术革新以后每年的年生产总值比上一年增长5 设计一个程序框图 输出预计年生产总值超过300万元的最早年份 算法分析 第一步 输入2005年的年生产总值 第二步 计算下一年的年生产总值 第三步 判断所得的结果是否大于300 若是 则输出该年的年份 否则 返回第二步 由于 第二步 是重复操作的步骤 所以可以用循环结构来实现 我们按照 确定循环体 初始化变量 设定循环控制条件 的顺序来构造循环结构 2 初始化变量 若将2005年的年生产总值堪称计算的起始点 则n的初始值为2005 a的初始值为200 3 设定循环控制条件 当 年生产总值超过300万元 时终止循环 所以可通过判断 a 300 是否成立来控制循环 1 确定循环体 设a为某年的年生产总值 t为年生产总值的年增长量 n为年份 则循环体为 程序框图 开始 n 2005 a 200 t 0 05a n n 1 a 300 是 输出n 结束 否 a a t 小结 1 循环结构的特点 2 循环结构的框图表示 3 循环结构有注意的问题 避免死循环的出现 设置好进入 结束 循环体的条件 当型和直到型 重复同一个处理过程 作业 课本P20页A组2