高中数学 第一章 算法初步 1.3.1 辗转相除法与更相减损术、秦九韶算法课件2 新人教A版必修3.ppt

1 3算法案例第1课时辗转相除法与更相减损术 秦九韶算法 1 理解辗转相除法与更相减损术的含义 了解执行过程 2 掌握秦九韶算法的计算过程 了解它在数学计算中的应用 3 进一步体会算法的基本思想 1 辗转相除法 1 作用 是用于求 的一种方法 这种算法由欧几里得在公元前300年左右首先提出 因而又叫 2 算法步骤 第一步 给定两个正整数m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若 则m n的最大公约数等于m 否则 返回第二步 两个正整数的最大公约数 欧几里得算法 r 0 2 更相减损术 1 作用 是我国古代数学专著 中介绍的一种求两个数最大公约数的方法 2 算法步骤 第一步 任意给定两个正整数 判断它们是否都是 若是 用2约简 若不是 执行第二步 第二步 以较大的数 较小的数 接着把所得的差与较小的数比较 并以 减 继续这个操作 直到所得的差与减数 为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 九章算术 偶数 减去 大数 小数 相等 3 秦九韶算法把一个n次多项式f x anxn an 1xn 1 a1x a0改写成如下形式 f x anx an 1 x an 2 x a1 x a0 求多项式的值时 首先计算 一次多项式的值 即v1 然后由内向外逐层计算一次多项式的值 即v2 v3 vn 这样 求n次多项式f x 的值就转化为求 的值 最内层括号内 anx an 1 v1x an 2 v2x an 3 vn 1x a0 n个一次多项式 1 辗转相除法可解决下列问题中的 a 求两个正整数的最大公约数b 多项式求值c 求两个正整数的最小公倍数d 排序问题 解析 选a 辗转相除法可以求两个正整数的最大公约数 2 用更相减损术可求得78与36的最大公约数是 a 24b 18c 12d 6 解析 选d 先用2约简得39 18 然后辗转相减得39 18 21 21 18 3 18 3 15 15 3 12 12 3 9 9 3 6 6 3 3 所以所求的最大公约数为3 2 6 3 运算速度快是计算机一个很重要的特点 而算法好坏的一个重要标志是 解析 运算次数多少决定计算速度 故运算次数是算法好坏的重要标志 答案 运算次数 4 求多项式的值时 首先计算最内层括号内一次多项式的值 然后由内向外逐层计算一次多项式的值 这样通过一次式的反复运算 逐步得出高次多项式的值的方法称作 解析 根据秦九韶算法的步骤 是秦九韶算法 答案 秦九韶算法 5 用更相减损术求294和84的最大公约数时 第一步是 解析 由于294和84都是偶数 先用2约简 答案 用2约简 一 辗转相除法与更相减损术根据辗转相除法与更相减损术求两个正整数最大公约数的步骤 探究下列问题 探究1 1 用辗转相除法可以求两个正整数m n的最大公约数 那么用什么逻辑结构来设计算法 其算法步骤如何设计 提示 用循环结构设计算法 算法如下 第一步 给定两个正整数m n m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于m 否则 返回第二步 2 该算法的程序框图如何表示 该程序框图对应的程序如何表述 提示 程序框图 程序 inputm ndor mmodnm nn rloopuntilr 0printmend 3 如果用当型循环结构设计算法 正整数m n的最大公约数的程序框图和程序分别如何表示 提示 程序框图 程序 inputm nwhilen 0r mmodnm nn rwendprintmend 探究2 1 用更相减损术可以求两个正整数m n的最大公约数 那么用什么逻辑结构来构造算法 其算法步骤如何设计 提示 用循环结构设计算法 算法如下 第一步 任意给定两个正整数m n m n 第二步 设计m n所得的差k 第三步 比较n与k的大小 其中大者用m表示 小者用n表示 第四步 若m n 则m n的最大公约数等于m 否则 返回第二步 2 该算法的程序框图如何表示 该程序框图对应的程序如何表述 提示 程序框图 程序 inputm nwhilemnk m nifn kthenm nn kelsem kendifwendprintmend 探究总结 辗转相除法与更相减损术概念的关注点 1 辗转相除法与更相减损术有着相同的算法依据 但要注意运算过程的差别 辗转相除法的上一次运算的除数和余数分别作为下一次运算的被除数和除数 其结果直至余数为零得出 更相减损术在上一次运算结束后 比较减数和差的大小 将大的作为下一次运算的被减数 小的作为减数 直至出现相等数时得到结果 2 两者主要区别在于 辗转相除法进行的是除法运算 即辗转相除 更相减损术进行的是减法运算 即辗转相减 但其实质都是一个不断的递推过程 3 两者在算法设计上有一个重要的区别点 辗转相除法 下一次进行相除时 由上一次的除数和余数直接相除即可 而更相减损术下一次相减前必须有一个判断大小的过程 以区别谁做被减数 4 用更相减损术求两正整数的最大公约数时 若两数为偶数 可先约去2 这时莫忘记求得的相等两数乘以约简的数才是所求最大公约数 二 秦九韶算法根据秦九韶算法的含义和步骤探究下列各题 探究1 秦九韶算法的实质是什么 提示 秦九韶算法的实质是 求多项式f x anxn an 1xn 1 a1x a0的值时 转化为求n个一次多项式的值 共进行n次乘法运算和n次加法运算 这种算法的运算次数较少 是多项式求值比较先进的算法 探究2 依据秦九韶算法的过程填空 f x anxn an 1xn 1 a1x a0 anxn 1 an 1xn 2 a1 x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 设v1 v2 v1x an 2 v3 v2x an 3 vn 答案 anx an 1vn 1x a0 探究总结 秦九韶算法的算法特点秦九韶算法是多项式求值的优秀算法 其特点是 1 化高次多项式求值为一次多项式求值 2 减少了运算次数 提高了效率 3 步骤重复执行 容易用计算机实现 类型一辗转相除法和更相减损术的应用1 下列对辗转相除法的说法错误的是 a 辗转相除法与欧几里得算法是两种不同的求最大公约数的方法b 辗转相除法的基本步骤是用较大的数除以较小的数c 在对两个数求最大公约数时 除辗转相除法之外还有更相减损术d 在用辗转相除法时 需要用到循环语句编写程序 2 已知7163 209 34 57 209 57 3 38 57 38 1 19 38 19 2 根据上述一系列等式 可确定7163和209的最大公约数是 a 57b 3c 19d 343 用辗转相除法求80和36的最大公约数 并用更相减损术检验所得结果 解题指南 1 结合辗转相除法的含义来判断 2 根据算法过程 只需看最后一个算式38 19 2 3 将80作为大数 36作为小数 执行辗转相除法和更相减损术的步骤即可 自主解答 1 选a 辗转相除法是由欧几里得在公元前300年左右首先提出的 b c d都正确 2 选c 由38 19 2 则19是7163和209的最大公约数 3 用辗转相除法 80 36 2 8 36 8 4 4 8 4 2 0 故80和36的最大公约数是4 用更相减损术检验 先用4约简得20和9 20 9 11 11 9 2 9 2 7 7 2 5 5 2 3 3 2 1 2 1 1 故80和36的最大公约数是4 延伸探究 题3中条件不变 求这两个数的最小公倍数是多少 解析 已知最大公约数是4 从而80和36的最小公倍数是80 36 4 720 规律总结 辗转相除法和更相减损术求最大公约数的注意点 1 辗转相除法是当大数被小数除尽时 结束除法运算 较小的数就是最大公约数 2 更相减损术是当大数减去小数的差等于小数时停止减法 较小的数就是最大公约数 变式训练 1 用辗转相除法求288与123的最大公约数 2 用更相减损术求57与93的最大公约数 3 求567与405的最小公倍数 解析 1 288 123 2 42 123 42 2 39 42 39 1 3 39 3 13 所以288和123的最大公约数是3 2 93 57 36 57 36 21 15 21 15 6 9 6 3 6 3 3 所以57与93的最大公约数是3 3 567 405 1 162405 162 2 81162 81 2 0所以81是567与405的最大公约数 从而567与405的最小公倍数为567 405 81 2835 类型二用秦九韶算法求多项式的值1 秦九韶算法与直接计算相比较 下列说法错误的是 a 秦九韶算法与直接计算相比 大大减少了做乘法的次数 使计算量减小 逻辑结构简单b 秦九韶算法减少做乘法的次数 在计算机上也就加快了计算的速度c 秦九韶算法减少做乘法的次数 在计算机上也就降低了计算的速度d 秦九韶算法避免对自变量x单独做幂的计算 而是与系数一起逐次增长幂次 从而可提高计算的速度 2 设计程序框图 用秦九韶算法求多项式的值 要选用的结构是 a 顺序结构b 条件结构c 循环结构d 以上都有3 已知一个5次多项式为f x 4x5 3x3 2x2 5x 1 用秦九韶算法求这个多项式当x 2时的值 解题指南 1 根据秦九韶算法的过程特点可以得到答案 2 设计程序框图 需要输入 计算和判断 然后多次循环 故三种结构都需要 3 把所给的多项式写成关于x的一次函数的形式 依次写出 得到最后结果 从里到外进行运算 得到要求的值 自主解答 1 选c 秦九韶算法减少做乘法的次数 在计算机上也就提高了计算的速度 2 选d 设计程序框图需先输入相关量 中间判断计算次数 决定是否继续循环 故三种常用的结构都需要 3 由f x 4x 0 x 3 x 2 x 5 x 1 v0 4 v1 4 2 0 8v2 8 2 3 13v3 13 2 2 28v4 28 2 5 61v5 61 2 1 123故这个多项式当x 2时的值为123 规律总结 利用秦九韶算法计算多项式的值的策略 1 正确地将多项式改写 若在多项式中有几项不存在 可将这些项的系数看成0 即把这些项看做0 xn 2 由内向外逐次计算 3 每一步计算结果准确 由于下一次计算用到上一次计算的结果 应认真 细致地计算每一步 变式训练 求多项式f x x5 5x4 10 x3 10 x2 5x 1当x 2时的值 解题指南 先改写多项式 再由内向外计算 解析 f x x5 5x4 10 x3 10 x2 5x 1 x 5 x 10 x 10 x 5 x 1 而x 2 所以有 v0 1 v1 v0 x a4 1 2 5 3 v2 v1x a3 3 2 10 4 v3 v2x a2 4 2 10 2 v4 v3x a1 2 2 5 1 v5 v4x a0 1 2 1 1 即f 2 1 拓展类型 求三个数的最大公约数1 三个正整数分别是a b c 若a b的最大公约数是m m c的最大公约数是n 则a b c的最大公约数是 2 三个数175 100 75的最大公约数是 3 求三个数324 243 108的最大公约数 解题指南 1 先求两数的最大公约数 再求此公约数和第三个数的最大公约数 就是这三个数的最大公约数 2 先求出175与100的最大公约数25 再求25与75的最大公约数 所得结果就是这三个数的最大公约数 3 方法一先求两数的最大公约数 再求此数与第三个数的最大公约数就为所求 方法二按照最大公约数的性质逐步来求 自主解答 1 n显然是三数a b c的最大公约数 答案 n2 方法一 辗转相除法 先求175与100的最大公约数 175 100 1 75 100 75 1 25 75 25 3 所以175与100的最大公约数是25 以下再求25与75的最大公约数 75 25 3所以25和75的最大公约数是25 所以175 100 75的最大公约数是25 方法二 更相减损术 第一步 先从较大数中减去较小的数 175 100 75 100 75 25 得75 25 75 第二步 重复上面的算法 75 25 2 25 75 2 25 25 得25 25 25 因为25 25 25的最大公约数为25 所以三个数175 100 75的最大公约数为25 注 方法二的过程可简记为 175 100 75 175 100 100 75 75 75 25 75 75 2 25 25 75 25 2 25 25 25 所以三个数175 100 75的最大公约数为25 答案 25 3 方法一 先求324与243的最大公约数 324 243 1 81 243 81 3 所以324与243的最大公约数为81 下面再求108与81的最大公约数 108 81 27 81 27 3 所以108与81的最大公约数是27 故324 243 108的最大公约数为27 方法二 324 243 108 324 243 243 108 108 81 135 108 81 135 108 108 81 81 27 27 81 2 27 27 27 27 27