辗转相除法与更相减损术、秦九韶算法

1.3 算 法 案 例第 1课 时 辗 转 相 除 法 与 更 相 减 损术 、 秦 九 韶 算 法 1.通 过 辗 转 相 除 法 与 更 相 减 损 术 、 秦 九 韶 算 法 的 学 习 ,进一 步 体 会 算 法 思 想 ;2.通 过 古 代 著 名 的 算 法 ,理 解 掌 握 辗 转 相 除 法 与 更 相 减 损术 、 秦 九 韶 算 法 的 含 义 ;(重 点 )3.了 解 其 计 算 过 程 ;(重 点 )4.了 解 其 算 法 程 序 框 图 和 程 序 (难 点 ) 1. 回 顾 算 法 的 三 种 表 述 ：自 然 语 言程 序 框 图 （ 三 种 逻 辑 结 构 ）程 序 语 言 （ 五 种 基 本 语 句 ） 2.小 学 学 过 的 求 两 个 数 最 大 公 约 数 的 方 法 .先 用 两 个 公 有 的 质 因 数 连 续 去 除 ， 一 直 除 到 所 得 的 商 是互 质 数 为 止 ， 然 后 把 所 有 的 除 数 连 乘 起 来 .例 如 ： 求 两 个 正 整 数 的 最 大 公 约 数（ 1） 求 25和 35的 最 大 公 约 数（ 2） 求 49和 63的 最 大 公 约 数25（ 1） 5 5 357 49（ 2） 7 7 639所 以 ， 25和 35的 最 大 公约 数 为 5. 所 以 ， 49和 63的 最 大 公约 数 为 7.除 了 用 这 种 方 法 外 还 有没 有 其 他 方 法 吗 ？ 辗 转 相 除 法 （ 欧 几 里 得 算 法 ）思 考 ： 算 出 8 251和 6 105的 最 大 公 约 数 .第 一 步 ,用 两 数 中 较 大 的 数 除 以 较 小 的 数 ， 求 得 商 和 余数 8 251=6 105 1+2 146.结 论 ： 8 251和 6 105的 公 约 数 就 是 6 105和 2 146的 公约 数 ， 求 8 251和 6 105的 最 大 公 约 数 ， 只 要 求 出 6 105和 2 146的 最 大 公 约 数 就 可 以 了 . 为 什 么 ？ 第 二 步 ,对 6 105和 2 146重 复 第 一 步 的 做 法 ，6 105=2 146 2+1 813，同 理 6 105和 2 146的 最 大 公 约 数 也 是 2 146和 1 813的最 大 公 约 数 . 完 整 的 过 程 : 8 251=6 105 1+2 146 6 105=2 146 2+1 813 2 146=1 813 1+3331 813=333 5+148333=148 2+37148=37 4+0 显 然 37是 148和 37的 最 大 公 约 数 ， 也 就 是 8 251和 6 105的最 大 公 约 数 . 所 谓 辗 转 相 除 法 ， 就 是 对 于 给 定 的 两 个 数 ， 用 较大 的 数 除 以 较 小 的 数 .若 余 数 不 为 零 ， 则 将 余 数 和 较小 的 数 构 成 新 的 一 对 数 ， 继 续 上 面 的 除 法 ， 直 到 大 数被 小 数 除 尽 ， 则 这 时 较 小 的 数 就 是 原 来 两 个 数 的 最 大公 约 数 .（ 1） 辗 转 相 除 法 （ 2） 算 法 步 骤第 一 步 ,输 入 两 个 正 整 数 m,n(mn).第 二 步 ,计 算 m除 以 n所 得 的 余 数 r.第 三 步 ,m=n,n=r.第 四 步 ,若 r 0,则 m,n的 最 大 公 约 数 等 于 m； 否 则 转到 第 二 步 . 第 五 步 ,输 出 最 大 公 约 数 m. （ 3） 程 序 框 图 （ 4） 程 序INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND开 始输 入 m， n求 m除 以 n的 余 数 rm=nn=rr=0？是输 出 m结 束 否 更 相 减 损 术 算 理 ： 可 半 者 半 之 ， 不 可 半 者 ， 副 置 分 母 、 子 之 数 ， 以 少减 多 ， 更 相 减 损 ， 求 其 等 也 ， 以 等 数 约 之 .第 一 步 ： 任 意 给 定 两 个 正 整 数 ， 判 断 它 们 是 否 都 是 偶 数 .若 是 ， 则 用 2约 简 ； 若 不 是 则 执 行 第 二 步 .第 二 步 ： 以 较 大 的 数 减 较 小 的 数 ， 接 着 把 所 得 的 差 与 较 小的 数 比 较 ， 并 以 大 数 减 小 数 .继 续 这 个 操 作 ， 直 到 所 得 的数 相 等 为 止 ， 则 这 个 数 （ 等 数 ） 或 其 与 约 简 的 数 的 乘 积 就是 所 求 的 最 大 公 约 数 . 更 相 减 损 术（ 1） 算 理 ： 所 谓 更 相 减 损 术 ， 就 是 对 于 给 定 的 两 个 数 ，用 较 大 的 数 减 去 较 小 的 数 ， 然 后 将 差 和 较 小 的 数 构 成 新的 一 对 数 ， 再 用 较 大 的 数 减 去 较 小 的 数 ， 反 复 执 行 此 步骤 ， 直 到 差 数 和 较 小 的 数 相 等 ， 此 时 相 等 的 两 数 便 为 原来 两 个 数 的 最 大 公 约 数 . （ 2） 算 法 步 骤第 一 步 ,输 入 两 个 正 整 数 a,b(ab);第 二 步 ,若 a不 等 于 b ,则 执 行 第 三 步 ； 否 则 转 到 第 五 步 ；第 三 步 ,把 a-b的 差 赋 予 r;第 四 步 ,如 果 br, 那 么 把 b赋 给 a,把 r赋 给 b;否 则 把 r赋 给 a，执 行 第 二 步 ；第 五 步 ,输 出 最 大 公 约 数 b. （ 3） 程 序 框 图 开 始输 入 a， bbr？a=b是 输 出 b结 束ab？r=a-b是 否b=ra=r否 （ 4） 程 序 INPUT “ a,b=“ ;a,bWHILE a b r=a-b IF br THEN a=b b=r ELSE a=r END IFWENDPRINT bEND 例 1 用 更 相 减 损 术 求 98与 63的 最 大 公 约 数 .解 ： 由 于 63不 是 偶 数 ， 把 98和 63以 大 数 减 小 数 ， 并 辗 转 相 减 , 98 63 3563 35 2835 28 728 7 2121 7 1414 7 7所 以 ， 98和 63的 最 大 公 约 数 等 于 7. 秦 九 韶 算 法 的 基 本 思 想对 于 求 n次 多 项 式 的 值 ， 在 我 国 古 代 数 学 中 有 一 个 优 秀 算 法 ，即 秦 九 韶 算 法 ， 我 们 将 对 这 个 算 法 作 些 了 解 和 探 究 .思 考 1:对 于 多 项 式 f(x)=x5+x4+x3+x2+x+1， 求 f(5)的 值 . 若 先 计 算 各 项 的 值 ， 然 后 再 相 加 ， 那 么 一 共 要 做 多 少 次 乘法 运 算 和 多 少 次 加 法 运 算 ？4+3+2+1=10次 乘 法 运 算 ， 5次 加 法 运 算 . 思 考 2:在 上 述 问 题 中 ， 若 先 计 算 x2的 值 ， 然 后 依 次 计 算x2 x， (x2 x) x， (x2 x) x) x的 值 ， 这 样 每 次都 可 以 利 用 上 一 次 计 算 的 结 果 ， 再 将 这 些 数 与 x和 1相 加 ，那 么 一 共 做 了 多 少 次 乘 法 运 算 和 多 少 次 加 法 运 算 ？4次 乘 法 运 算 ， 5次 加 法 运 算 . 思 考 3:利 用 后 一 种 算 法 求 多 项 式 f(x)=anxn+an-1xn-1+ +a1x+a0的 值 ， 这 个 多 项 式 应 写 成 哪 种 形 式 ？f(x)=anxn+an-1xn-1+ +a1x+a0 =(anxn-1+an-1xn-2+ +a2x+a1)x+a0=(anxn-2+an-1xn-3+ +a2)x+a1)x+a0 =( (anx+an-1)x+an-2)x+ +a1)x+a0. 这 是 怎 样 的 一种 改 写 方 式 ？最 后 的 结 果 是什 么 ？ 思 考 4:对 于 f(x)=( (anx+an-1)x+an-2)x+ +a1)x+a0， 由内 向 外 逐 层 计 算 一 次 多 项 式 的 值 ， 其 算 法 步 骤 如 何 ？第 一 步 ,计 算 v1=anx+an-1. 第 二 步 ,计 算 v2=v1x+an-2.第 三 步 ,计 算 v3=v2x+an-3. 第 n步 ,计 算 vn=vn-1x+a0. 最 后 的 一 项是 什 么 ？ 思 考 5:上 述 求 多 项 式 f(x)=anxn+an-1xn-1+ +a1x+a0的 值 的方 法 称 为 秦 九 韶 算 法 ， 利 用 该 算 法 求 f(x0)的 值 ， 一 共 需要 多 少 次 乘 法 运 算 ， 多 少 次 加 法 运 算 ？思 考 6:在 秦 九 韶 算 法 中 ， 记 v0=an， 那 么 第 k步 的 算 式 是 什么 ？vk=vk-1x+an-k (k=1， 2， ， n) 秦 九 韶 算 法 的 程 序 设 计 思 考 1:用 秦 九 韶 算 法 求 多 项 式 的 值 ， 可 以 用 什 么 逻 辑 结 构来 构 造 算 法 ？ 其 算 法 步 骤 如 何 设 计 ？第 一 步 :输 入 多 项 式 的 次 数 n， 最 高 次 项 的 系 数 an和 x的 值 . 第 二 步 :令 v=an， i=n-1. 第 三 步 :输 入 i次 项 的 系 数 ai. 第 四 步 :v=vx+ai， i=i-1.第 五 步 :判 断 i 0是 否 成 立 .若 是 ， 则 返 回 第 三 步 ； 否 则 ，输 出 多 项 式 的 值 v. 思 考 2:该 算 法 的 程 序框 图 如 何 表 示 ？ 开 始输 入 n， an， x的 值v=an v=vx+ai输 入 a ii0？i=n-1 i=i-1结 束 是 输 出 v 否 思 考 3:该 程 序 框 图 对 应 的 程 序 如 何 表 述 ？开 始输 入 n， an， x的 值v=an v=vx+a i输 入 aii0？i=n-1 i=i-1结 束 是输 出 v 否 INPUT “ n=” ； nINPUT “ an =” ； aINPUT “ x=” ； x v=a i=n-1WHILE i=0 PRINT “ i=” ;i INPUT “ ai=” ； a v=v*x+a i=i-1WENDPRINT vEND 例 2 已 知 一 个 5次 多 项 式 为 f(x)=4x5+2x4+3.5x3-2.6x2+1.7x-0.8， 用 秦 九 韶 算 法 求 这 个 多 项 式 当 x=5时 的 值 .解 ： 根 据 秦 九 韶 算 法 把 多 项 式 改 写 成 如 下 形 式 ：f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.按 照 从 内 到 外 的 顺 序 ， 依 次 计 算 一 次 多 项 式 当 x=5时 的 值 ：v0=4;v1=4 5+2=22；v2=22 5+3.5=113.5；v 3=113.5 5-2.6=564.9；v4=564.9 5+1.7=2 826.2；v5=2 826.2 5-0.8=14 130.2.所 以 f(5)=14 130.2. 阅 读 下 列 程 序 ， 说 明 它 解 决 的 实 际 问 题 是 什 么 ？解 ： 求 多 项 式 f(x)=1+2x+3x 2+4x3+5x4在 x=a时 的 值 . INPUT “ x=” ； an=0y=0WHILE n5 y=y+(n+1)*a n n=n+1WENDPRINT yEND 1. 用 辗 转 相 除 法 求 225和 135的 最 大 公 约 数 .显 然 45是 90和 45的 最 大 公 约 数 ， 也 就 是 225和 135的 最 大公 约 数 . 225=135 1+90135=90 1+4590=45 2 2.利 用 辗 转 相 除 法 求 两 数 4 081与 20 723的 最 大 公 约 数 .20 723 =4 081 5+318;4 081 =318 12+265;318=265 1+53;265=53 5+0. 所 以 4 081与 20 723的 最 大 公 约 数 是 53. 3.用 秦 九 韶 算 法 求 多 项 式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时 的 值 .解 :首 先 将 原 多 项 式 改 写 成 如 下 形 式 : f(x)=(2x-5)x-4)x+3)x-6)x+7然 后 由 内 向 外 逐 层 计 算 一 次 多 项 式 当 x=5时 的 值 ,即v0=2 v1=v0 x-5=2 5-5=5v2=v1x-4=5 5-4=21v 3=v2x+3=21 5+3=108v4=v3x-6=108 5-6=534v5=v4x+7=534 5+7=2 677所 以 ,当 x=5时 ,多 项 式 的 值 是 2 677. 1.比 较 辗 转 相 除 法 与 更 相 减 损 术 的 区 别（ 1） 都 是 求 最 大 公 约 数 的 方 法 ， 计 算 上 辗 转 相 除 法 以 除法 为 主 ， 更 相 减 损 术 以 减 法 为 主 ， 计 算 次 数 上 辗 转 相 除法 计 算 次 数 相 对 较 少 ， 特 别 当 两 个 数 字 大 小 区 别 较 大 时 ，计 算 次 数 的 区 别 较 明 显 .（ 2） 从 结 果 体 现 形 式 来 看 ， 辗 转 相 除 法 体 现 结 果 是 以 相除 余 数 为 0而 得 到 ， 而 更 相 减 损 术 则 以 减 数 与 差 相 等 而 得到 . 2.评 价 一 个 算 法 好 坏 的 一 个 重 要 标 志 是 运 算 的 次 数 ， 如果 一 个 算 法 从 理 论 上 需 要 超 出 计 算 机 允 许 范 围 内 的 运 算次 数 ， 那 么 这 样 的 算 法 就 只 能 是 一 个 理 论 算 法 .在 多 项 式求 值 的 各 种 算 法 中 ， 秦 九 韶 算 法 是 一 个 优 秀 算 法 . 昨 天 的 努 力 就 是 今 天 的 收 获 ， 今 天 的 努 力就 是 未 来 的 希 望 .岁 月 不 饶 人 ， 不 妨 现 在就 行 动 ！