0

根据 wiki 的 wiki catalan 定义,我看到以下表达式: 在此处输入图像描述

我可以理解前两个表达,但对第三个表达真的很困惑。pi 符号代表乘法。该表达式是否表示以下代码:

for (int i = 2; i < n + 1; i++) {
    sum *= (n + i)/i;
}

我的代码如下

public class Test {
public  int getCatalan(int n) {
    //Catalan Number = (2n)!/(n+1)!*n!
    int product = 1;
    if (n == 1)
        return 1;

    for (int i = 2; i < n + 1; i++) {
        product *= (n+i)/i;
    }
    return product;
}

public static void main(String[] args) {
    Test test = new Test();

    for (int i = 1;i < 7; i++) {
        System.out.println("when i=" + i + " its catalan number is "+ test.getCatalan(i));
    }
}

}

我得到的结果是完全错误的

在此处输入图像描述

有人帮我吗?

4

3 回答 3

2

是的。这大致就是它的意思(假设你初始化sum为 1)。

但要小心整数除法。如果你写(n + i)/iand 两者n都是i整数,你可能会发现自己在某些语言中有一些意想不到的输出。

例如,在 Java 中,如果n = 3i = 2(n + i)/i = 2而不是2.5,因为int / int = int和我们不能存储2.5在整数中。

如果您在某处投射某些东西double或在某处添加+ 0.0* 1.0,则结果将是double( double / int = double) 并且应该是正确的。

还要记住,sum它本身应该是一个double/ float,而不是一个int(因为sum不能存储2.5,类似于上面提到的)。如果您希望输出为int,则应该Math.round这样做。

int n = 3;
double product = 1;
for (int i = 2; i <= n; i++) {
   product *= (0.0 + n + i)/i;
}
System.out.println(product); // 5

(我也改为i < n + 1-i <= n后者对我来说似乎更清楚,但它在功能上并没有改变代码)

有关更多技术细节,请参阅 JLS -除法运算符 /二进制数字提升

于 2014-06-04T20:12:52.577 回答
1

是的。确保将sum(可能应该称为product)初始化为 1。

于 2014-06-04T19:52:21.913 回答
0

使用 longs 或 BigIntegers(或您使用的任何语言的等价物)可能更安全,以避免浮点错误。您可以只跟踪分子和分母并在最后进行除法。(或在步骤之间不断减少以减少溢出的机会)

long catalan(long n) {
    long p = 1;
    long q = 1;
    for (long k = 2; k <= n; k++) {
        p *= (n + k);
        q *= k;

        // these 3 lines are optional, and just delay when overflow happens
        long gcd = gcd(p, q);
        p /= gcd; 
        q /= gcd;
    }
    return p / q;
}

在此处查看比较:https ://coderpad.io/565957使用双打将在 n=30 时给您错误的答案,而 gcd 我的只有 33 好,但您可以轻松地将 BigIntegers 的 long 换成无限期.

于 2014-06-05T02:42:06.753 回答