解题思路:
很多人都用辗转相除法来递归,但是我们上中学时用的更多的应该是短除法,或者叫倒除法,我们进行进制转换时也会用到这种方法
所以我想利用短除法写出代码来表示,也是给大家提供一种不同的思考方式
那么什么是短除法:
假设我们输入 m=12,n=18 ,初始化最大公约数 gcd=1
我们发现 2 是12和18的一个公因子
我们令 m /= 2 ,n /= 2 ,gcd *= 2
现在 m == 6 , n == 9 , gcd == 2
又发现 3 是 6 和 9 的一个公因子
我们令 m /= 3 , n /= 3 , gcd *= 3
现在m == 2 , n == 3 , gcd == 6
我们找不到除 1 以外的 2 和 3 的公因子了
所以现在的 gcd == 6 就是我们要找的最大公因数
而最小公倍数 lcm = gcd * m * n = 6 * 2 * 3 = 36
图片:
参考代码:
#include <stdio.h> int main() { int m, n; int j, k; int lcm, gcd = 1; scanf("%d %d", &m, &n); //输入m和n j = m, k = n; //用j和k表示m和n,不破坏m与n的值 if (j > k) { j = n, k = m; //确保j是较小的那个 } for (int i = 2; i <= j; i++) //循环寻找从i到j的因子(注意j是可变的,而i会被重置) { if (j % i == 0 && k % i == 0) //判断i是否为j和k的公因子 { j /= i; k /= i; //j与k分别除以i gcd *= i; //gcd乘以i i = 1; //将i重置为1 (循环末尾会i++) } } lcm = gcd * j * k; //求出最小公倍数lcm printf("%d %d", gcd, lcm); //输出gcd与lcm return 0; }
看了评论区的诸多意见,决定重写这份时隔一年的代码:
//短除法求公约公倍 #include <stdio.h> int main() { int m, n; scanf("%d %d", &m, &n); int gcd = 1; for (int i = 2; i <= m && i <= n; i++) { while (m % i == 0 && n % i == 0) { m /= i; n /= i; gcd *= i; } } printf("%d %d\n", gcd, m * n * gcd); return 0; }
短除法可能便于理解,但效率其实并不理想,时间复杂度可以达到O(n)(当输入质数时)
而辗转相除法被推断出时间复杂度为 O(log(n))
所以还是建议使用辗转相除法,代码量少且运算速度快:
//辗转相除法求公约公倍 #include <stdio.h> int gcd(int a, int b) { return (a % b == 0) ? b : gcd(b, a % b); } int main() { int m, n; scanf("%d %d", &m, &n); int ans = gcd(m, n); printf("%d %d\n", ans, m * n / ans); return 0; }
0.0分
271 人评分
#include<stdio.h> int main() { int a,b,j,k,i,x; scanf ("%d%d",&a,&b); j=a,k=b; if(b<a) j=b; k=a; for (i>0;i<j;i--) { if(j/i==0&&k/i==0) break; } printf("%d",i); x=(j*k)/i; printf("%d",x); return 0; } 大佬们,萌新,请问哪里有问题?谢谢!
1、j 和 k 多余了吧,为什么要确保 m和n 要对最小的、最少的数取余? 多了也不碍事啊!2、for循环:i 为什么要重置?if 条件 符号一次就够了啊,重置用来干嘛?
骏 2021-11-28 09:45:36 |
if 条件 符合一次 就可以出结果啊,重置 'i' 是为什么???”
笔墨 2021-12-22 21:08:30 |
符合一次不一定啊,它的for每循环一次是找最小公因数,所以它要找到每次最小公因数的结果然后相乘才能得到最大公因数
jxnbhckmshckabckmsbfkdnfjzghsbfkdudn 2022-01-22 13:16:57 |
@aj1433223 因为i是从2开始的,而不是从j开始的。可能出现两个公因子都是2.
#include <stdio.h> int main() { int a,b,c; while(a) { scanf("%d%d",&a,&b); printf("%d\n",a*b); c=a%b; while(c) { a=b; b=c; c=a%b; } printf("%d\n",b); } } 大佬,问下,我哪里错了
骏 2021-11-28 09:41:53 |
1、j 和 k 多余了吧,为什么要确保 m和n 要对最小的、最少的数取余? 多了也不碍事啊!2、for循环:i 为什么要重置?if 条件 符号一次就够了啊,重置用来干嘛?
发个函数的做法 #include <stdio.h> int gcd(int n, int m); int lcm(int n, int m); int main() { int n, m; scanf("%d%d", &n, &m); printf("%d\n", gcd(n, m)); printf("%d\n", lcm(n, m)); return 0; } int gcd(int n, int m) { if (m <= n) { return m == 0 ? n:gcd(m, n % m); } else { return gcd(m, n); } } int lcm(int n, int m) { return n * m / gcd(n,m); }
EasyHuang 2022-03-04 21:10:24 |
emm 函数部分能解释下嘛,新手求教.
//看那些i j k通常好头大,我喜欢有点可读性 #include <stdio.h> int main(int argc, char* argv[]) { int maxFac =1, minMult = 1, a, b, i; scanf("%d%d", &a, &b); for (i = 1; i <=a; i++){ if (a%i == 0 && b%i == 0) { maxFac = i; } minMult = a*b/maxFac; } printf("%d %d\n", maxFac,minMult); return 0; }
狗子 2021-11-15 20:00:23 |
接龙,发一个函数的做法 #include <stdio.h> int gcd(int n, int m); int lcm(int n, int m); int main() { int n, m; scanf("%d%d", &n, &m); printf("%d ", gcd(n, m)); printf("%d ", lcm(n, m)); return 0; } int gcd(int n, int m) { if (m <= n) { return m == 0 ? n:gcd(m, n % m); } else { return gcd(m, n); } } int lcm(int n, int m) { return n * m / gcd(n,m); }
#include<stdio.h> int main() { int n,m,a,b; scanf("%d%d",&n,&m); a=m/n; b=n*m; printf("%d %d\n",a,b); return 0; } 我的结果没错但是没通过
怪兽兽 2021-10-21 22:39:09 |
因为你这个a 和b的算法只针对5和7那个例子,不是通例
#include <stdio.h> int main () { int a,b; int c;//中间量 scanf("%d%d",&a,&b); int x=a,y=b;//储存初始输入值 while(1){ if(a<b){ c=a;a=b;b=c; } a%=b; float n=a,m=b; if(a/b==n/m) break;//根据两值是否相等,判断是否除尽,是则跳出循环 } printf("%d\n",b); printf("%d\n",x*y/b); return 0; }
【回文数(二)】 (C++代码)浏览:932 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1059 |
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)浏览:910 |
这可能是一个假的冒泡法浏览:1071 |
简单的a+b (C语言代码)浏览:564 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:484 |
WU-整除问题 (C++代码)浏览:648 |
Pascal三角 (C语言代码)浏览:707 |
交换Easy (C语言代码)浏览:805 |
1162答案错误,为什么浏览:700 |