算法的概念 (4).ppt

1 1算法与程序框图 1 1 1算法的概念 同煤一中数学组李勇 1 要把水果装入冰箱分几步 2 假设家中生火泡茶有以下几个步骤 a 生火b 将水倒入锅中c 找茶叶d 洗茶壶茶碗e 用开水冲茶请选出一个最优算法 A abcdeB bacdeC cadbeD dcabe 思考1 在初中 对于解二元一次方程组你学过哪些方法 加减消元法和代入消元法 思考2 用加减消元法解二元一次方程组的具体步骤是什么 知识探究 一 算法的概念 4 第一步 得 第二步 解 得 第三步 得 第四步 解 得 思考4 根据上述分析 用加减消元法解二元一次方程组 可以分为五个步骤进行 这五个步骤就构成了解二元一次方程组的一个 算法 我们再根据这一算法编制计算机程序 就可以让计算机来解二元一次方程组 思考5 根据上述分析 你能归纳出算法的概念吗 在数学中 按照一定规则解决某一类问题的明确和有限的步骤称为算法 算法的五个特征 概括性 逻辑性 有穷性 不唯一性 普遍性 1 概括性 写出的算法必须能解决某一类问题 并且能够重复使用 2 逻辑性 算法从初始步骤开始 分为若干明确的步骤 前一步是后一步的前提 只有执行完前一步才能进行下一步 而且每一步都是正确无误的 从而组成了一个有着很强逻辑性的步骤序列 3 有穷性 算法有一个清晰的起始步 终止步是表示问题得到解答或指出问题没有解答 所有序列必须在有限个步骤之内完成 不能无停止地执行下去 4 不唯一性 求解某一个问题的算法不一定只有唯一的一个 可以有不同的算法 当然这些算法有简繁之分 优劣之别 5 普遍性 很多具体的问题 都可以设计合理的算法去解决 例如手算 心算或用算盘 用计算器去计算都要经过有限的 事先设计好的步骤加以解决 同样的一个工作计划 生产流程等都可以视为 算法 思考1 如果让计算机判断7是否为质数 如何设计算法步骤 第一步 用2除7 得到余数1 所以2不能整除7 第四步 用5除7 得到余数2 所以5不能整除7 第五步 用6除7 得到余数1 所以6不能整除7 第二步 用3除7 得到余数1 所以3不能整除7 第三步 用4除7 得到余数3 所以4不能整除7 因此 7是质数 知识探究 二 算法的设计 思考2 如果让计算机判断35是否为质数 如何设计算法步骤 第一步 用2除35 得到余数1 所以2不能整除35 第二步 用3除35 得到余数2 所以3不能整除35 第三步 用4除35 得到余数3 所以4不能整除35 第四步 用5除35 得到余数0 所以5能整除35 因此 35不是质数 第一步 用2除89 得到余数1 所以2不能整除89 第二步 用3除89 得到余数2 所以3不能整除89 第三步 用4除89 得到余数1 所以4不能整除89 第八十七步 用88除89 得到余数1 所以88不能整除89 因此 89是质数 思考3 整数89是否为质数 如果让计算机判断89是否为质数 按照上述算法需要设计多少个步骤 思考4 用2 88逐一去除89求余数 需要87个步骤 这些步骤基本是重复操作 我们可以按下面的思路改进这个算法 减少算法的步骤 1 用i表示2 88中的任意一个整数 并从2开始取数 2 用i除89 得到余数r 若r 0 则89不是质数 若r 0 将i用i 1替代 再执行同样的操作 3 这个操作一直进行到i取88为止 你能按照这个思路 设计一个 判断89是否为质数 的算法步骤吗 用i除89 得到余数r 令i 2 若r 0 则89不是质数 结束算法 若r 0 将i用i 1替代 判断 i 88 是否成立 若是 则89是质数 结束算法 否则 返回第二步 第一步 第四步 第三步 第二步 算法设计 思考5 一般地 判断一个大于2的整数是否为质数的算法步骤如何设计 第一步 给定一个大于2的整数n 第二步 令i 2 第三步 用i除n 得到余数r 第四步 判断 r 0 是否成立 若是 则n不是质数 结束算法 否则 将i的值增加1 仍用i表示 第五步 判断 i n 1 是否成立 若是 则n是质数 结束算法 否则 返回第三步 理论迁移 设函数f x 的图象是一条连续不断的曲线 写出用 二分法 求方程f x 0的一个近似解的算法 算法的设计 设计一个具体问题的算法 通常按以下步骤 1 认真分析问题 找出解决此问题的一般数学方法 2 借助有关变量或参数对算法加以表述 3 将解决问题的过程划分为若干步骤 4 用简练的语言将这个步骤表示出来 算法的特征 概括性 逻辑性 有穷性 不唯一性 普遍性 算法的用途 为计算机服务 练习一 任意给定一个正实数 设计一个算法求以这个数为半径的圆的面积 算法分析 第一步 输入任意一个正实数r 第二步 计算以r为半径的圆的面积S r2 第三步 输出圆的面积 练习二 任意给定一个大于1的