四川省开江县高中数学 第一章 算法初步 1.1.1 算法的概念课件 新人教A版必修3.ppt

1 1 1算法的概念 为什么要学习算法 计算机与算法 在现代社会里 计算机已经成为人们日常生活和工作不可缺少的工具 听音乐 看电影 玩游戏 画卡通画 处理数据 计算机几乎可以是一个全能的助手 你可以用它来做你想做的任何事情 那么 计算机是怎样工作呢 要想弄清楚这个问题 就需要学习算法 算筹 算盘 计算机等从古到今的计算工具的基础都是 算法 算法对我们而言并不陌生 其实我们从小学就开始接触算法 例如 做四则运算要先乘除后加减 从里往外去括号 竖式笔算等都是算法 至于乘法口诀 珠算口诀更是算法的具体体现 后来我们又陆续学习过一元一次方程 一元一次不等式 一元二次方程 一元二次不等式 二元一次方程组的解法 求两个数的最大公因数 解三角形等 这些问题中都蕴含了丰富的算法 第一步 把冰箱门打开第二步 把大象放进去第三步 把冰箱门带上 情境1 把大象放冰箱 统共分几步 情境2 农夫过河问题 有一个农夫带三只狼和三只羚羊过河 只有一条船 同船可以容纳一个人和两只动物 没有人在的时候 如果狼的数量不少于羚羊的数量 狼就会吃掉羚羊 农夫应该如何渡河 河流 第一步 人带两只狼过河 自己返回 第二步 人带一只羊过河 并带两只狼返回 第三步 人带两只羊过河 自己返回 第四步 人带两只狼过河 自己返回 第五步 人带一只狼过河 算法自然语言描述 如何求解二元一次方程组 回顾 归纳它的步骤 第一步 2 得5y 3 第三步 思考 第二步 解 得 第一步 得 第三步 将代入 得 我们从事各种工作和活动 都必须事先想好进行的步骤 然后按部就班地进行才能避免产生错乱 即做每件事情都需要设计出 行动步骤 做数学问题也是按一定步骤进行的 上述步骤构成了解二元一次方程组的算法 我们可以进一步根据这一算法编制计算机程序 让计算机来解二元一次方程组 1 算法的概念 在数学中 算法 通常是指按照一定的规则来解决的某一类问题的明确和有限的步骤 这些步骤必须是明确和有效的 而且能够在有限步之内完成 3 算法的基本思想与特征 2 算法的表示方法 自然语言 程序框图 程序 1 解决某一类问题 2 在有限步之内完成 3 每一步的明确性和有效性 4 每一步具有顺序性 一般性 有限性 确定与可行性 顺序性 一般算法的基本性质有四条 a 有穷性 b 唯一的初始动作 c 每个动作都有唯一的后继动作 d 动作序列终止时 表示问题得到解答或没有解答 练习 判断下列关于算法的说法是否确 1 求解某一类问题的算法是唯一的 2 算法必须在有限步操作之后停止 3 算法的每一步必须是明确的 不能有歧义或模糊 4 算法执行后一定产生确定的结果 例题1 2 设计一个算法 判断35是否为质数 1 设计一个算法 判断7是否为质数 只能被1和自身整除的大于1的整数叫质数 例题1 1 设计一个算法 判断7是否为质数 解 算法分析 由质数的定义 可以这样判断 依次用2 6除7 若它们中有一个能整除7 则7不是质数 否则7是质数 根据以上分析 可以写出如下的算法 第一步 用2除7 余数不为0 第二步 用3除7 余数不为0 得到余数1 2不能整除7 得到余数1 3不能整除7 第三步 用4除7 余数不为0 得到余数3 4不能整除7 第四步 用5除7 余数不为0 得到余数2 5不能整除7 第五步 用6除7 余数不为0 得到余数1 6不能整除7 故7是质数 例题1 2 设计一个算法 判断35是否为质数 解 根据以上分析 可以写出如下的算法 第一步 用2除35 余数不为0 第二步 用3除35 余数不为0 得到余数1 2不能整除35 得到余数2 3不能整除35 第三步 用4除35 余数不为0 得到余数3 4不能整除35 第四步 用5除35 余数为0 得到余数0 5能整除35 故35不是质数 探究 你能写出 判断整数n n 2 是否为质数 的算法吗 算法分析 对于任意的整数n n 2 若用i表示2 n 1 中的任意整数 则 判断n是否为质数 的算法包含下面的重复操作 用i除n 得到余数r 判断余数r是否为0 若为0 则n不是质数 否则将i的值增加1 再执行同样的操作 一直到i的值等于n 1为止 解析 由上述算法分析我们得到判断任意大于2的整数n是否为质数的算法步骤为 第一步 给定大于2的整数n 第二步 令i 2 第三步 用i除n 得到余数r 第四步 判断 r 0 是否成立 若是 则n不是质数 结束算法 否则 将i的值增加1 仍用i表示 第五步 判断 i n 1 是否成立 若成立 则n是质数 结束算法 否则 返回第三步 分析 1 二分法求方程近似解是通过求对应函数的近似零点得到的 所以首先要建立函数 而且要有具体精确度要求 因此第一步应该怎么做 2 二分法分的是什么 3 如何确定新区间的端点 4 如何表达出反复二分区间的过程 例2 用二分法设计一个求方程x2 2 0的近似根的算法 精确度为0 005 例2 用二分法设计一个求方程x2 2 0的近似根的算法 精确度为0 005 第一步 令f x x2 2 给定精确度d 根据以