[开始 程序框图 输入m,D INPUT m. n DO 求m除以m的余数r =m mod n m-n h-r n-r LOOP UNTIL r=0 02 PRINT m END 输出m [结束」
程序框图 开始 输入m，n 求m除以n的余数r m=n n=r r=0？ 是 输出m 结束 否 INPUT m，n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END
思考6:如果用当型循环结构构造算法,则用辗 转相除法求两个正整数m、n的最大公约数的程序框 图和程序分别如何表示?
思考6:如果用当型循环结构构造算法，则用辗 转相除法求两个正整数m、n的最大公约数的程序框 图和程序分别如何表示？
开始 INPUT m, n 输入m,n WHILE r>0 n-r =m mod n M-n 上-n n-r 求m除以n的余数r WEND PRINT m r≠0 END 输出m 结割
开始 输入m，n 求m除以n的余数r m=n r≠0 ？ 否 输出m 结束 是 n=r INPUT m，n WHILE r<>0 r=m MOD n m=n n=r WEND PRINT m END
练习:用辗转相除法求下列两数的最大公约数: (1)(225,135)45(2)(98,196)98 (3)(72,168)24(4)(153,119)17
练习：用辗转相除法求下列两数的最大公约数： （1）（225，135） （2）（98，196） （3）（72，168） （4）（153，119） 45 98 24 17
二、更相减损术 《九章算术》是中国古代的数学专著,其中的 更相减损术”也可以用来求两个数的最大公约数, 即“可半者半之,不可半者,副置分母、子之数, 以少减多,更相减损,求其等也以等数约之” 意思是: 第一步:任意给定两个正整数,判断它们是否 都是偶数.若是,用2约简;若不是,执行第二步 第二步:以较大的数减去较小的数,接着把差 与较小的数比较,并以大数减小数继续这个操作 直到所得的数相等为止,则这个等数或这个数与约 简的数的乘积就是所求的最大公约数
二、更相减损术 《九章算术》是中国古代的数学专著，其中的 “更相减损术”也可以用来求两个数的最大公约数， 即“可半者半之，不可半者，副置分母、子之数， 以少减多，更相减损，求其等也.以等数约之.” 意思是： 第一步：任意给定两个正整数，判断它们是否 都是偶数. 若是，用2约简；若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把差 与较小的数比较，并以大数减小数.继续这个操作， 直到所得的数相等为止，则这个等数或这个数与约 简的数的乘积就是所求的最大公约数