CodeRookie


私信TA

用户名:Shmily124

访问量:133465

签 名:

清风前烹茶对弈,明月下把酒言欢

等  级
排  名 14
经  验 22966
参赛次数 7
文章发表 39
年  龄 0
在职情况 学生
学  校 ZUA
专  业 计科

  自我简介:

悄悄地秃头,然后惊艳所有人?

解题思路:


很多人都用辗转相除法来递归,但是我们上中学时用的更多的应该是短除法,或者叫倒除法,我们进行进制转换时也会用到这种方法

所以我想利用短除法写出代码来表示,也是给大家提供一种不同的思考方式

那么什么是短除法:

假设我们输入 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


图片:

20200421113208150.jpg


参考代码:

#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;
 }
大佬们,萌新,请问哪里有问题?谢谢!
2021-12-08 15:09:01
1、j 和 k 多余了吧,为什么要确保 m和n 要对最小的、最少的数取余? 多了也不碍事啊!2、for循环:i 为什么要重置?if 条件 符号一次就够了啊,重置用来干嘛?
2021-11-28 09:43:38
#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-27 19:00:58
发个函数的做法
#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);
}
2021-11-15 20:01:15
//看那些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-10-21 22:42:12
#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 21:30:35
#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;
}
2021-10-03 15:24:16
vs2012报错了啊
2021-09-28 20:02:42