0

我必须确保 3 个数字之间的 GCD 不大于 1。

这是我到目前为止的方法代码：

private int greatestCommonFactor(int a, int b, int c)
{
    for(int n = 0; n <= number; n++)
    {
        if()
    }

    return 1;
}

当return 1我开始在实验室工作时，它就已经在那里了。如何确保 GCD 不超过 1？并返回所有三个整数？

如果它有助于弄清楚需要做什么，这是代码的其余部分：

import static java.lang.System.*;

public class Triples
{
 private int number;

public Triples()
{
    this(0);
}

public Triples(int num)
{
    number = num;
}

public void setNum(int num)
{
    number = num;
}

private int greatestCommonFactor(int a, int b, int c)
{
    for(int n = 0; n <= number; n++)
    {
        if()
    }

    return 1;
}

public String toString()
{
    String output="";
    int max = number;
    for(a = 1; a <= max; a++)
    {
        for(b = a +1; b <= max; b++)
        {
            for(c = b + 1; c <= max; c++)
            {
                if(Math.pow(a, 2)+ Math.pow(b, 2)== Math.pow(c, 2))
                {
                    if((a%2==1 && b%2==0)|| (a%2==0 && b%2==1))
                }
            }
        }
    }


    return output+"\n";
}
}

更新

这是我为同一个实验室编写的新代码：

import static java.lang.System.*;

public class Triples
{
 private int number;

public Triples()
{
    this(0);
}

public Triples(int num)
{
    number = num;
}

public void setNum(int num)
{
    number = num;
}

private int greatestCommonFactor(int a, int b, int c)
{
    for(int n = 0; n <= number; n++)
    {
    int max = number;
    for(a = 1; a <= max; a++)
    {
        a = n;
        for(b = a +1; b <= max; b++)
        {
            b =n;
            for(c = b + 1; c <= max; c++)
            {
                c = n;
                if(Math.pow(a, 2)+ Math.pow(b, 2)== Math.pow(c, 2))
                {
                    if((a%2==1 && b%2==0)|| (a%2==0 && b%2==1))
                    {
                        if(a%2<=1 && b%2<=1 && c%2<=1)
                        {
                            return 1;
                        }
                    }
                }
            }
        }
    }
    }

    return 1;
}

public String toString()
{
    String output="";
    output = greatestCommonFactor(a, b, c);


    return output+"\n";
}
}
4

2 回答 2

4

您可以使用欧几里得算法来计算 和 的aGCD b。调用结果d。那么a,b和c的 GCD 是c和的 GCD d; 为此，您可以再次使用欧几里得算法。

于 2012-11-26T21:01:45.567 回答
0

如果您不关心效率，这是一种蛮力方法：

private int greatestCommonFactor(int a, int b, int c)
{
    limit = Math.min(a, b);
    limit = Math.min(limit, c);
    for(int n = limit; n >= 2; n--)
    {
        if ( (a % n == 0) && (b % n == 0) && (c % n == 0) ) {
            return n;
        }
    }

    return 1;
}

解释：

  • 您只需检查最少的(a, b, c). 任何大于此的数字绝对不会是所有 3 的 GCD。
  • 您需要开始循环n = limit而不是n = 0倒数。
  • 一旦我们遇到一个对 产生零余数的数字(a, b, c)，那一定是 GCD。
  • 如果在循环中找不到任何内容，则 GCD 默认为 1。
于 2012-11-26T21:02:26.987 回答