項目歐拉＃14

Question

我目前解決，Project Euler problem 14：

以下迭代序列的組正 整數的定義：

n → n/2 (n is even) 
n → 3n + 1 (n is odd) 

Using the rule above and starting with 13, we generate the following sequence: 
       13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 

Which starting number, under one million, produces the longest chain? 

我設計了以下算法來解決問題：

• 而不是找到系列的ea ch編號，這將包含大量的冗餘計算，我嘗試從1開始向後開發該系列。也就是說，從數字開始並預測它之前的元素。
• 由於可以生成多個系列，因此使用鏈接列表存儲所有系列的最新數量。 （這個想法是隻存儲那些具有更長序列的元素。）
• 我會循環這個，直到找到給定限制下的所有數字;限制下的最後一個數字將具有最長的系列。

這裏是我的代碼：

void series_generate(long num) 
{ 
    long n = 1; 
    addhead(n);    //add 1 to list. 
    while (n < num) 
    { 
      series *p; 
      for (p = head; p != NULL; p = p->next) 
      { 
        long bf = p->num - 1; 
        if (p->num%2 == 0 && bf != 0 && bf%3 == 0) { 
          bf /= 3; 
          if (bf != 1) 
            addhead(bf); 
          if (bf < num) 
            n++; 
        } 
        p->num *= 2; 
        if (p->num < num) 
          n++; 

      }  
    }  
} 

Here is the link to complete code. 不過，我並不如我所料得到答案。 任何人都可以擴展爲什麼這個算法不起作用嗎？

Answer 1

您正在嘗試向後逐級構建Collat​​z樹。因此，在內循環的第k次迭代之後，該列表包含（在沒有發生溢出的情況下）所有需要精確到k步長的數字，以在它們的Collat​​z序列中達到1。

該方法有兩個嚴重問題。

1. 級別的大小呈指數級增長，大小几乎每三個級別翻一番。您沒有足夠的內存來存儲過去不超過100的水平。
2. k中最大的成員是2 ^k。根據num成員的使用類型，您會在31,32,63或64級出現溢出。然後，如果您使用簽名類型，則會出現未定義的行爲，列表中可能爲負數，並且一切都會失靈。如果你使用無符號類型，你的列表包含一個0，並且一切都會失靈。

由於27需要111個步驟才能達到1，所以只要有num > 27就會發生溢出，因此會得到錯誤的結果。