Pourquoi ce programme qui trouve le plus petit numéro de triangle avec> 500 facteurs tombe-t-il en panne?

Question

J'ai écrit le programme ci-dessous pour résoudre Project Euler 12, qui consiste à trouver le plus petit nombre de triangle avec plus de 500 facteurs.

Je ne pense pas qu'il y ait des erreurs majeures. Je soupçonne que l'optimisation de la mémoire peut être un problème. Cela étant dit, cependant, j'ai besoin du long long non signé pour le grand nombre de triangles qui sera finalement la réponse. Je commence ma séquence de nombres naturels à triangleNumbers [0] = 10,000,000,000. Je sais que 9 000 000 000 ont environ 300 facteurs, donc 10 000 000 000 était une «meilleure estimation». Ceci étant dit, je suppose que 10.000.000.000 est le "premier nombre naturel" et continue d'ajouter les nombres naturels suivants pour obtenir le "second" nombre naturel et au-delà (donc triangleNumbers [1] = 10,000,000,000 + 2, triangleNumbers [2] = 10,000,000,000 +3, et ainsi de suite).

Des suggestions et des conseils seraient appréciés. Merci d'aider un débutant à s'améliorer.

#include <iostream> 
#include <vector> 
#include <math.h> 

using namespace std; 

bool keepRunning=true; 

unsigned long long int naturalNumberCount=0; 
unsigned long long int j=4; 
unsigned long long int sum=0; 

vector <unsigned long long int> triangleNumbers(0); 

unsigned long long int totalFactors=0; 
unsigned long long int trialDivisors=1; 

unsigned long long int storer=0; 

int main() 
{ 
    triangleNumbers[0]=10000000000; 
    triangleNumbers[1]=10000000002; 
    triangleNumbers[2]=10000000005; 
    triangleNumbers[3]=10000000009; 
    triangleNumbers[4]=10000000014; 
    //listed first few prime numbers above. j is set at 4 for this reason 

    naturalNumberCount=5; 
    //10000000014 is the 5th triangle number, and 5 is the 5th natural num 
    //need this for recursive relation 
    //5th triangle number = 4th triangle num + 5 (num + naturalNumberCount 

    while(keepRunning) 
    { 
     for(trialDivisors;trialDivisors<=(unsigned long long int)(sqrt(triangleNumbers[j]));trialDivisors++) 
     { 
      if(triangleNumbers[j]%trialDivisors==0) 
      { 
       totalFactors++; 
       if(totalFactors>499)//499 because the number itself will be a divisor of itself, so no need to check 
       { 
        keepRunning=false; 
        break; 
       } 
       else 
       { 
        keepRunning=true; 
       } 
      } 
      else 
      { 
       keepRunning=true; 
      } 
     } 
     //need the below to generate and store the next triangle number (as next element of array) 

     naturalNumberCount++;//for recursive relation 
     storer=triangleNumbers[j];//store the (j+1)'th triangle number, since we are changing j itself 
     j++;//raise j, we gonna add the next value 
     triangleNumbers[j]=(storer+naturalNumberCount);//the new value (last triangle number + current natural) 
     totalFactors=0;//reset total factors to preclude any carry-over 
    } 


    cout<<triangleNumbers[j]<<flush; 

    return 0; 
} 

Answer 1

TL;DR

#include <vector> 

std::vector <unsigned long long int> triangleNumbers(0); 

int main() 
{ 
    triangleNumbers[0]=10000000000; 
} 

Vous avez un vecteur vide, et la toute première ligne dans main conduit à un comportement non défini puisque vous essayez d'accéder à l'article 0 (il n'y a pas de point).

Live Example using operator [ ]

Live Example showing what vector::at() does

Notez le deuxième lien montre que vous accédez à un élément hors des limites à l'aide at() au lieu de [ ] pour accéder au premier élément.

Pour ajouter des éléments à un std::vector, utilisez l'une des méthodes conçues pour ce faire, à savoir vector::push_back(), vector::insert(), vector::emplace_back(), vector::resize(), ou la construction de la std::vector avec le nombre requis d'entrées.

Le moyen le plus sur toutes ces options serait de construire le vecteur en utilisant la liste initialiseur:

std::vector<unsigned long long int> triangleNumbers = {10000000000, 10000000002, 10000000005, 10000000009, 10000000014};

std::vector reference

Une fois que vous correctement configuré le vecteur, alors vous devez regarder pour le reste de votre code, pour voir où vous pouvez accéder à un index hors-limites. Jetez un oeil à j dans votre boucle, et comment vous l'utilisez comme index. La fonction vector::at() vous dira immédiatement si j est hors limites.

---

EDIT: Si vous vouliez vraiment une syntaxe qui simuler un tableau « déplié automatiquement », le plus proche vous pouvez venir à cela serait d'utiliser un std::unordered_map<int, unsigned long long> comme on le voit par this example.

Il est possible que la solution map soit une solution de remplacement - vous devrez la tester.