1.1 算法与程序框图算法与程序图框图 .ppt

人教a版高中数学必修3多媒体课件 多思 创新 融合 随着计算科学和信息技术的飞速发展 计算机已经成为人们日常生活中不可缺少的工具 计算机几乎渗透都了生活的各个领域 那么 你知道计算机的工作原理吗 算法是计算机工作的基础 算法的发展推动了计算机的发展 算法的思想已经渗透到社会的方方面面 在以前的学习中 虽然没有出现算法这个名词 但实际上在数学教学中已经渗透了大量的算法思想 如四则运算的过程 求解方程的步骤等等 完成这些工作都需要一系列程序化的步骤 这就是算法的思想 思考 解二元一次方程组 还记得它的解法吗 1 2 得 5y 3 2 解 的 3 将代入 得 解 我们可以对它进行一般化 按照上面步骤求解 可以得到二元一次方程组的一般算法 我们可以根据这一算法编制计算机程序 让计算机自动来完成二元一次方程组的解 怎样解它的出一组解 算法 algorithm 是解题的步骤 可以把算法定义成解一确定类问题的任意一种特殊的方法 在计算机科学中 算法要用计算机算法语言描述 算法代表用计算机用有穷的步骤解决一类问题的明确 有效的方法 算法的每一种运算必须有确定的意义 该种运算应执行何种动作应无二义性 目的明确 一个算法总是在执行了有穷步的运算后终止 即该算法是可达的 现代数学中算法 algorithm 一词即来源于花拉子米的人名花拉子米 algoritmi 约780 850 中世纪阿拉伯数学家 天文学家 生于波斯北部城市花拉子模 卒于巴格达 他对天文历法 地理地图 代数学等方面均有所贡献 要求算法中有待实现的运算都是基本的 每种运算至少在原理上能由人用纸和笔在有限的时间内完成 其主要数学著作有 一是成书于820年左右的 代数学 原名为 阿尔热巴拉和阿尔穆卡巴拉 意为还原与对消 亦即方程两端的移项和同类项合并 是代数学发展史上的重要经典著作 二是 花拉子米算术 介绍了印度传入的十进位值制记数法和以此为基础的算术知识 现代数学中算法一词即来源于这部著作的书名 即花拉子米的人名 代数学 受到希腊数学乃至印度数学的影响 它不仅对阿拉伯数学而且对欧洲数学的发展产生了深远的影响 因此在历史上 花拉子米有 代数学之父 的称号 按照上面的理解 我们可以设计出很多具体的数学问题的算法 例1 任意给定一个大于1的整数n 试设计一个程序或步骤对n是否为质数作出判定 只能被1和它本身整除的大于1的整数 算法分析 根据质数的定义有 第一步 判断n是否被2整除 若n 2 则n是质数 若n 2则执行第二步 第二步 一次从2 n 1检验是不是n的因数 即整除n的数 若有 则n不是质数 若无 则n是质数 这样判断一个大于1的整数是否为质数的最基本的算法 1 任意给定一个大于1的正整数n 设计一个算法求出n的所有因数 步骤 1 以此以1 n整除n 若能整除 则是n的因子 若不能整除 则不是n的因数 练一练 2 输出所有n的因数 你还有其他的算法吗 例2 用二分法设计一个求方程的近似根的算法 1 回顾二分法求解的过程 2 设计误差度 精确度 3 解题步骤 第一步 因为f 1 0 所以设x1 1 x2 2 第三步 若f x1 f m 0 则令x1 m 否则令x2 m 第四步 判断 x1 x2 0 005是否成立 若是 则x1 x2之间的任意实数都看做方程的近似根 否则返回第二步 0 005 第二步 令 判断f m 是否为0 若是 则m即为所求 若否 则继续判断f x1 f m o 于是 开区间 1 4140625 1 41796875 中的实数都是满足条件的原方程的近似根 2 利用最小二乘法求方程在 0 4 上的根的算法 精确到0 001 事实上 例1我们可以用另外一种方法表示 如图所示 标记 flag 0表示n不是质数flag 1表示n是质数 这种方式的表示 我们就叫程序图框 流程图 来表示算法 程序图框要比自然语言来得更准确 直观 方便 通常 程序图框由程序框和流程线组成 一个或几个程序框的组合表示算法中的一个步骤 流程图的方向箭头就是流程的执行方向 为了使算法的表述简洁 清晰 直观 便于检查 以及交流 流程框统一利用下面的形式表示各自的功能 从上面的例1图框可以看到三种不同的结构形式 顺序结构 循环结构 条件结构 顺序结构是指按照书写顺序依次执行的算法结构 数学中常见的作图问题一般都是顺序结构的算法 1 它只有在a执行完的情况下 才去执行b 如例1 只有在完成上一步的基础上 才能执行下一步 2 顺序结构只能处理一些简单的问题 如代入公式求值 求函数值等 不包含判断和重复操作的过程 3顺序结构是最基本的结构 任何结构都含有顺序结构 例3已知三角形的边长分别为 2 3 4 利用海伦 秦九韶公式设计一种算法求出它的面积 已知三角形的三边为a b c则面积 算法设计 开始 结束 开始 结束 输入a b c 3 一个船工要送一匹狼 一只山羊和一棵白菜过河 每次除船工外 只能带一个乘客渡河 并且狼和山羊不能单独在一起 山羊和白菜也不能单独在一起 应该如何渡河 有些问题利用顺序结构我们无法解决 它需要先进行条件判断 判断的结果确定后面的步骤 象这样的结构我们通常称为条件结构 条件结构的算法流程如图所示 在算法中含有一个判断 通过判断来选择执行哪里个流程 一般来讲 数学中需要分类讨论或分段函数问题均要用到条件结构 例4 任意给定3个正实数 设计一种算法判断分别以这3个数为边长的三角形是否存在 画出它的流程框图 算法分析 根据三角形存在的条件 任意两边之和大于第三边 需要用到条件结构 4 通常说一年有365天 它表示地球围绕太阳一周所需要的时间 但事实上 并不是那么精确 根据天文资料 地球围绕太阳一周的时间是365 2422天 称之为天文年 这个误差看似不大 却引起季节和日历之间难以预料的大变动 在历法上规定4年一闰 百年少一闰 四百年多一闰 如何判断一年是否是闰年 请你设计一个算法 解决这个问题 并用流程图描述这个算法 在一些算法中 经常会出现从某处开始 按照一定的条件 反复执行某一处理 如在复利利率的计算问题 这样的结构就是循环结构 反复执行的处理步骤称为循环体 显然 循环结构中一定包含条件结构 在循环结构中 通常有一个起计数作用的变量 这个变量的取值一般都包含在循环体中 通过它来判断是执行循环还是终止循环 我们叫这个变量为循环变量 说明 1循环体是算法的核心 2循环变量控制着循环的开始和结束 3循环体必须有终止条件 例5 设计一个算法1 2 3 100的算法 并画出程序图框 算法分析 只需要利用一个累加变量和一个计数变量 将累加变量从1累加到100 计数变量的值可以从1 100 累加变量sum 计数变量i 5 最近 中国应欧美等发达国家的要求将人民币增值 以保证世界通货的稳定 但是这将不利于我国经济的发展 有关专家研究 我国的通货膨胀 人民币贬值 率保持在3 左右将对我国经济的稳定有利无害 所谓通货膨胀率为3 是指每年消费品的价格增长率为3 在这种情况下 某种品牌的钢琴2004年的价格为10000元 请用流程图描述这种钢琴今后5年的价格变化情况 并输出这5年的价格 说明 1 算法的设计不唯一 2 循环体的设计要注意数与数之间的变化规律 也就是变量之间的关系 3 循环结构大大的简化了算法 循环变量在构造循环结构中发挥了重要作用 这就是 函数思想 4 循环结构又分为2种 当型 while 和直到型 until while型是先判断是否满足条件 满足条件是执行循环体 不满足则停止 until型是先执行循环体在判断条件 不满足条件是执行循环体 满足则停止 小结 算法与程序框图 算法的概念 算法的起源 算法的基本思想 程序图框 相关概念 基本结构 顺序结构 条件结构 循环结构 当型 while 直到型 until 课后练习 1 尺规作图 确定线段的一个5等分点的一种 2 一群小兔一群鸡 两群合到一群里 要数腿共48