辗转相除法与更相减损术 1.解决算法问题需经过哪些步骤？ 知问 回顾： 2.循环结构的程序框图和语句？ 算法分析 程序框图 程序 语句 结构 ____型循环结构 __型循环结构 知问 直到型循环结构 当型循环结构 知问 5 满足条件？ 是 循环体 否 满足条件？ 否 循环体 是 DO 循环体 LOOP UNTIL 条件 WHILE 条件 循环体 WEND 1.编程解决问题需经过哪些步骤？ 知问 回顾： 2.循环结构的程序框图和语句？ 短除法：先用两个数的公约数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数。 算法分析、程序框图、程序 3.求两个正整数最大公约数的方法？ 18 30 3 18与30的最大公约数为 . 2 例如：求18与30的最大公约数. 知问 3 5 （辗转相除法、更相减损术） 求8251与6105的最大公约数. 可以使用短除法吗？ 9 15 问题1. 两数比较大、公约数不易观察。 困难： 知问 思考1：辗转相除法与更相减损术可以用来解决什么问题？ 可以解决求两个正整数最大公约数的任何问题。 1.（例1）求8251与6105的最大公约数. 导学 知问 思考1：辗转相除法与更相减损术可以用来解决什么问题？ 可以解决求两个正整数最大公约数的任何问题。 思考2：辗转相除法与更相减损术为什么可以用来解决该问题？ 第一步： 1.（例1）求8251与6105的最大公约数. 导学 8251 = 6105 ×1 + 2146 结论：8251和6105的最大公约数就是6105和2146的最大公 约数. 问题2：为什么辗转相除法得到的结果是所求最大公约数？ 6105 = 2146 ×2 + 1813 第二步： 结论：6105和2146的最大公约数也是2146和1813的最大公 约数. …… 最后一步： 148 = 37 ×4 最终结论：8251和6105的最大公约数也是148和37的最大公约数，即37. + 0. 原理： 余数为0 辗转相除法 上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法（Euclidean algorithm）. 欧几里得（公元前330年—公元前275年），古希腊数学家，被称为“几何之父”。 《几何原本》，又称《原本》，是欧几里得所著的一部数学著作，提出了平面几何五大公设，欧几里得几何，是欧洲数学的基础，被广泛认为是历史上最成功的教科书，在西方是仅次于《圣经》而流传最广的书籍。 问题3.辗转相除法求两个正整数m，n的最大公约数，其算法步骤如何设计？ 第四步：重复二、三步， 直到余数为0. 第一步，给定两个正整数m，n(m>n). 第二步，计算m除以n所得的余数r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约 数等于__；否则，返回第二步. 算法分析： 辗转相除法 思考：从例1可以看出辗转相除法计算的规律是什么？蕴含什么思想？ 第一步：给定两个正整数； 第二步：用大数除以小数； 第三步：除数变成被除数， 余数变成除数； 算法的思想 m 问题4. 辗转相除法的算法有什么特点？ 需要使用哪种基本逻辑结构？ 辗转相除法是一个反复执行直到余数等于0停止的步骤，可以使用循环结构来构造算法。 回顾：构造循环结构应确定哪几部分内容？ ①初始化变量 ②确定循环体 ③设定循环控制条件 辗转相除法 第一步，给定两个正整数m，n(m>n). 第二步，计算m除以n所得的余数r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约 数等于m；否则，返回第二步. 算法分析： 初始化变量 循环体 循环控制条件 ①初始化变量 ②确定循环体 ③设定循环控制条件 辗转相除法 练习：根据“辗转相除法”的算法分析画出程序框图。 第一步，给定两个正整数m，n(m>n). 第二步，计算m除以n所得的余数r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约 数等于m；否则，返回第二步. 算法分析： 开始 输入m，n 求m除以n的余数r m=n n=r r=0？ 是 输出m 结束 否 小组展示 程序框图： 小组合作 小组合作，设计“辗转相除法”的计算机程序，并 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
