时间戳

首页 > 解决方案 > Project Euler #8 答案太大以获得有效答案

c++ - Project Euler #8 答案太大以获得有效答案

问题描述

我查看了这里的结果，试图看看我的错误在哪里。我不是在寻找解决方案的答案，而是在寻找关于我忽略了什么导致错误答案的提示。话虽如此，让我们进入它。

我正在处理 Project Euler 问题，目前排在第 8 位。我相信这个问题应该测试您对迭代和存储大数的知识。我试图将值存储为 unsigned int、long long int 和字符串，但所有这些都给了我不同的错误答案。正如我之前提到的，我想知道是否有人能指出我是否忽略了正确的方向，或者可能没有进行足够彻底的研究。

我的代码：

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;
int main()
{
   vector<int> numberList = "I broke the number provided into individual one digit integers";
   string sum;
   string answer;

for(auto it = numberList.begin(); it != numberList.end(); it++)
    {
        auto it2 = next(it, 1);
        auto it3 = next(it2, 1);
        auto it4 = next(it3, 1);
        auto it5 = next(it4, 1);
        auto it6 = next(it5, 1);
        auto it7 = next(it6, 1);
        auto it8 = next(it7, 1);
        auto it9 = next(it8, 1);
        auto it10 = next(it9, 1);
        auto it11 = next(it10, 1);
        auto it12 = next(it11, 1);
        auto it13 = next(it12, 1);

        if(it12 == numberList.end())
        {
            break;
        }

        sum = to_string(*it * *it2 * *it3 * *it4 * *it5 * *it6 * *it7 * *it8 * *it9 * *it10 * *it11 * *it12 * *it13);

        if(sum.compare(answer) > 0)
        {
            answer = sum;
        }
    }
    cout << answer << endl;
}

我对这个解决方案的攻击计划是在每个循环上更新 13 个迭代器，我会使用这些值来倍增并找到解决方案。我发现的问题是结果数字对于导致溢出的 int 来说太大了。然后我尝试了 long long 和 unsigned 都导致了错误的答案。这个版本的解决方案我试图将它存储在一个字符串中，这也导致了错误的答案。重要的是要注意，我试图在线性时间内保持这个解决方案。谢谢您的帮助。

标签： c++iterationlargenumber

解决方案

在标准架构（其中long long64 位长）上，您不需要 astd::string来解决这个问题，因为您要乘以 13 位数字，因此结果将始终小于10^13，这很容易适合long long( 2^63 ~ 10^19)。

您的代码的问题是您正在使用 执行乘法int，因此您在转换之前溢出：

sum = to_string(*it * *it2 * *it3 * *it4 * *it5 * *it6 * *it7 * *it8 * *it9 * *it10 * *it11 * *it12 * *it13);

这里*it, *it2, ..., 是 的迭代器int，因此您在int域中得到一个在转换之前溢出的产品to_string。

您应该使用 astd::vector<long long>来存储数字或将第一个数字转换为 a long long：

sum = (long long) *it * *it2 * *it3 * *it4 * *it5 * *it6 * *it7 * *it8 * *it9 * *it10 * *it11 * *it12 * *it13;

和sum/answer可以简单地是long long。

推荐阅读