4

我尝试用 Java 编写递归 Ackermann 函数。但我想我在某个地方走错了！任何人都可以看看，检查并指出我纠正代码的正确方向吗？谢谢！

阿克曼

我对代码的问题是，在我写完它之后，我想，如果 n == 0 和 m == 0，没有这个区域怎么办？这会属于 if (m == 0) 还是需要它自己的 if 语句？

我的以下解决方案是否正确？如果我以不同的顺序给它相同的数字，它会给出不同的结果，我不确定这是否是这种情况。

public static int ackermann(int m, int n) {

        if (m == 0) {

            return n + 1;

        } else if ((m > 0) && (n == 0)) {

            return ackermann(m-1, n);

        } else if ((m > 0) && (n > 0)) {

            return ackermann(m-1, ackermann(m,n-1));

        } else {

            return 0;

        }

    }

我想了更多，我认为我错得更大。如果你不知道我做了什么，我给了每个 if 语句一个相反的，因为我认为如果 m 和 n 值以不同的方式给出，下面的代码将起作用。显然没有，但有人可以尝试解释我哪里出错了吗？

public static int ackermann(int m, int n) {

        if (m == 0) {

            return n + 1;

        } else if (n == 0) {

            return m + 1;

        } else if ((m > 0) && (n == 0)) {

            return ackermann(m-1, n);

        } else if ((n > 0) && (m == 0)) {

            return ackermann(n-1, m);

        } else if ((m > 0) && (n > 0)) {

            return ackermann(m-1, ackermann(m,n-1));

        } else if ((n > 0) && (m > 0)) {

            return ackermann(n-1, ackermann(n, m-1));

        } else {

            return 0;

        }

    }
4

5 回答 5

5

这部分是错误的：

    } else if ((m > 0) && (n == 0)) {
        return ackermann(m-1, n);

那应该是A(m - 1, 1)

于 2012-01-01T16:19:08.660 回答
5

我认为您的第一个版本几乎是正确的。我会稍微修改一下：

public static int ackermann(int m, int n) {
    if (m < 0 || n < 0) {
        throw new IllegalArgumentException("Non-negative args only!");
    }

    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermann(m-1, 1); // Corrected!
    } else {
        // perforce (m > 0) && (n > 0)
        return ackermann(m-1, ackermann(m,n-1));
    }
}

案件m == 0 && n == 0应列入m == 0案件。

编辑：请注意，阿克曼函数仅针对非负参数定义。特别是ackermann(0, -1)应该抛出异常。因此，您不能只将最后一个else子句转换为throw.

于 2012-01-01T16:21:16.773 回答
2

有趣的是，您的问题的所有答案都指出了您在第一个版本中的错误，但对第二个版本中的大错误只字未提

 else if (n == 0) {
        return m + 1;
    }

其中，对于正整数，在条件上等价于

else if ((m > 0) && (n == 0)) {
        return ackermann(m-1, n);
    }

因此，您的函数将返回 m+1 而不是 ackermann(m-1, 1) ，这应该适用于第二种情况 ((m > 0) && (n == 0)) 。

于 2017-12-16T01:37:33.520 回答
1

“如果 m = 0”规则适用于 n 的所有值，因此 A(0, 0) 为 1。

'else' 子句只能在 m 和 n 在进入函数时都为负数时使用，这可以被诊断为异常。实际上，如果 m 或 n 为负数，您应该诊断错误。或者，由于 A(m, n) 在其他情况下永远不会返回零，因此可以将 0 视为指示错误。

请注意，评估 A(m, n) 所需的堆栈深度与答案相同 - 并且 A(m, n) 很快就会变得非常大。不要费心尝试评估 A(4, 4); 您的计算机没有足够的内存。

于 2012-01-01T16:18:32.920 回答
0

第一个片段是好的，除了它返回ackermann(m-1, n)而不是ackermann(m-1, 1)在第二种情况下。默认情况下不应该发生，应该抛出一个IllegalStateException以防它实际发生。

于 2012-01-01T16:20:51.830 回答