医院招聘网站建设和维护,摄影设计方案,工作啦,丽水高端网站建设更相减损法和辗转相除法#xff08;GCD#xff09;求最小公倍数和最大公约数 标签#xff08;空格分隔#xff09;#xff1a; 算法 算法竞赛 这两种算法平时经常听到#xff0c;听起来也很装逼#xff0c;但是我老是忘了他们的原理#xff0c;今天好好想想#xff0c… 更相减损法和辗转相除法GCD求最小公倍数和最大公约数 标签空格分隔 算法 算法竞赛 这两种算法平时经常听到听起来也很装逼但是我老是忘了他们的原理今天好好想想写下来。 更相减损法 更相减损法最早起源于我国的《九章算术》用于求两个数的最小公倍数。大意是给定两个数a,b如果存在偶数就将偶数以2否则就比较两数大小用大数减小数得到一个差对差和剩下的那个小数重复该过程直到两数相等下一次相减结果为0这时的数就是a和b的最大公约数。注意去掉偶数除以2的步骤也正确但是加上这一步可能会让时间复杂度减少。 例如15和12。15-12312-399-366-3333跳出。则最大公因数是3。 算法的C/C代码写法如下(循环实现int gcdgxjs(int a,int b) {while (a!b) {if (aif (ab) a-b;else b-a;}return a;
) 辗转相除法 辗转相除法最早是由欧几里得发现的也被用来求最大公约数。算法是这样的给定两个数ab求a%b如果余数非0就继续用除数除以余数重复该过程直到除数为0。此时的被除数就是最大公约数。 例如42和12。42%12612%6060此时的6即为最大公约数。 算法的C/C代码写法如下递归实现int gcd(int a,int b) {if (b0)return a;gcd(b,a%b);
} 上面就是这两个算法的具体实现过程。除此之外再补充一个定理两个正整数ab。假设他们的最大公约数是p最小公倍数是q则qa*b/p即abpq。证明很简单多想想就好了在此不再赘述。 转载于:https://www.cnblogs.com/yichuan-sun/p/9624172.html
