c - 为什么此代码在一定限制后不回复 nCr？

Question

这是从 this similar question 复制的代码的解决方案。为什么comb(100, 50)后失败了？我相信它不应该超过long long的限制。如果确实如此，我不应该期待运行时错误而不是错误的答案吗？

  long long comb(long long n, long long r) {
        long long limit = r;
        if(r>(n-r))
            limit = n-r;
        long long sum = 1;
        long long i=0;
        while(i<limit){
            sum *= n-i;
            sum /= i+1;
            i++;        
        }
        return sum % 1000000007;
    }

我期望 100C50 % 1000000007 的正确答案是 538992043(使用帕斯卡三角形方法计算)，而不是 354365244。

Answer 1

我认为你应该阅读你的尖锐答案，然后尝试模拟一些代码。正如您尖锐的答案所示，这里的问题很可能是整数溢出。

在读取long long声明后，C仅被迫分配它认为应该分配的空间；换句话说，根据平台的不同，long long 可以分配可变数量的字节，且不能短于 C 约定设置的限制。

This这篇文章应该能让您了解该语言的这个特定方面。

另一方面，假设您传递到 C++，您可以使用专用的 Decimal 类来存储数字的数字，然后消除 long long int 内存大小问题.

关于运行时错误，如果您尝试写入未分配的数据，C 甚至不需要发出警报。假设您有一个 unsigned int (根据定义，它至少可以存储 0 到 65535 之间的数字(请参阅 this ))。如果你尝试写一个比这个数字更大的数字，比如 70000，C 会很乐意写这个；但是您声明的 int 将存储一个荒谬的数字。发生的情况是，要写入 70000，C 必须写入比 int 所能容纳的多一个字节。它会写入，但结果将是垃圾。如果您尝试访问并写入“ protected ”内存，它只会给出运行时错误。

您还可以尝试使用unsigned long long int(对于遵循 C99 标准的编译器)保证至少保存 0 到 18446744073709551615 之间的数字。