gcd辗转相除算法

2024-01-07 17:42:44

2024年1月3日18:12:14还在玩ginka 目前的话香蕉会他们这种奇怪的算法?

2024年1月3日17:34:13完成了辗转相除解决了幕布的算法,这样艰巨的任务是否能交给我来完成呢?一切都是未知数。朋友,答案在空中飘荡。

//建立一个
#include<stdio.h>
int main()
{
    int gcd(int a,int b);
    int x,y,t;
    while(scanf("%d%d",&x,&y),x||y)
    {
        t=gcd(x,y);
        printf("%d\n",(x/t)*(y/t));
    }
    return 0;
}
int gcd(int a,int b)
{
    return b==0 ? a : gcd(b,a%b);
}

????????

这边还要掌握三元运算符

这边是递归算法的实现过程

这段代码是一个递归函数的一部分,用于计算两个整数的最大公约数(GCD)。这是使用欧几里得算法的一个实现。

代码解释如下:

c
return b==0 ? a : gcd(b,a%b);
b==0 ? a : ...: 这是一个三元运算符。它的工作原理是:如果 b 等于0,则返回 a 的值;否则返回 ... 的值。
gcd(b,a%b): 这是递归调用。它再次调用 gcd 函数,但是这次使用的参数是 b 和 a % b。这里的 % 是取余操作,它返回 a 除以 b 的余数。
这个递归调用的逻辑基于以下事实:两个整数的最大公约数与较小的数和两数的余数之间的最大公约数是相同的。例如,考虑数字 48 和 18:

GCD(48, 18) = GCD(18, 48 % 18) = GCD(18, 12)
GCD(18, 12) = GCD(12, 18 % 12) = GCD(12, 6)
GCD(12, 6) = GCD(6, 12 % 6) = GCD(6, 0)
在上面的例子中,当余数为0时,这意味着较小的数(在这里是6)就是两数的最大公约数。

这个递归过程会一直持续,直到找到最大公约数,然后该值会被返回。

另外一种可能是得到这种东西

文章来源:https://blog.csdn.net/leke2003/article/details/135369503
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。