項目歐拉問題12 - C + +

我正在處理問題12關於第一個三角形數字與500除數。我試圖強制解決方案。我在35秒內得到300個除數，在10分鐘內無法獲得400個除數。我將改變我的解決方案以使用主因子方法，但我現在已經看到，人們仍然在一分鐘之內以強力的方式獲得這個解決方案。項目歐拉問題12 - C + +

您可以批評我的代碼，並告訴我是否錯過了使這種可怕的低效率的東西？

unsigned long long TriangleNumberDivisors(int divisorTarget) 
{ 
    unsigned long long triangleNum=1; 
     unsigned long long currentNum=2; 
    int numOfDivisors=0; 


    numOfDivisors=NumOfDivisors(triangleNum); 
    while(numOfDivisors<divisorTarget) 
    { 
     triangleNum+=currentNum; 
     currentNum++; 
     numOfDivisors=NumOfDivisors(triangleNum); 
    } 

    return triangleNum; 
} 

int NumOfDivisors(unsigned long long dividend) 
{ 
    int numDivisors=0; 
    set<unsigned long long> divisors; 
    set<unsigned long long>::iterator it; 

    for(unsigned long long index=1; index<=dividend/2; index++) 
    { 
     if(dividend%index==0) 
     { 
      divisors.insert(index); 
      numDivisors++; 
      it=divisors.find(dividend/index); 
      if(it==divisors.end()) 
      { 
       divisors.insert(dividend/index); 
       numDivisors++; 
      } 
       /*for some reason not checking for dups above and 
just checking for how many items are in the set at the end is slower 
      for(it=divisors.begin();it!=divisors.end();it++) 
      { 
        numDivisors++; 
      } 
        */ 
     } 
    } 

    return numDivisors; 
} 

int main() 
{ 
    cout<<TriangleNumberDivisors(500)<<endl; 

    return 0; 
}

更新：明白了，謝謝。改爲只檢查數字的平方根，並進行了額外的檢查，看看它是否是一個完美的正方形。這讓我也完全刪除了這個集合。在12秒內跑出500個因子。

來源

2010-09-27 ChurchSkiz

請在'='，'<'，'=='周圍放置空格。 otherwiseitisverydifficulttoread。 – Arun 2010-09-27 22:00:05

請閱讀我對同一個問題的回答：http://stackoverflow.com/questions/3273379/understanding-some-math-relating-to-euler-12/3273405#3273405 :) – AraK 2010-09-27 22:02:06

您目前檢查除數達到dividend/2。你可以減少到sqrt(dividend)，這是漸近地快。如果dividend是正方形，則可能需要特殊情況。

爲問題12我的C++代碼（其基本上不與你的相同，但使用此下限，也只是計數除數而不是將它們存儲在該組）取約1秒

來源

2010-09-27 21:54:44

我不明白爲什麼檢查除數到sqrt（股息）將工作。例如，28的因數是1,2,4,7,14,28。 sqrt（28）是5.如果你在5停止檢查，你怎麼能找到7和14？ – 2013-01-09 10:27:43

@Jérôme除數成對出現（當你找到除數2時，你也隱式地找到除數14;當你找到4時，你隱含地找到7）。因此，您可以計算每個除數小於平方根的兩個除數。 – 2013-01-09 12:07:14

for(unsigned long long index=1; index<=dividend/2; index++)

我看到您試圖通過將您的循環限制爲dividend/2來優化此操作，而不是一直迭代到dividend。限制你自己sqrt(dividend)會更好（從你檢查更少的除數）。

另外，如果您通過股息的平方根限制自己，則不必檢查重複的除數。這隻會發生平方數，所以只需檢查index == dividend/index，以避免重複插入。

來源

2010-09-27 21:56:10 Tim

略有改進：不是測試'index == dividend/index'，而是測試'index * index == dividend'是否更快，因爲乘法通常比除法更快。 – LarsH 2010-09-30 02:19:38

我假設你的意思是代替sqrt（股息）。如果我們計算循環的每次迭代的平方根，那將會起作用。但是，理想情況下，只需計算一次sqrt，然後保存它，然後檢查'index <= saved_sqrt'，它只是比較兩個數字。不需要爲每次迭代重新計算'sqrt'，因爲它不會改變（但是index的平方在每次迭代中都會改變）。 – Tim 2010-09-30 02:31:05

我不確定爲什麼你需要divisors，set類型變量，在NumOfDivisors方法。爲什麼要計算numDivisors（索引高達sqrt(dividend)）是不夠的？（set是作爲一個平衡二叉搜索樹實現的，它會減慢該方法。）。此外，你似乎調用divisors.insert(..)兩次。

來源

2010-09-27 21:58:19 Arun

似乎你可以獲得一些性能，如果你緩存了特定數量的因數，你去了。

來源

2010-09-27 22:01:04 John

項目歐拉問題12 - C + +

回答

相關問題