c++ - 欧拉计划 114 和 115

Question

我遇到了项目 euler 问题 114 的问题。我已经解决了问题 115。114 不只是 F(3, 50) 吗？我使用组合方法而不是流行的递归方法。我不明白为什么不能解决 Q114。

问题 114

问题 115

unsigned long long Q114::nCr(unsigned long long n, unsigned long long r) {
    unsigned long long result = 1;
    for(unsigned long long i = 1; i <= r; i++)
        result *= (n--);
    while(r != 1)
        result /= (r--);
    return result;
}

unsigned long long Q114::find(unsigned long long leastunit, unsigned long long total) {
    unsigned long long max = (total + 1) / (leastunit + 1);
    unsigned long long sum = 0;
    for(unsigned long long i = 1; i <= max; i++) {
        unsigned long long slots =  2 * i;
        unsigned long long left = (total - i * leastunit - (i - 1));
        sum += nCr(left + slots, slots);
    }
    return sum;
}

void Q114::solve() {
    unsigned long long sum = find(3,50);
    std::cout << (++sum);
}

void Q114::solveQ115() {
    for (long start = 50;;++start) {
        std::cout << start << std::endl;
        if(find(50, start) > 1000000) { 
            std::cout << start << std::endl;
            break;
        }
    }
}

谢谢！

Answer 1

我将您的代码更改为“大数字”版本，然后我得到了正确答案 16475640049。

我认为原因在于这句话：

result *= (n--);

'result' 的值会在这里溢出。

'unsigned long long'不足以存储结果。

更新：

既然你知道问题出在哪里，我们可以通过简单地更改代码来解决这个问题，如下所示：

unsigned long long Q114::nCr(unsigned long long n, unsigned long long r) {
    unsigned long long result = 1;
    for(unsigned long long i = 1; i <= r; i++)
    {
        result *= (n--);
        result /= i;  // highlight
    }
    return result;
}

您可以尝试使用此解决方案。