111算法的概念

为您服务教育网 1 1 1 1 算法的概念 珠海市斗门和风中学 邝国均 教学目标教学目标 1 了解算法的含义 体会算法的思想 2 能够用自然语言叙述算法 3 掌握正确的算法应满足的要求 4 会写出解线性方程 组 的算法 5 会写出一个求有限整数序列中的最大值的算法 教学重点教学重点 算法的含义 解二元一次方程组和判断一个数为质数的算法设计 教学难点教学难点 把自然语言转化为算法语言 学法与教学用具学法与教学用具 学法 学法 1 写出的算法 必须能解决一类问题 如 判断一个整数 n n 1 是否为质数 求任意一个 方程的近似解 并且能够重复使用 2 要使算法尽量简单 步骤尽量少 3 要保证算法正确 且计算机能够执行 如 让计算机计算 1 2 3 4 5 是可以做到的 但让计算机去执行 倒一杯水 替我理发 等则是做不到的 教学用具教学用具 计算机 TI voyage200 图形计算器 教学过程教学过程 一 本章章头图说明 章头图体现了中国古代数学与现代计算机科学的联系 它们的基础都是 算法 算法作为一个名词 在中学教科书中并没有出现过 我们在基础教育阶段还没有接触算 法概念 但是我们却从小学就开始接触算法 熟悉许多问题的算法 如 做四则运算要先乘 除后加减 从里往外脱括弧 竖式笔算等都是算法 至于乘法口诀 珠算口诀更是算法的具 体体现 广义地说 算法就是做某一件事的步骤或程序 菜谱是做菜肴的算法 洗衣机的使 用说明书是操作洗衣机的算法 歌谱是一首歌曲的算法 在数学中 主要研究计算机能实现 的算法 即按照某种机械程序步骤一定可以得到结果的解决问题的程序 古代的计算工具 算筹与算盘 20 世纪最伟大的发明 计算机 计算机是强大的实现各种算法的工具 例例 1 解二元一次方程组 yx yx 12 12 分析 解二元一次方程组的主要思想是消元的思想 有代入消元和加减消元两种消元的方法 下面用加减消元法写出它的求解过程 解 第一步 2 得 5y 3 为您服务教育网 2 第二步 解 得 5 3 y 第三步 将代入 得 5 3 y 5 1 x 学生探究 对于一般的二元一次方程组来说 上述步骤应该怎样进一步完善 老师评析 本题的算法是由加减消元法求解的 这个算法也适合一般的二元一次方程组的解 法 下面写出求方程组的解的算法 例例 2 写出求方程组的解的算法 0 1221 222 111 baba cybxa cybxa 解 第一步 a1 a2 得 12211221 cacaybaba 第二步 解 得 1221 1221 baba caca y 第三步 将代入 得 1221 1221 baba caca y 11 1 cb y x a 利用 TI voyage200 图形计算器演示 吸引学生的注意力 运行结果 算法算法概念概念 在数学上 现代意义上的 算法 通常是指可以用计算机来解决的某一类问题是程序或 步骤 这些程序或步骤必须是明确和有效的 而且能够在有限步之内完成 说明 1 算法 没有一个精确化的定义 教科书只对它作了描述性的说明 2 算法的特点 1 有限性 一个算法的步骤序列是有限的 必须在有限操作之后停止 不能是无限的 其中输入 a1 1 b1 2 m1 1 a2 2 b2 1 m2 1 当然可输入其它数值 为您服务教育网 3 2 确定性 算法中的每一步应该是确定的并且能有效地执行且得到确定的结果 而不应当是模棱两可 3 顺序性与正确性 算法从初始步骤开始 分为若干明确的步骤 每一个步骤只能有一个确定的后继步骤 前一 步是后一步的前提 只有执行完前一步才能进行下一步 并且每一步都准确无误 才能完成 问题 4 不唯一性 求解某一个问题的解法不一定是唯一的 对于一个问题可以有不同的算法 5 普遍性 很多具体的问题 都可以设计合理的算法去解决 如心算 计算器计算都要经过有限 事先 设计好的步骤加以解决 例题讲评 例题讲评 例例 3 任意给定一个大于 1 的整数 n 试设计一个程序或步骤对 n 是否为质数做出判断 分析 1 质数是只能被 1 和自身整除的大于 1 的整数 2 要判断一个大于 1 的整数 n 是否为质数 只要根据质数的定义 用比这个整数小 的数去除 n 如果它只能被 1 和本身整除 而不能被其它整数整除 则这个数便是质数 解 算法 第一步 判断 n 是否等于 2 若 n 2 则 n 是质数 若 n 2 则执行第二步 第二步 依次从 2 n 1 检验是不是 n 的因数 即整除 n 的数 若有这样的数 则 n 不是质 数 若没有这样的数 则 n 是质数 说明 本算法是用自然语言的形式描述的 设计算法一定要做到以下要求 1 写出的算法必须能解决一类问题 并且能够重复使用 2 要使算法尽量简单 步骤尽量少 3 要保证算法正确 且计算机能够执行 利用 TI voyage200 图形计算器演示 学生已经被吸引住了 例例 4 用二分法设计一个求方程的近似根的算法 02 2 x 分析 该算法实质是求的近似值的一个最基本的方法 2 解 设所求近似根与精确解的差的绝对值不超过 0 005 算法 第一步 令 因为 所以设 x1 1 x2 2 2 2 xxf 02 01 ff 第二步 令 判断 f m 是否为 0 若是 则 m 为所求 若否 则继续判断 2 21 xx m 大于 0 还是小于 0 mfxf 1 第三步 若 则 x1 m 否则 令 x2 m 0 1 mfxf 运行 为您服务教育网 4 第四步 判断是否成立 若是 则 x1 x2之间的任意值均为满足条件的近似005 0 21 xx 根 若否 则返回第二步 说明 按以上步骤 我们将依次得到课本第 4 页的表 1 1 和图 1 1 1 于是 开区间 1 4140625 1 41796875 中的实数都满足假设条件的原方程是近似根 利用 TI voyage200 图形计算器演示 运行结果 练习练习 1 写出解方程 x2 2x 3 0 的一个算法 解 算法算法 1 第一步 移项 得 x2 2x 3 0 第二步 式两边同加 1 并配方 得 x 1 2 4 第三步 式两边开方 得 x 1 2 第四步 解 得 x 3 或 x 1 算法算法 2 第一步 计算方程的判别式判断其符号 22 4 3 16 0 第二步 将 a 1 b 2 c 3 代入求根公式 x 得 x1 3 x2 1 评析 比较两种算法 算法 2 更简单 步骤少 所以利用公式解决问题是最理想 合算的算法 因此在寻求算法的过程中 首先是利用公式 下面设计一个求一般的一元二次方程 ax2 bx c 0 的根的算法如下 第一步 计算 b2 4ac 第二步 若 0 第三步 输出方程无实根 第四步 若 0 为您服务教育网 5 第五步 计算并输出方程根 x1 2 练习练习 2 求 1 3 5 7 9 11 的值 写出其算法 第一步 先求 1 3 得到结果 3 第二步 将第一步所得结果 3 再乘以 5 得到结果 15 第三步 再将 15 乘以 7 得到结果 105 第四步 再将 105 乘以 9 得到 945 第五步 再将 945 乘以 11 得到 10395 即是最后结果 评析 求解某个问题的算法不同于求解一个具体问题的方法 算法必须能够解决一类问 题 并且能够重复使用 算法过程要能一步一步地执行 每一步操作必须确切 能在有 限步后得出结果 练习练习 3 有蓝和黑两个墨水瓶 但现在却错把蓝墨水装在了黑墨水瓶中 黑墨水错装在 了蓝墨水瓶中 要求将其互换 请你设计算法解决这一问题 分析 由于两个墨水瓶中的墨水不能直接交换 故可以考虑通过引入第三个空墨水 瓶的办法进行交换 解 算法步骤如下 第一步 取一只空的墨水瓶 设其为白色 第二步 将黑墨水瓶中的蓝墨水装入白瓶中 第三步 将蓝墨水瓶中的黑墨水装入黑瓶中 第四步 将白瓶中的蓝墨水装入蓝瓶中 第五步 交换结束 评析 对于这种非数值性问题的算法设计问题 应当首先建立过程模型 根据过程设计步骤 完成算法 小结小结 1 算法概念和算法的基本思想 1 算法与一般意义上具体问题的解法的联系与区别 2 算法的五个特征 2 利用算法的思想和方法解决实际问题 能写出一此简单问题的算法 3 两类算法问题 1 数值性计算问题 如 解方程 或方程组 解不等式 或不等式组 套用公式判断 性的问题 累加 累乘等一类问题的算法描述 可通过相应的数学模型借助一般数学计算方 法 分解成清晰的步骤 使之条理化即可 2 非数值性计算问题 如 排序 查找 变量变换 文字处理等需先建立过程模型 通 过模型进行算法设计与描述 4 利用 TI voyage200 图形计算器演示时 开始学生看 想 探究 然后模范 创新 图形 计算器为学生创建一个自我发挥的平台 作业 作业 课本第 4 页练习 为您服务教育网 6 1 任意给定一个正实数 设计一个算法求以这个数为半径的圆的面积 解 算法步骤 第一步 输入任意一个正实数 r 第二步 计算以 r 为半径的圆的面积 2 rS 第三步 输出圆的