1.1.1.1.2 程序框图与算法的基本逻辑结构.ppt

1 1算法与程序框图 1 1 1算法的概念 学习目标 通过分析具体问题过程与步骤 体会算法的思想 了解算法的含义 能用自然语言描述解决具体问题的算法 学习重点 难点 通过实例体会算法思想 初步理解算法的含义 第一步 2得 5y 3 第二步 解 得 第三步 将代入 解得 对于一般的二元一次方程组其中也可以按照上述步骤求解 这些步骤就构成了解二元一次方程组的算法 我们可以根据这一算法编制计算机程序 让计算机来解二元一次方程组 算法的概念与特征 算法 algorithm 这个词出现于12世纪 指的是用阿拉伯数字进行算术运算的过程 在数学上 现代意义上的 算法 通常是指可以用计算机来解决的某一类问题的程序或步骤 这些程序或步骤必须是明确和有效的 而且能够在有限步之内完成 说明 1 事实上算法并没有精确化的定义 2 算法虽然没有一个明确的定义 但其特点是鲜明的 不仅要注意算法的程序性 有限性 构造性 精确性的特点 还应该充分理解算法问题的指向性 即算法往往指向解决某一类问题 泛泛地谈算法是没有意义的 算法学的发展 随着科学技术的日新月异 算法学也得到了前所未有的发展 现在已经发展到了各个领域 有遗传算法 排序算法 加密算法 蚁群算法等 与生物学 计算机科学等有着很广泛的联系 尤其是在现在的航空航天中 更是有着更广泛的应用 很多复杂的运算都是借助计算机和算法来完成的 在高端科学技术中有着很重要的地位 科学家王小云主导破解两大密码算法获百万大奖杨振宁教授为获得 求是杰出科学家奖 的山东大学特聘教授王小云颁发了获奖证书和奖金100万元人民币 表彰其密码学领域的杰出成就 例1 任意给定一个大于1的整数n 试设计一个程序或步骤对n是否为质数做出判定 分析 请回顾这个问题的解题过程 算法分析 第一步 判断n是否等于2 若n 2 则n是质数 若n 2 则执行第二步 第二步 依次检验2 n 1 这些整数是不是n的因素 即是不是整除n的数 若有这样的数 则n不是质数 若没有这样的数 则n是质数 说明 用语言描述一个算法 最便捷的方式就是按解决问题的步骤进行描述 每一步做一件事情 若是 则m为所求 例2 用二分法设计一个求方程x2 2 0的近似根的算法 算法分析 设所求近似根与精确解的差的绝对值不超过 0 005 第一步 令f x x2 2 因为f 1 0 所以设a 1 b 2 第二步 令 判断f m 是否为0 第四步 判断 a b 是否成立 若是 则a或b为满足条件的近似根 若否 则返回第二步 点评 1 上述算法也是求的近似值的算法 2 与一般的解决问题的过程比较 算法有以下特征 设计一个具体问题的算法时 与过去熟悉地解数学题的过程有直接的联系 但这个过程必须被分解成若干个明确的步骤 而且这些步骤必须是有效的 算法要 面面俱到 不能省略任何一个细小的步骤 只有这样 才能在人设计出算法后 把具体的执行过程交给计算机完成 计算机解决任何问题都要依赖于算法 只有将解决问题的过程分解为若干个明确的步骤 即算法 并用计算机能够接受的 语言 准确地描述出来 计算机才能够解决问题 练习一 任意给定一个正实数 设计一个算法求以这个数为半径的圆的面积 算法分析 第一步 输入任意一个正实数r 第二步 计算以r为半径的圆的面积S r2 第三步 输出圆的面积 练习二 任意给定一个大于1的正整数n 设计一个算法求出n的所有因数 算法分析 第一步 依次从2 n 1 为除数去除n 判断余数是否为0 若是 则是n的因数 若不是 则不是n的因数 第二步 在n的因数中加入1和n 第三步 输出n的所有因数 练习三 为了加强居民的节水意识 某市制订了以下生活用水收费标准 每户每月用水未超过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 作业 课本P6页T2 只需用自然语言写出算法步骤 1 1 2程序框图 学习目标 1 在具体问题的解决过程中 掌握基本的程序框图的画法 理解程序框图的三种基本逻辑结构 顺序结构 条件结构 循环结构 2 通过模仿 操作 探索 经历通过设计程序框图表达解决问题的算法的过程 学习重点 通过模仿 操作 探索 经历通过设计程序框图表达求解问题的过程 在具体问题解决过程中 理解程序框图的三种基本逻辑结构 学习难点 用程序框图清晰表达含有循环结构的算法 从上节课我们知道 算法可以用自然语言来描述 如例1 为了使算法的程序或步骤表达得更为直观 我们更经常地用图形方式来表示它 设n是一个大于2的整数 一般用i i 1表示 i i 1 说明 i表示从2 n 1 的所有正整数 用以判断例1步骤2是否终止 i是一个计数变量 有了这个变量 算法才能依次执行 逐步考察从2 n 1 的所有正整数中是否有n的因数存在 思考 通过上述算法的两种不同表达方式的比较 你觉得用程序框图来表达算法有哪些特点 用程序框图表示的算法更加简练 直观 流向清楚 程序框图又称流程图 是一种用规定的图形 指向线及文字说明来准确 直观地表示算法的图形 通常 程序框图由程序框和流程线组成 一个或几个程序框的组合表示算法中的一个步骤 流程线是方向箭头 按照算法进行的顺序将程序框连接起来 基本的程序框和它们各自表示的功能如下 终端框 起止框 表示一个算法的起始和结束 输入 输出框 表示一个算法输入和输出的信息 处理框 执行框 判断某一条件是否成立 成立时在出口处标明 是 或 Y 不 成立时标明 否 或 N 判断框 赋值 计算 流程线 连接程序框 连接点 连接程序框图的两部分 顺序结构 用程序框图来表示算法 有三种不同的基本逻辑结构 条件结构 循环结构 程序框图的三种基本的逻辑结构 顺序结构 条件结构 循环结构 1 顺序结构 是由若干个依次执行的处理步骤组成的 这是任何一个算法都离不开的基本结构 例1 已知一个三角形的三边边长分别为2 3 4 利用海伦 秦九韶公式设计一个算法 求出它的面积 画出算法的程序框图 算法分析 第一步 计算p的值 第二步 由海伦 秦九韶公式求出三角形的面积S 第三步 输出S的值 1 顺序结构 是由若干个依次执行的处理步骤组成的 这是任何一个算法都离不开的基本结构 例1 已知一个三角形的三边边长分别为2 3 4 利用海伦 秦九韶公式设计一个算法 求出它的面积 画出算法的程序框图 算法分析 第一步 计算p的值 第二步 由海伦 秦九韶公式求出三角形的面积S 第三步 输出S的值 程序框图 开始 输出S 结束 画出 已知三角形的三边长a b c 求它的面积的程序框图 开始 输出S 结束 输入a b c 返回 已知三角形三边长分别为a b c 则三角形的面积为其中这个公式被称为海伦 秦九韶公式 返回 2 条件结构 在一个算法中 经常会遇到一些条件的判断 算法的流向根据条件是否成立有不同的流向 条件结构就是处理这种过程的结构 例2 任意给定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是否同时成立 是 存在这样的三角形 不存在这样的三角形 否 结束 例3 为了加强居民的节水意识 某市制订了以下生活用水收费标准 每户每月用水未超过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 结束 程序框图 例4 画程序框图 对于输入的x值 输出相应的y值 开始 程序框图 x 0 是 y 0 否 0 x 1 是 y 1 否 y x 输出y 结束 输入x 是 例5 设计一个求任意数的绝对值的算法 并画出程序框图 算法分析 第一步 输入数x 第二步 判断x 0是否成立 若是 则 x x 若否 则 x x 程序框图 开始 输入x x 0 输出x 否 输出 x 结束 返回 作业 课本P20页练习 P21页A组T1 画出程序框图 3 循环结构 在一些算法中 也经常会出现从某处开始 按照一定条件 反复执行某一步骤的情况 这就是循环结构 反复执行的步骤称为循环体 注意 循环结构不能是永无终止的 死循环 一定要在某个条件下终止循环 这就需要条件结构来作出判断 因此 循环结构中一定包含条件结构 例3 设计一个计算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的初始值为0 i依次取1 2 100 由于i同时记录了循环的次数 所以i称为计数变量 程序框图 开始 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 结束 当型循环结构 说明 1 一般地 循环结构中都有一个计数变量和累加变量 计数变量用于记录循环次数 同时它的取值还用于判断循环是否终止 累加变量用于输出结果 累加变量和计数变量一般是同步执行的 累加一次 记数一次 2 循环结构分为两种 当型和直到型 当型循环在每次执行循环体前对循环条件进行判断 当条件满足时执行循环体 不满足则停止 当条件满足时反复执行循环体 直到型循环在执行了一次循环体之后 对控制循环条件进行判断 当条件不满足时执行循环体 满足则停止 反复执行循环体 直到条件满足 程序框图 开始 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 结束 当型循环结构 顺序结构 用程序框图来表示算法 有三种不同的基本逻辑结构 条件结构 循环结构 直到型循环结构 若是 则m为所求 探究 画出用二分法求方程x2 2 0的近似根 精确度为0 005 的程序框图 算法分析 第一步 令f x x2 2 因为f 1 0 所以设a 1 b 2 第二步 令 判断f m 是否为0 第四步 判断 a b 是否成立 若是 则a或b为满足条件的近似根 若否 则返回第二步 否 是 是 否 程序框图 开始 f x x2 2 输入误差 和初值a b f m 0 a m 否 b m a b 1 2 2 输出a和b 结束 输出m 3 1 3 是 是 是 否 程序框图 开始 f x x2 2 输入误差 和初值a b a m 否 b m a b 或f m 0 输出m 结束 课堂小结 本节主要讲述了程序框图的基本知识 包括常用的图形符号 算法的基本逻辑结构 算法的基本逻辑结构有三种 即顺序结构 条件结构和循环结构 其中顺序结构是最简单的结构 也是最基本的结构 循环结构必然包含条件结构 所以这三种基本逻辑结构是相互支撑的 它们共同构成了算法的基本结构 无论怎样复杂的逻辑结构 都可以通过这三种结构来表达 作业 课本P12页A组T2 P40页A组T4 习题练习 是 1 P12页A组T3 程序框图 开始 输入x x 3 否 结束 输入y y 5 y 1 2x 1 4 是 2 P40页A组T3 程序框图 开始 输入t 0 t 3 否 结束 输入y y 0 3 y 0 1t 3 P40页A组T1 1 开始 程序框图 x 0 是 y 0 否 0 x 1 是 y 1 否 y x 输出y 结束 输入x 4 P40页A组T1 2 开始 程序框图 x 0 是 y x 2 2 否 x 0 是 y 4 否 输出y 结束 输入x y x 2 2 开始 i 1 S 0 S S i2 i i 1 i 100 是 输出S 结束 否 直到型循环结构 开始 i 1 S 0 i 100 是 S S i2 i i 1 否 输出S 结束 当型循环结构 5 P12页A组T2 开始 i 1 S 0 S S i i 1 i n 是 输出S 结束 否 直到型循环结构 开始 i 1 S 0 i n 是 S S i i 1 否 输出S 结束 当型循环结构 6 P40页A组T4 输入n 输入n 7 P12BT1 某高中男子体育小组的50m跑成绩 单位 s 为 6 4 6 5 7 0 6 8 7 1 7 3 6 9 7 4 7 5 设计一个算法 从这些成绩中搜出小于6