为什么下面的代码是错误的？二项式系数

Question

我正在做欧拉项目，现在遇到第 15 个问题，这里是 link： https://projecteuler.net/problem=15 . I am trying to solve this with binomial coefficient. Here is a site that explains it: http://www.mathblog.dk/project-euler-15/。你可以在底部找到它。

我的问题是，为什么下面的代码是错误的？由于这遵循我认为的数学算法：n-k+i/i

        int grid = 20;
        long paths = 1;
        for (int i = 0; i < grid; i++)
        {
            paths *= (grid * 2) - (grid + i)
            paths /= (i + 1);
        }
        Console.WriteLine(paths);
        Console.ReadKey();

为什么这段代码是错误的？这与数学博客网站完全一样，但只有 1 行。

        int grid = 20;
        long paths = 1;
        for (int i = 0; i < grid; i++)
        {
            paths *= ((grid * 2) - i) / (i + 1);
        }
        Console.WriteLine(paths);
        Console.ReadKey();

但是为什么这段代码是正确的呢？是不是和之前的代码一样？它并不完全遵循数学算法，对吗？因为是n-k+i/i，而这段代码做的是n-i/i

       int grid = 20;
        long paths = 1;
        for (int i = 0; i < grid; i++)
        {
            paths *= ((grid * 2) - i);
            paths /=  (i + 1);
        }
        Console.WriteLine(paths);
        Console.ReadKey();

谢谢大家！

Answer 1

如果要合并计算应该是这样的

paths = (path *((grid * 2) - i))/(i + 1);

Answer 2

按照惯例，在许多编程语言中，int/int 给出一个 int，* 而不是浮点数。您的方法意味着 'paths' 应该采用非整数值。事实上，这三种方法中的 none 应该有效，但巧合的是，最后一种方法有效：基本上是因为 'paths' 的所有中间值恰好也是二项式系数。

调试建议：让你的程序输出中间值。这很有帮助。

*：作为一名数学家，我几乎从不需要那个功能。事实上，另一个约定（int/int -> double）平均来说会让我作为程序员的生活更轻松。

我看过你提到的博客。这使您的信息更容易理解。博客中提到了一个公式：i从1到k的乘积(n-k+1)/i。所以要模仿它你需要写

    for (int i = 1; i <= grid; i++) // bounds!
    {
        paths *= (grid * 2) - (grid - i) // minus sign!
        paths /= (i + 1);
    }

关于这适用于整数的事实：这是一个意外，因为乘积的中间值（在每个循环的末尾）在整个计算过程中都是二项式系数。如果您按其他顺序计算乘积和除法，则很可能会得到非整数，因此由于约定 int/int -> int，计算将因路径的整数变量类型而失败。该博客在不提及这一点上不是很有帮助。

为什么下面的代码是错误的？二项式系数

Why is the following code wrong? binomial coefficient

c#

algorithm

grid

binomial-coefficients