项目欧拉#8,我不明白我哪里出错了

Question

我正在研究项目euler问题的第八个问题,其中我提供了这个非常大的数字:

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 7163626956188267042825248360082 3257530420752963450

我应该"找到1000位数字中具有最大产品的十三个相邻数字." 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

事实上,你的解决方案太小而不是太大.答案是注释中指出的,存在整数溢出,并且线索是您的解决方案接近签名int的最大可能值:2147483647.您需要使用不同的类型来存储产品.

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

以前的答案

您正在检查内部循环内部而不是外部的新最佳产品.这意味着您的最大值包括所有小于或等于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;
    }
}

Answer 2

9 ^13≈2.54e12(最大可能值,需要42位精确表示),不适合signed int.你应该使用int64.