c++ - Project Euler #8，我不明白我哪里出错了

Question

我正在开发 euler problem number eight 项目，我在其中得到了这么多可笑的数字:

7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420 752963450

并且应该“在 1000 位数字中找到具有最大乘积的 13 个相邻数字。” EG 前四个相邻数字的乘积是 7 * 3 * 1 * 6。我的代码如下:

int main()
{
    string num = /* ridiculously large number omitted */;
    int greatestProduct = 0;
    int product;
    for (int i=0; i < num.length() -12; i++)
    {
        product = ((int) num[i] - 48);
        for (int j=i+1; j<i+13; j++)
        {
            product = product * ((int) num[j] - 48);
            if (greatestProduct <= product)
            {
                greatestProduct = product;
            }
        }
    }
    cout << greatestProduct << endl;
}

我不断收到 2091059712，因为项目 euler 告诉我的答案是错误的，我怀疑它太大了。任何帮助将不胜感激。

编辑:更改为 unsigned long int 并且有效。谢谢大家!

Answer 1

事实上，您的解决方案太小而不是太大。答案是评论中指出的，存在整数溢出，线索在于您的解决方案接近有符号整数的最大可能值:2147483647。您需要使用不同的类型来存储产品。

请注意，下面的答案仍然是“正确的”，因为您的代码确实做错了，但这不是导致错误值的原因。尝试将您的(工作)代码发送到 http://codereview.stackexchange.com如果您希望那里的人告诉您在您的方法和编码风格方面可以改进的地方。

上一个答案

您正在内部循环内部而不是外部检查新的最佳产品。这意味着您的最大值包括小于或等于 ton 13 位的所有字符串，而不仅仅是 13 位。

如果您找到的字符串少于 13 位且乘积很大，但两端均为 0，这可能会有所不同。您不应该将其视为最大的，但您的代码确实如此。 (我还没有检查这是否真的发生。)

for (int i=0; i < num.length() -12; i++)
{
    product = ((int) num[i] - 48);
    for (int j=i+1; j<i+13; j++)
    {
        product = product * ((int) num[j] - 48);
    }
    if (greatestProduct <= product)
    {
        greatestProduct = product;
    }
}