辗转

2146=1813 1+333 1813=333 5+148 333=148 2+37 148=37 4+0 m = n q ＋ r 用程序框图表示出右边的过程 r=m MOD n m = n n = r r=0? 是 否 思考： 你能把辗转相除法编成一个计算机程序吗。 (1)、算法步骤： 第一步：输入两个正整数 m,n(mn). 第二步：计算 m除以 n所得的余数 r. 第三步： m=n

,直到大数被小数除尽 ,则这时的较小数就是原来两个数的最大公约数 . 2 .利用更相减损术求两个正整数的最大公约数的一般步骤是 :首先判断两个正整数是否都是偶数 .若是 ,用 2 约简 .也可以不除以 2 ,直接求最大公约数 ,这样不影响最后结果 . 3 .当两个整数的差较大时 ,利用辗转相除法计算的次数较少 . 【典型例题 1 】 求下列两数的最大公约数 : ( 1 ) 228 与 1 9 9

、评价分析 一、教材分析 二、目的分析 三、教法分析 四、过程分析 五、评价分析 一、教材分析 （二）理解辗转相除法原理 【 练 1】 求 678与 35的最大公约数。 【 设计意图 】 巩固练习 二、教法分析 三、过程分析 四、评价分析 一、教材分析 二、目的分析 三、教法分析 四、过程分析 五、评价分析 一、教材分析 (三）、设计辗转相除法算法 【 问 4】 写出两个正整数