爲什麼這個程序能找到500多個因子最小的三角形數字？

Question

我已經編寫了下面的程序來解決Project Euler 12，它涉及到找到超過500個因子的最小三角形數。

我不認爲有重大錯誤。我懷疑內存優化可能是一個問題。然而，這就是說，我需要無符號long long int來表示大三角形數字，最終會成爲答案。我開始我的自然數序列triangleNumbers [0] = 10,000,000,000。我知道90億有大約300個因素，所以100億是「最好的猜測」。 這就是說，然而，我假設10,000,000,000是「第一自然數」，並繼續添加隨後的自然數以獲得「第二」自然數並超出（所以triangleNumbers [1] = 10,000,000,000 + 2，triangleNumbers [2] = 10,000,000,000 +3等等）。

任何建議和提示，將不勝感激。感謝您幫助初學者改進。

#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; 
} 

你有一個空的載體，因爲你正在試圖訪問項目0在main的第一行會導致不確定的行爲（有沒有這樣的項目）。

Live Example using operator [ ]

Live Example showing what vector::at() does

注二等鏈接表明，您是通過使用at()代替[ ]訪問的第一個項目訪問越界的元素。

要將項目添加到std::vector，使用的設計要做到這一點，即vector::push_back()，vector::insert()，vector::emplace_back()，vector::resize()，或構建std::vector的條目必要數量的方法之一。

最簡單了所有這些選項將是使用初始化列表來構建其載體：

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

std::vector reference

一旦你正確設置載體，那麼你需要看看在你的代碼的其餘部分，看看你可能在哪裏訪問一個越界索引。特別是在循環中查看j，以及如何將它用作索引。如果j超出範圍，vector::at()函數將立即告訴您。

---

編輯：如果你真的想要一個語法，將模擬「自動擴展」陣列，就可以得出這樣的最接近的是使用一個std::unordered_map<int, unsigned long long>通過this example所見。

可能map解決方案將是一個直接替代 - 你將不得不測試它。