0

这是从这个类似问题的解决方案中复制的代码。为什么说 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。

4

2 回答 2

1

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

阅读long long声明后，C 只被迫分配它认为应该分配的空间；换句话说，取决于平台，long long 可以分配可变数量的字节，不会比 C 约定设置的限制短。

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

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

关于运行时错误，如果您尝试写入未分配的数据，C 甚至不需要发出警报。假设您有一个unsigned int（根据定义，它至少可以存储一个介于 0 和 65535 之间的数字（参见this））。如果你尝试写一个比那个更高的数字，比如 70000，C 会很乐意写那个；但是您声明的 int 将存储一个荒谬的数字。发生的事情是，要写 70000，C 必须写一个字节，超出了int可以容纳的范围。它会写，但结果将是垃圾。如果您尝试访问和写入“受保护”内存，它只会给出运行时错误。

您也可以尝试使用unsigned long long int它（对于遵循 C99 标准的编译器）保证至少包含 0 到 18446744073709551615 之间的数字。

于 2013-08-15T23:50:27.457 回答
0

我很可能是错的，但对我来说，您似乎在计算 100!/(50!^2)，大约为 1*10^29，而 unsigned long long int 只能处理 18,446,744,073,709,551,615。所以这将是一个溢出的情况。

于 2013-08-16T02:08:23.640 回答