0 
public static int divisor(int m, int n) {
    if (m == 0 || n == 0) {
        return m+n;
    } else {
        return divisor(n, m%n);
    }
}

它在 amazon.interviewstreet.com 中给了我一些输入的错误答案（我不知道是哪个，因为他们没有透露他们用于测试用例的输入）

还有为什么这个实现一直给我stackoverflow（再次不知道哪些输入）

public static int divisor(int m, int n) {
    if(m == 0 || n == 0) {
        return m+n;
    } else if (m > n) {
        return divisor(n, m%n);
    } else {
        return divisor(m, n%m);
    }
}

请让我知道我错过了什么。我是编程新手，仍然是初学者。

4

6 回答 6

1

我认为第一个是编程竞赛的代码。如果是这样，请注意您的数据类型。可能是 'int' 不足以容纳输入。尝试“长”。（这只有在你的算法正确的情况下才有效。）

于 2013-07-11T20:21:18.030 回答
1

第二部分是什么

返回(m, n%m);

这段代码是否被编译？

利用 ：

public static int divisor(int m, int n) {
if(m == 0 || n == 0)
    return m+n;
else if(m>n)
    return divisor(n, m%n);
else
    return divisor(m, n%m);}
于 2013-07-11T20:12:23.627 回答
1

第一的，

return(m, n%m)

绝对不能编译，我想它本来就是

return divisor(m, n%m);

其次，我猜第二个片段中的错误是处理负数。因为 A 和 B 与 -A 和 -B 具有相同的 GCD，所以我会添加

m = Math.abs(m);
n = Math.abs(n);

到方法的开头

于 2013-07-11T20:13:37.273 回答
1

我认为

return(m, n%m);

应该

return divisor(m, n%m);

于 2013-07-11T20:02:06.830 回答
1

n可能无效处理and的负值m？阅读例如：让Java的模数表现得像负数一样的最佳方法？

于 2013-07-11T20:06:50.257 回答
1

对于第二部分：

还有为什么这个实现总是给我stackoverflow（再次不知道哪些输入）？

试试这个输入集：

5 3 1 16 5 10

它会给你stackoverflow错误。对于您在 pastebin 中的给定代码。

为什么 ？

如果输入是'1'，就会出现这个问题。

编辑您的代码部分，如下所示，并查看输入的输出 (1 1)。

public static int divisor(int m, int n) {
    System.out.println("### "+m+" "+n);
    if (m == 0 || n == 0) {
        return m + n;
    } else if (m > n) {
        return divisor(n, m % n);
    } else {
        return divisor(m, n % m);
    }
}

在某些方面会是这样的：

.
.
### 1 1134903170
### 1 0
### 1 1836311903
### 1 0
### 1 -1323752223
### -1323752223 1
### -1323752223 1
### -1323752223 1
.
.

因为在您的代码中，函数调用如下所示。

   public static int divFib(int num) {
    int i = 1, j = 2, temp;

    while (divisor(num, j) == 1) {
        temp = j;
        j = j + i;
        i = temp;
    }
    return j;
   }

divisor(num, j) 将像 divisor(1, 2) 一样被调用，然后下面的部分将执行

else {
        return divisor(m, n % m);
    }

调用将类似于除数（1,0），因为 n%m = 2%1 =0

那么 '1' 将作为 (m+n = 1) 返回。

然后 while (divisor(num, j) == 1){} 将再次执行并且 'j' 将增加。但是'num'是'1'。同样的事情一次又一次地发生。结果 'j' 是一个巨大的数字，最终它将分配一个负数。（我想你知道它为什么会发生）。

问题是这永远不会停止。因此堆栈将由于大量的函数调用而溢出。

我认为这是一个非常清楚的解释，如果您有任何疑问，请询问。（对不起，我错误地在这里发布了答案。）

于 2013-07-13T15:33:02.153 回答