爪哇 - 欧几里德算法

的递归函数，我似乎无法以下算法转换成Java的成功，请原谅可怕的画面质量，但我工作的一个问题是问：爪哇 - 欧几里德算法

Euclidean Algorithm

我试图用下面的代码来表示欧几里得算法，但它似乎不起作用。我真的不知道我会如何去代表Java代码。任何帮助？

public static int gcd(int x, int y) { 
    if (y == 0) { 
     return x; 
    } else if (x >= y && y > 0) { 
     return gcd(y, (x % y)); 
    } 
}

谢谢。

来源

2011-12-31 mino

您正在关注文本书算法。只是文本书算法不完整 - 因为它没有考虑两个类都不满足的情况。 – Mysticial 2011-12-31 18:19:55

它不起作用？你打电话时究竟发生了什么？你传递了什么论点，它返回什么？ – 2011-12-31 18:20:12

@KeithThompson我相信OP的直接问题是代码不能编译。 – dasblinkenlight 2011-12-31 18:22:33

x和y之间没有任意的顺序。

来源

2011-12-31 18:30:00

'return y == 0？ x：gcd（y，x％y）;''就是你需要的。哪个更重要并不重要。不过，它会采取更多的递归。 – st0le 2012-01-02 07:45:02

仅供参考：此答案以前更有帮助（请参阅编辑历史记录）。 – nobar 2015-02-21 04:19:22

你快到了。您需要考虑y > x时发生的情况，并从最终的else分支返回结果（提示：x和y可以自由切换地点）。

来源

2011-12-31 18:20:28 dasblinkenlight

你快到了。

您的代码不能编译，因为没有捕获从函数返回的所有子句。

这实际上取决于您是否要将y的负值传递给此函数。如果你期望只有正值，就抛出一个异常。

public static int gcd(int x, int y) { 

    if (y == 0) { 

     return x; 

    } else if (x >= y && y > 0) { 

     return gcd(y, (x % y)); 

    } 

    throw 
     new IllegalArgumentException(
      String.format(
       "Unexpected values for x(%d) and y(%d)", 
       Integer.valueOf(x), 
       Integer.valueOf(y) 
      ) 
     ); 
}

来源

2011-12-31 18:21:09

理想情况下，我想包含负值。 – mino 2011-12-31 18:22:13

@ m92来自作业的递归公式不包括负数。 – dasblinkenlight 2011-12-31 18:26:34

您的代码不完整！如果？你的代码不会返回值！

本书未提及的是函数的两个参数不一定需要按降序排列（即x >= y）。考虑到这个事实，你需要做的是计算gcd。

只要你能做到以下几点：

public static int gcd (int x , int y) 
{ 
    if (y == 0)       
     return x; 
    else if (x >= y && y > 0) 
     return gcd (y , x % y); 
    else return gcd (y , x);  // if x < y then go ahead and switch them around. 
}

来源

2011-12-31 18:40:44

这里是我有一个账户负数：负数

public static int gcd(int x, int y) 
{ 
    if (y == 0) 
     return x; 
    if (x < 0) 
     return gcd(x * -1, y); //turns the first parameter to a positive if it's initally negative 
    if (y < 0) 
     return gcd(x, y * -1); //turns the second parameter to a positive if it's initally negative 
    if (y <= x && x % y == 0) 
     return y; 

    return gcd(y, x%y); 
}

注意，如果你试图找到最大公约数，并且其中任何一个数字都是负数，您可以将其更改为正数，结果将相同。

如果这两个数字都是负数，那么我不确定gcd应该是什么。 1？ -1？ idk，所以我离开了。我刚刚看到的代码就好像它们都是正面的。

来源

2014-09-30 09:20:59

爪哇 - 欧几里德算法

回答

相关问题