高中数学 1.3.1辗转相除法与更相减损术课件 新人教A版必修3.ppt

1 3算法案例 第一课时 辗转相除法与更相减损术 算法案例之求最大公约数 求以下几组正整数的最大公约数 注 若整数m和n满足n整除m 则 m n n 用 m n 来表示m和n的最大公约数 1 18 30 2 24 16 3 63 63 4 72 8 5 301 133 想一想 如何求8251与6105的最大公约数 思考1 求18与24的最大公约数 6 8 63 8 7 短除法 知识探究 一 辗转相除法 思考2 对于8251与6105这两个数 由于其公有的质因数较大 利用上述方法求最大公约数就比较困难 注意到8251 6105 1 2146 那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系 思考3 又6105 2146 2 1813 同理 6105与2146的公约数和2146与1813的公约数相等 重复上述操作 你能得到8251与6105这两个数的最大公约数吗 2146 1813 1 333 148 37 4 0 333 148 2 37 1813 333 5 148 8251 6105 1 2146 6105 2146 2 1813 8251和6105的最大公约数 解 8251 6105 1 21466105 2146 2 18132146 1813 1 3331813 333 5 148333 148 2 37148 37 4 8251 6105 6105 2146 2146 1813 1813 333 333 148 148 37 37 关系式m np r中m n r得取值变化情况 8251 6105 2146 6105 2146 2146 1813 1813 333 1813 333 148 148 333 37 148 37 0 辗转相除法是一个反复执行直到余数等于0停止的步骤 这实际上是一个循环结构 m n q r 用程序框图表示出右边的过程 r mMODn m n n r r 0 是 否 思考4 辗转相除法中的关键步骤是哪种逻辑结构 思考5 上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法 一般地 用辗转相除法求两个正整数m n的最大公约数 可以用什么逻辑结构来构造算法 其算法步骤如何设计 第一步 给定两个正整数m n m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于m 否则 返回第二步 思考5 该算法的程序框图如何表示 思考6 该程序框图对应的程序如何表述 INPUTm n DO r mMODn m n n r LOOPUNTILr 0 PRINTm END 思考7 如果用当型循环结构构造算法 则用辗转相除法求两个正整数m n的最大公约数的程序框图和程序分别如何表示 INPUTm n WHILEn 0 r mMODn m n n r WEND PRINTm END 练习1 利用辗转相除法求两数4081与20723的最大公约数 53 20723 4081 5 318 4081 318 12 265 318 265 1 53 265 53 5 0 穷举法 也叫枚举法 步骤 从两个数中较小数开始由大到小列举 直到找到公约数立即中断列举 得到的公约数便是最大公约数 穷举法 知识探究 二 更相减损术 思考1 设两个正整数m n 若m n k 则m与n的最大公约数和n与k的最大公约数相等 反复利用这个原理 可求得98与63的最大公约数为多少 98 63 35 14 7 7 21 7 14 28 7 21 35 28 7 63 35 28 思考2 上述求两个正整数的最大公约数的方法称为更相减损术 一般地 用更相减损术求两个正整数m n的最大公约数 可以用什么逻辑结构来构造算法 其算法步骤如何设计 第一步 给定两个正整数m n m n 第二步 计算m n所得的差k 第三步 比较n与k的大小 其中大者用m表示 小者用n表示 第四步 若m n 则m n的最大公约数等于m 否则 返回第二步 思考3 该算法的程序框图如何表示 思考4 该程序框图对应的程序如何表述 INPUTm n WHILEmn k m n IFn kTHEN m n n k ELSE m k ENDIF WEND PRINTm END 更相减损术 在中国古代数学专著 九章算术 中记述为 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 程序 INPUT a b a bi 0WHILEaMOD2 0ANDbMOD2 0a a 2b b 2i i 1WENDDOIFb aTHENt aa bb tENDIFa a bLOOPUNTILa bPRINTa 2 iEND 理论迁移 例1分别用辗转相除法和更相减损术求168与93的最大公约数 辗转相除法 168 93 1 75 93 75 1 18 75 18 4 3 18 3 6 更相减损术 168 93 75 93 75 18 75 18 57 57 18 39 39 18 21 21 18 3 18 3 15 15 3 12 12 3 9 9 3 6 6 3 3 例2求325 130 270三个数的最大公约数 因为325 130 2 65 130 65 2 所以325与130的最大公约数是65 因为270 65 4 10 65 10 6 5 10 5 2 所以65与270最大公约数是5 故325 130 270三个数的最大公约数是5 1 辗转相除法 就是对于给定的两个正整数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽为止 这时的较小的数即为原来两个数的最大公约数 小结作业 2 更相减损术 就是对于给定的两个正整数 用较大的数减去较小的数 然后将差和较小的数构成新的一对数 继续上面的减法 直到差和较小的数相等 此时相等的两数即为原来两个数的最大公约数 比较辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 小结 作业 P45练习 1 P48习题1 3A组 1