Getting falsche Antwort auf Projekt euler # 8

Question

Dies könnte wiederholt werden, aber vertrauen Sie mir, ich finde keine befriedigende Antwort. Kann mir bitte jemand sagen, warum bekomme ich falsche Antwort auf dieses Problem: https://projecteuler.net/problem=8. Ich benutzte Brute-Forcing. Mein Code gibt korrekte Antwort für kleine Zahlen. Für 13-stellige gibt es jedoch eine falsche Antwort. Code:

#include <iostream> 
#include<string> 
#include<cmath> 
using namespace std; 

int main() 
{ 
    string str = "73167176531330624919225119674426574742355349194934969835203127745063262395783180169848018694788518438586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"; 
    int len = str.size(); 
    double maxi = 0, product = 1; 
    for(int i = 0; i < len - 13; i ++){ 
     product = (str[i] - '0') * (str[i+1] - '0') * (str[i+2] - '0') * (str[i+3] - '0') * (str[i+4] - '0') * (str[i+5] - '0')* (str[i+6] - '0') * (str[i+7] - '0') * (str[i+8] - '0') * (str[i+9] - '0') * (str[i+10] - '0') * (str[i+11] - '0') * (str[i+12] - '0'); 
     if(maxi < product){ 
      maxi = product; 
     } 
    } 
    cout << maxi; 
    cin.get(); 
    return 0; 
} 

Für das Beispiel haben sie gegeben. Das ist Produkt von 4 aufeinander folgenden Ziffern, bekomme ich richtige Antwort 5832.-Code für das gleiche:

#include <iostream> 
#include<string> 
#include<cmath> 
using namespace std; 

int main() 
{ 
    string str = "73167176531330624919225119674426574742355349194934969835203127745063262395783180169848018694788518438586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"; 
    int len = str.size(); 
    double maxi = 0, product = 1; 
    for(int i = 0; i < len - 13; i ++){ 
     product = (str[i] - '0') * (str[i+1] - '0') * (str[i+2] - '0') * (str[i+3] - '0'); //* (str[i+4] - '0') * (str[i+5] - '0')* (str[i+6] - '0') * (str[i+7] - '0') * (str[i+8] - '0') * (str[i+9] - '0') * (str[i+10] - '0') * (str[i+11] - '0') * (str[i+12] - '0'); 
     if(maxi < product){ 
      maxi = product; 
     } 
    } 
    cout << maxi; 
    cin.get(); 
    return 0; 
} 

Answer 1

Jedes Mal, wenn Sie ein Problem wie dies begegnen, wo Sie die richtigen Ergebnisse für ein Beispiel, aber ein falschen für der große Datensatz, den Sie über Überläufe denken sollten. Ihre product und maxi sind vom Typ double. Ich änderte sie zu long long und erhielt das korrekte Ergebnis. Ich habe auch deinen Code ein wenig aufgeräumt. Hier geht es

#include <iostream> 
#include<string> 
#include<cmath> 
using namespace std; 

int main() 
{ 
    string str = "73167176531330624919225119674426574742355349194934" \ 
       "96983520312774506326239578318016984801869478851843" \ 
       "85861560789112949495459501737958331952853208805511" \ 
       "12540698747158523863050715693290963295227443043557" \ 
       "66896648950445244523161731856403098711121722383113" \ 
       "62229893423380308135336276614282806444486645238749" \ 
       "30358907296290491560440772390713810515859307960866" \ 
       "70172427121883998797908792274921901699720888093776" \ 
       "65727333001053367881220235421809751254540594752243" \ 
       "52584907711670556013604839586446706324415722155397" \ 
       "53697817977846174064955149290862569321978468622482" \ 
       "83972241375657056057490261407972968652414535100474" \ 
       "82166370484403199890008895243450658541227588666881" \ 
       "16427171479924442928230863465674813919123162824586" \ 
       "17866458359124566529476545682848912883142607690042" \ 
       "24219022671055626321111109370544217506941658960408" \ 
       "07198403850962455444362981230987879927244284909188" \ 
       "84580156166097919133875499200524063689912560717606" \ 
       "05886116467109405077541002256983155200055935729725" \ 
       "71636269561882670428252483600823257530420752963450"; 

    const size_t adjacent = 13; 
    size_t len = str.size(); 

    long long max = 0, product = 1; 
    for(size_t i = 0; i+adjacent < len; ++i) { 
     product = 1; 
     for (size_t j = 0; j < adjacent; ++j) 
      product *= str[i+j] - '0'; 
     if (max < product) 
      max = product; 
    } 
    cout << max << endl; 
    return 0; 
} 

Demo

Answer 2

Der wahrscheinlichste Grund ist, dass es ein Integer-Überlauf passiert.
Der maximale Wert des Produkts von 13 Ziffern ist 9^13, und ein double kann das nicht genau unterstützen.

Also, die Lösung ist long long statt double zu verwenden.