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

本文关键字：二项式 错误 代码 为什么 | 更新日期: 2023-09-27 18:14:56

我正在做项目euler，我现在在问题15，这里是一个链接:https://projecteuler.net/problem=15。我试着用二项式系数来解它。这里有一个网站可以解释: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();

为什么这个代码是错误的?这与mathblog网站完全相同，只是在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();

感谢的人!

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

如果你想合并计算，它应该像这样

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

按照惯例，在许多编程语言中，int/int给出int，*不是浮点数。你的方法暗示'paths'应该接受非int型的值。事实上，这三种方法都不应该起作用，但幸运的是，最后一种方法起作用了:基本上是因为"路径"的所有中间值恰好也是二项式系数。

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

*:作为一名数学家，我几乎从不需要这个特性。实际上，另一种约定(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 -> int，对于path的整数变量类型计算将失败。博客没有提到这一点是没有多大帮助的。

相关文章：