算法案例之求最大公约数课件.pptx

算法案例之求最大公约数;;定理： 已知m,n,r为正整数，若m=nq+r（0≤r<n）（即r=m MOD n） ,则（m,n）=(n,r)。;练习：用辗转相除法求下列两数的最大公约数：;;思考：辗转相除直到何时结束？主要运用的是哪种算法结构？ 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构 辗转相除法求两个数的最大公约数，其算法可以描述如下： ① 输入两个正整数m和n； ② 求余数r：计算m除以n，将所得余数存放到变量r中； ③更新被除数和余数：m=n，n=r。 ④判断余数r是否为0：若余数为0则输出结果，否则转向第②步继续循环执行。 如此循环，直到得到结果。;;更相减损术;例、用更相减损术求98与63的最大公约数;练习：用更相减损术求下列两数的最大公约数：;例 用更相减损术求98与63的最大公约数 解：由于63不是偶数，把98和63以大数减小数，;更相减损是一个反复执行直到减数等于差时停止的步骤，这实际也是一个循环结构;程序： INPUT “a,b”;a,b i=0 WHILE a MOD 2=0 AND b MOD 2=0 a=a/2;小 结;作业： P38 习题：1.3 第一题;2019-11-7;算法案例之求最大公约数;;定理： 已知m,n,r为正整数，若m=nq+r（0≤r<n）（即r=m MOD n） ,则（m,n）=(n,r)。;练习：用辗转相除法求下列两数的最大公约数：;;思考：辗转相除直到何时结束？主要运用的是哪种算法结构？ 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构 辗转相除法求两个数的最大公约数，其算法可以描述如下： ① 输入两个正整数m和n； ② 求余数r：计算m除以n，将所得余数存放到变量r中； ③更新被除数和余数：m=n，n=r。 ④判断余数r是否为0：若余数为0则输出结果，否则转向第②步继续循环执行。 如此循环，直到得到结果。;;更相减损术;例、用更相减损术求98与63的最大公约数;练习：用更相减损术求下列两数的最大公约数：;例 用更相减损术求98与63的最大公约数 解：由于63不是偶数，把98和63以大数减小数，;更相减损是一个反复执行直到减数等于差时停止的步骤，这实际也是一个循环结构;程序： INPUT “a,b”;a,b i=0 WHILE a MOD 2=0 AND b MOD 2=0 a=a/2;小 结;作业： P38 习题：1.3 第一题;2019-11-7;