《算法的概念》PPT课件.pptx

1.1.1 算 法 的 概 念1.1 算 法 与 程 序 框 图 发 电 子 邮 件 的 方 法 很 多 ， 下 面 是 其 中 的 一 种操 作 步 骤 ： ;第 二 步 点 击 “ 写 信 ” ;第 三 步 输 入 收 件 人 地 址;第 四 步 输 入 主 题 ;第 五 步 输 入 信 件 内 容第 六 步 点 击 “ 发 送 ” .;第 一 步 登 录 电 子 信 箱新课导入假 如 你 的 朋 友 不 会 发 电 子 邮 件 ， 你 怎 么 教 会 他 ？ 我 们 做 任 何 事 情 都 是 在 一 定 条 件 下 按 某 种顺 序 执 行 的 一 系 列 操 作 。 解 决 数 学 问 题 也 是 如此 。 例 如 用 加 减 消 元 法 解 二 元 一 次 方 程 组 时 ，就 可 以 按 照 某 一 步 骤 进 行 操 作 。 请 你 写 出 解 下 面 二 元 一 次 方 程 组 的 详 细 过 程 . 2 12 1x yx y 第 二 步 , 解 得 1 ;5x 第 三 步 , - 2得 5y=3; 第 四 步 , 解 得 3 ;5y 1 ,53.5xy 第 五 步 , 得 到 方 程 组 的 解 为第 一 步 , + 2得 5x=1; 解 ： 你 能 写 出 解 一 般 的 二 元 一 次 方 程 组 的 步 骤 吗 ？ 第 一 步 , 2 1(1) ( 2 )b b 得 ： 1 2 2 1 1 2 2 1 .a b a b x c b c b （ 3） 第 二 步 ,解 （ 3） 得 1 2 2 11 2 2 1 .c b c bx a b a b 1 1 1 1 2 2 12 2 2 (1) 0(2)a x b y c a b a ba x b y c 2 1 1 22 1 1 2 .ac acy ab ab 第 四 步 ,解 （ 4） 得 2 1(1) (2)a a 得 ：第 三 步 , 2 1 1 2 2 1 1 2.a b ab y a c ac （ 4） 第 五 步 ,得 到 方 程 组 的 解 为 1 2 2 11 2 2 12 1 1 22 1 1 2 ,.c b c bx a b a ba c a cy a b a b 这 两 个 解 方 程 组 的 算 法 的 适 用 范 围 有 何 不 同 ？ 在 数 学 中 ， 算 法 通 常 是 指 按 照 一 定 规 则解 决 某 一 类 问 题 的 明 确 和 有 限 的 步 骤 .现 在 ，算 法 通 常 可 以 编 成 计 算 机 程 序 ， 让 计 算 机 执行 并 解 决 问 题 .2.算 法 的 要 求(1)写 出 的 算 法 ,必 须 能 解 决 一 类 问 题 (例 如 解 任意 一 个 二 元 一 次 方 程 组 ),并 且 能 重 复 使 用 ;(2) 算 法 过 程 要 能 一 步 一 步 执 行 ,每 一 步 执 行 的操 作 ,必 须 确 切 ,不 能 含 混 不 清 ,而 且 在 有 限 步 之内 完 成 后 能 得 出 结 果 .1.算 法 的 定 义探究新知 3.算 法 的 基 本 特 征 :明 确 性 :算 法 对 每 一 个 步 骤 都 有 确 切 的 、 非 二义 性 的 规 定 ,即 每 一 步 对 于 利 用 算 法 解 决 问 题 的人 或 计 算 机 来 说 都 是 可 读 的 、 可 执 行 的 ,而 不 需要 计 算 者 临 时 动 脑 筋 . 有 效 性 :算 法 的 每 一 个 步 骤 都 能 够 通 过 基 本 运算 有 效 地 进 行 ,并 得 到 确 定 的 结 果 ； 对 于 相 同 的输 入 ,无 论 谁 执 行 算 法 ,都 能 够 得 到 相 同 的 最 终结 果 有 限 性 :算 法 应 由 有 限 步 组 成 ,至 少 对 某 些 输 入,算 法 应 在 有 限 多 步 内 结 束 ,并 给 出 计 算 结 果 信 息 输 出 :一 个 算 法 至 少 要 有 一 个 有 效 的 信息 输 出 ,这 就 是 问 题 求 解 的 结 果 .不 唯 一 性 :求 解 某 一 个 题 的 解 法 不 一 定 是 唯一 的 , 对 于 一 个 问 题 可 以 有 不 同 的 算 法 .数 据 输 入 :算 法 一 定 要 根 据 输 入 的 初 始 数 据 或给 定 的 初 值 才 能 正 确 执 行 它 的 每 一 步 骤 . 例 1.(1)设 计 一 个 算 法 判 断 7是 否 为 质 数 .第 一 步 , 用 2除 7,得 到 余 数 1.因 为 余 数 不 为 0， 所 以 2不 能 整 除 7.第 二 步 , 用 3除 7,得 到 余 数 1.因 为 余 数 不 为 0， 所 以 3不 能 整 除 7.第 三 步 , 用 4除 7,得 到 余 数 3.因 为 余 数 不 为 0， 所 以 4不 能 整 除 7.第 四 步 , 用 5除 7,得 到 余 数 2.因 为 余 数 不 为 0， 所 以 5不 能 整 除 7.第 五 步 , 用 6除 7,得 到 余 数 1.因 为 余 数 不 为 0， 所 以 6不 能 整 除 7.因 此 ， 7是 质 数 . 例 1.(2)设 计 一 个 算 法 判 断 35是 否 为 质 数 .第 一 步 , 用 2除 35,得 到 余 数 1.因 为 余 数 不 为 0， 所 以 2不 能 整 除 35.第 二 步 , 用 3除 35,得 到 余 数 2.因 为 余 数 不 为 0， 所 以 3不 能 整 除 35.第 三 步 , 用 4除 35,得 到 余 数 3.因 为 余 数 不 为 0， 所 以 4不 能 整 除 35.第 四 步 , 用 5除 35,得 到 余 数 0.因 为 余 数 为 0， 所 以 5能 整 除 35.因 此 ， 35不 是 质 数 . 任 意 给 定 一 个 大 于 1的 整 数 n,试 设 计 一 个 程 序或 步 骤 对 n是 否 为 质 数 做 出 判 定 .分 析 :回 顾 这 个 问 题 的 解 题 过 程 .算 法 步 骤 :第 一 步 :判 断 n是 否 等 于 2. 若 n=2,则 n是 质 数 ;若 n2,则 执 行 第 二 步 . 第 二 步 :依 次 检 验 2(n-1)这 些 整 数 是 不 是 n的约 数 ,即 是 不 是 整 除 n的 数 .若 有 这 样 的 数 ,则 n不 是 质 数 ;若 没 有 这 样 的 数 ,则 n是 质 数 . 2 2 0 0 x x 例 2： 用 二 分 法 设 计 一 个 求 方 程 的 近 似 根 的 算 法 对 于 区 间 a,b 上 连 续 不 断 、 且 f(a)f(b)0的 函 数 y=f(x),通 过 不 断 地 把 函 数 f(x)的 零 点 所 在的 区 间 一 分 为 二 ,使 区 间 的 两 个 端 点 逐 步 逼 近 零 点 ，进 而 得 到 零 点 或 其 近 似 值 的 方 法 叫 做 二 分 法 。二 分 法 的 基 本 思 想 ：分 析 ： 2 2( ) 2, 2 0 ( )f x x x f x 令 则 方 程 的 解 就 是 函 数 的 零 点 。 第 四 步 , 若 f(a) f(m ) 0,则 含 零 点 的 区 间 为 a,m ； 否 则 ， 含 零 点 的 区 间 为 m , b .第 二 步 , 给 定 区 间 a,b ,满 足 f(a) f(b) 0第 三 步 , 取 中 间 点 2a bm 第 五 步 ,判 断 f(m )是 否 等 于 或 者 a,b 的 长度 是 否 小 于 d， 若 是 ， 则 m是 方 程 的 近 似 解 ;否则 ， 返 回 第 三 步 将 新 得 到 的 含 零 点 的 仍 然 记 为 a,b .第 一 步 , 令 ,给 定 精 确 度 d.2( ) 2f x x 算 法 步 骤 ： a b |a-b|1 2 11 1.5 0.51.25 1.5 0.251.375 1.5 0.1251.375 1.437 5 0.062 51.406 25 1.437 5 0.031 251.406 25 1.421 875 0.015 6251.414 625 1.421 875 0.007 812 51.414 062 5 1.417 968 75 0.003 906 25当 d=0.005时 ， 按 照 以 上 算 法 ， 可 得 下 面 表 和 图 . y=x2-21 21.51.3751.25 于 是 ， 开 区 间 （ 1.4140625,1.41796875） 中的 实 数 都 是 当 精 确 度 为 0.005时 的 原 方 程 的 近似 解 . 2.算 法 的 特 征 是 什 么 ？明 确 性 有 效 性 有 限 性1.算 法 的 概 念 算 法 通 常 指 可 以 用 来 解 决 的 某 一 类 问 题 的步 骤 或 程 序 ， 这 些 步 骤 或 程 序 必 须 是 明 确 的 和有 效 的 ， 而 且 能 够 在 有 限 步 之 内 完 成 的 .课堂小结 1. 任 意 给 定 一 个 正 实 数 ,设 计 一 个 算 法 求以 这 个 数 为 半 径 的 圆 的 面 积 .算 法 步 骤 :第 一 步 :给 定 一 个 正 实 数 r;第 二 步 :计 算 以 r为 半 径 的 圆 的 面 积 S=r2;第 三 步 :得 到 圆 的 面 积 S.课后练习