资源描述
一 人 带 着 一 只 狼 、 一 只 羊 和 一 箱 蔬 菜 要 过 河 ,但 只有 一 条 小 船 .乘 船 时 ， 每 次 只 能 带 狼 、 羊 和 蔬 菜 中 的 一种 .当 有 人 在 场 时 ， 狼 、 羊 、 蔬 菜 都 相 安 无 事 .一 旦 人不 在 ,狼 会 吃 羊 ,羊 会 吃 菜 .请 设 计 一 个 方 案 ,安 全 地 将 狼 、羊 和 蔬 菜 带 过 河 . 过 河 游 戏趣 味 益 智 游 戏 如 何 发 电 子 邮 件 ？假 如 你 的 朋 友 不 会 发 电 子 邮 件 ， 你 能 教 会 他 么 ？发 邮 件 的 方 法 很 多 ， 下 面 就 是 其 中 一 种 的 操 作 步 骤 ：第 一 步 登 陆 电 子 信 箱第 二 步 点 击 “ 写 信 ”第 三 步 输 入 收 件 人 地 址第 四 步 输 入 主 题第 五 步 输 入 信 件 内 容第 六 步 点 击 “ 发 送 ” 一 般 地 ,对 于 一 类 问 题 的 机 械 式 地 、 统 一地 、 按 部 就 班 地 求 解 过 程 称 为 算 法 (algorithm)它 是 解 决 某 一 问 题 的 程 序 或 步 骤 . 按 照 这 样 的 理 解 ,我 们 可 以 设 计 出 很 多 具体 数 学 问 题 的 算 法 .下 面 看 几 个 例 子 : 所 谓 “ 算 法 ” 就 是 解 题 方 法 的 精 确 描 述 .从 更 广 义 的 角 度 来 看 ,并 不 是 只 有 “ 计 算 ” 的问 题 才 有 算 法 ,日 常 生 活 中 处 处 都 有 .如 乐 谱 是乐 队 演 奏 的 算 法 ,菜 谱 是 做 菜 肴 的 算 法 ,珠 算 口诀 是 使 用 算 盘 的 算 法 . 请 你 写 出 解 下 面 二 元 一 次 方 程 组 的 详 细 过 程 . 2 12 1x yx y 第 二 步 解 得 1 ;5x 第 三 步 - 2得 5y=3; 第 四 步 解 得 3 ; 5y 1 ,53.5xy 第 五 步 得 到 方 程 组 的 解 为 第 一 步 + 2得 5x=1; 解 ： 做一做 你 能 写 出 解 一 般 的 二 元 一 次 方 程 组 的 步 骤 吗 ？ 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) ( 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 思考 2 1 1 22 1 1 2 .a c a cy a b a b 第 四 步 ,解 （ 4） 得 2 1(1) (2)a a 得 ：第 三 步 , 2 1 1 2 2 1 1 2.a b a b y a c a c （ 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 上 述 步 骤 构 成 了 解 二 元 一 次 方 程 组 的 一 个 算 法 ，我 们 可 以 进 一 步 根 据 这 一 算 法 编 制 计 算 机 程 序 ， 让计 算 机 来 解 二 元 一 次 方 程 组 . 练 习 1. 给 出 求 1+2+3+4+5+6的 一 个 算 法 .解 法 1.按 照 逐 一 相 加 的 程 序 进 行 .第 一 步 :计 算 1+2,得 3;第 二 步 :将 第 一 步 中 的 运 算 结 果 3与 3相 加 得 6;第 三 步 :将 第 二 步 中 的 运 算 结 果 6与 4相 加 得 10;第 四 步 :将 第 三 步 中 的 运 算 结 果 10与 5相 加 得 15;第 五 步 :将 第 四 步 中 的 运 算 结 果 15与 6相 加 得 21. 解 法 2.可 以 运 用 下 面 公 式 直 接 计 算 .( 1)1 2 3 4 2n nn 第 一 步 ,取 n =6;第 二 步 ,计 算 ;2 )1( nn第 三 步 ,输 出 计 算 结 果 .点 评 :解 法 1繁 琐 ,步 骤 较 多 ; 解 法 2简 单 ， 步骤 较 少 . 找 出 好 的 算 法 是 我 们 的 追 求 目 标 . 现 在 你 对 算 法 有 了 新的 认 识 了 吗 ？ 在 数 学 中 ， 算 法 通 常 是 指 按 照 一 定 规 则解 决 某 一 类 问 题 的 明 确 和 有 限 的 步 骤 .现 在 ，算 法 通 常 可 以 编 成 计 算 机 程 序 ， 让 计 算 机 执行 并 解 决 问 题 .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不 是 质 数 . 变 式 : “判 断 53是 否 质 数 ” 的 算 法 如 下 ：第 1步 ,用 2除 53得 余 数 为 1,余 数 不 为 0,所 以 2不 能 整 除 53;第 2步 ,用 3除 53得 余 数 为 2,余 数 不 为 0,所 以 3不 能 整 除 53;第 52步 ,用 52除 53得 余 数 为 1,余 数 不 为 0,故 52不 能 整 除 53;所 以 53是 质 数 .上 述 算 法 正 确 吗 ？ 请 说 明 理 由 . 算 法 要 “ 面 面 俱 到 ” ,不 能 省 略 任 何 一 个 细 小 的 步 骤 ,只 有 这 样 ,才 能 在 人 设 计 出 算 法 后 ,把 具 体 的 执 行 过 程 交 给 计 算 机 完 成 . 设 计 一 个 具 体 问 题 的 算 法 时 ,与 过 去 熟 悉 地 解 数 学 题 的 过 程有 直 接 的 联 系 ,但 这 个 过 程 必 须 被 分 解 成 若 干 个 明 确 的 步 骤 ,而 且 这 些 步 骤 必 须 是 有 效 的 . 判断“整数n(n2)是否是质数”的算法自然语言描述第 一 步 给 定 大 于 2的 整 数 n.第 二 步 令 i=2.第 三 步 用 i除 n， 得 到 余 数 r. 第 四 步 判 断 “ r=0” 是 否 成 立 .若 是 ， 则 n不 是 质 数 ， 结 束 算 法 ； 否 则 将 i的 值 增 加 1， 仍 用 i表 示 . 第 五 步 判 断 “ i(n-1)” 是 否 成 立 .若 是 ， 则 n是 质 数 ， 结 束 算 法 ； 否 则 返 回 第 三 步 . 例 2:用 二 分 法 设 计 一 个 求 方 程 近 似 根的 算 法 2 2 0 x ( 0)x 二 分 法 对 于 区 间 a,b 上 连 续 不 断 、 且 f(a)f(b)0的 函 数y=f(x),通 过 不 断 地 把 函 数 f(x)的 零 点 所 在 的 区 间 一 分为 二 ， 使 区 间 的 两 个 端 点 逐 步 逼 近 零 点 ， 进 而 得 到 零点 或 其 近 似 值 的 方 法 叫 做 二 分 法 . 第 四 步 , 若 f(a) f(m) 0,则 含 零 点 的 区 间 为 a,m ；第 二 步 , 给 定 区 间 a,b ,满 足 f(a) f(b) 0第 三 步 , 取 中 间 点 2a bm 第 五 步 ,判 断 f(m)是 否 等 于 或 者 a,b 的 长度 是 否 小 于 d， 若 是 ， 则 m是 方 程 的 近 似 解 ;否则 ， 返 回 第 三 步 将 新 得 到 的 含 零 点 的 仍 然 记 为 a,b . 否 则 ， 含 零 点 的 区 间 为 m, 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时 的 原 方 程 的 近似 解 . 小 结 ： 算 法 的 特 征 是 什 么 ？ n明 确 性 n有 效 性 n有 限 性算 法 的 概 念 ： 算 法 通 常 指 可 以 用 来 解 决 的 某一 类 问 题 的 步 骤 或 程 序 ， 这 些 步 骤 或 程 序 必 须 是 明确 的 和 有 效 的 ， 而 且 能 够 在 有 限 步 之 内 完 成 的 .
展开阅读全文