探究一,辗转相除法冖 思考1:在小学中我们是如何求出两个正整数 的最大公约数的呢? 算法案例之求最大公约数 例、求18与24的最大公约数: 解:2|1824用公有质因数2除, 3L12用公有质因数3除,短除法 343和4互质不除了 得:18和24最大公约数是:2×3=6 求以下几组正整数的最大公约数。 (注:若整数m和n满足n整除m,则(m,n)=n。用(m,n)来表示 m和n的最大公约数。 (1)(18,30)6 (2)(24,16)8 (3)(63,63)63 (4)(72,8)8 (5)(301,133)7; 想一想,如何求8251与6105的最大公约数?
探究一,辗转相除法 思考1:在小学中我们是如何求出两个正整数 的最大公约数的呢? 算法案例之求最大公约数 求以下几组正整数的最大公约数。 (注：若整数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 ） 解：2 1 8 2 4 用公有质因数2除， 3 9 1 2 用公有质因数3除， 3 4 3和4互质不除了。 得：18和24最大公约数是：2×3＝6 例、求18与24的最大公约数： 6； 8； 63； 8； 7； 短除法 想一想，如何求8251与6105的最大公约数？
思考2对于8251与6105这两个数,它们的最大 公约数是多少?你是怎样得到的? 由于它们公有的质因数较大,利用上述方法求 最大公约数就比较困难.有没有其它的方法可以较简 单的找出它们的最大公约数呢?
思考2:对于8251与6105这两个数，它们的最大 公约数是多少？你是怎样得到的？ 由于它们公有的质因数较大，利用上述方法求 最大公约数就比较困难.有没有其它的方法可以较简 单的找出它们的最大公约数呢？
思考3:注意到82516105×1+2146,那么8251 与6105这两个数的公约数和6105与2146的公约数有 什么关系? 我们发现6105=2146×2+1813,同理,6105与 2146的公约数和2146与1813的公约数相等 思考4:重复上述操作,你能得到8251与6105这 两个数的最大公约数吗? 8251-6105×1+2146,1813=333×5+148, 6105=21416×2+1813,33148×2+37, 2146=1813×1+333,148=37×4+0 定义:所谓的辗转相除法,就是对于给定的两个数, 用较大的数除以较小的数若余数不为零,则将余数 和较小的数构成新的数对继续上面的除法,直到数 被小数除尽则这是较小的数就是原来两个数的最公强
思考3：注意到8251=6105×1+2146，那么8251 与6105这两个数的公约数和6105与2146的公约数有 什么关系？ 我们发现6105=2146×2+1813，同理，6105与 2146的公约数和2146与1813的公约数相等. 思考4：重复上述操作，你能得到8251与6105这 两个数的最大公约数吗？ 2146=1813×1+333， 148=37×4+0. 333=148×2+37， 8251=6105×1+2146， 1813=333×5+148， 6105=2146×2+1813， 定义:所谓的辗转相除法,就是对于给定的两个数, 用较大的数除以较小的数,若余数不为零,则将余数 和较小的数构成新的数对,继续上面的除法, 直到大数 被小数除尽,则这是较小的数就是原来两个数的最大公约数
思考4:辗转相除直到何时结束? 主要运用的是哪种算法结构? 辗转相除法是一个反复执行直到余数等于0停止的步骤, 这实际上是一个循环结构 辗转相除法求两个数的最大公约数,其算法可以描述如下: ①输入两个正整数m和n; ②求余数r:计算m除以n,将所得余数存放到变量r中; ③更新被除数和余数:m=n,n=r ④判断余数r是否为0:若余数为0则输出结果,否则转 向第②步继续循环执行。 如此循环,直到得到结果
辗转相除法求两个数的最大公约数，其算法可以描述如下： 辗转相除法是一个反复执行直到余数等于0停止的步骤， 这实际上是一个循环结构 思考4：辗转相除直到何时结束？ 主要运用的是哪种算法结构？ 如此循环，直到得到结果。 ① 输入两个正整数m和n； ② 求余数r：计算m除以n，将所得余数存放到变量r中； ③更新被除数和余数：m=n，n=r。 ④判断余数r是否为0：若余数为0则输出结果，否则转 向第②步继续循环执行
思考5:你能把辗转相除法编成一个计算机程序吗? 第一步,给定两个正整数m,nm>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； 否则，返回第二步. 思考5:你能把辗转相除法编成一个计算机程序吗？