Project Euler # 8 Ответ - большой, чтобы получить правильный ответ - PullRequest
Новая
       19

Project Euler # 8 Ответ - большой, чтобы получить правильный ответ

0 голосов
/ 26 февраля 2020

Я просмотрел результаты здесь, чтобы попытаться увидеть, где моя ошибка. Я не ищу ответ на решение, а скорее намек на то, что я упустил, чтобы привести к неправильному ответу. Как говорится, давайте вникнем.

Я работаю над вопросами Project Euler, и в настоящее время я занимаюсь номером 8. Этот вопрос, я считаю, должен проверить вас на ваши знания итерации и хранения больших чисел. Я пытался сохранить значение как беззнаковое 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 итераторов, которые обновляются на каждом l oop, и я использовал бы эти значения для умножения и поиска решения. Проблема, которую я обнаружил, заключалась в том, что результирующее число слишком большое для целого числа, приводящего к переполнению. Затем я попытался долго и без знака, что привело к неправильному ответу. В этой версии решения я попытался сохранить ее в строке, что также привело к неправильному ответу. Важно отметить, что я пытаюсь сохранить это решение в линейном времени. Спасибо за помощь.

1 Ответ

4 голосов
/ 26 февраля 2020

В стандартной архитектуре (где long long длиной 64 бита) вам не нужно std::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.

Вы должны использовать std::vector<long long> для хранения цифр или преобразования первой цифры в long long: 

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

И sum / answer может быть просто long long.

...