在Collat​​z序列弊錯誤

Question

以下迭代序列是爲正整數的集合來定義：

Ñ→N/2（n爲偶數）

Ñ→3N + 1（n爲奇數）

使用上述規則，並用13開始，我們產生以下序列：

13→40→20→10→5→16→8→4→2→1

它可以看出，這個序列（從13開始並在1結束）包含10個術語。儘管尚未證明（Collat​​z問題），但可以認爲所有起始數字都是1.

哪一個起始數字低於100萬，會產生最長的鏈？

這是我解決手頭問題的方法。

static void Main(string[] args) 
{ 
    int possCounter = 0; 
    int largestChain = 0; 
    int largestChainNum = 0; 
    int chainNum = 0; 
    for (int i = 2; i <= 999999; i++) 
    { 
     chainNum = i; 
     possCounter = 1; 
     while (chainNum != 1) 
     { 
      if (chainNum % 2 == 0) 
      { 
       chainNum = chainNum/2; 
      } 
      else 
      { 
       chainNum = (3 * chainNum) + 1; 
      } 
      possCounter++; 
      Console.WriteLine(chainNum); 
     } 
     if (possCounter > largestChain) 
     { 
      largestChainNum = i; 
      largestChain = possCounter; 
     } 
    } 
    Console.WriteLine(largestChainNum); 
    Console.ReadLine(); 
} 

我把Console.WriteLine(chainNum)possCounter++之後只是爲了檢查，如果我的代碼是正確運行。它會正確運行，但是，在某個點它開始運行負數。我不確定我的代碼出錯了。

Answer 1

這是一個整數溢出。如果你使用更大的類型（比如Long），它應該可以正常工作。

Answer 2

當解決問題（跟蹤序列）你會碰到比int.MaxValue更大數目

56991483520 

，因此你將有一個溢出;我建議使用long作爲序列成員。一個優化技巧更多的是通過序列項系列更新：跟蹤關注

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 

你知道40，20和16長度和有沒有必要來計算這些數字再次

private static Dictionary<long, int> s_Counts = new Dictionary<long, int>() { 
    {1, 1}, 
}; 

private static void AppendCounts(long n) { 
    List<long> list = new List<long>(); 

    for (; !s_Counts.ContainsKey(n); n = n % 2 == 0 ? n/2 : 3 * n + 1) 
    list.Add(n); 

    int count = s_Counts[n]; 

    for (int i = list.Count - 1; i >= 0; --i) 
    s_Counts.Add(list[i], count + list.Count - i); 
} 

... 

for (int i = 1; i < 1000000; ++i) 
    AppendCounts(i); 

KeyValuePair<long, int> max = new KeyValuePair<long, int>(0, 0); 

foreach (var pair in s_Counts) 
    if (pair.Value > max.Value) 
    max = pair; 

Console("{0} generates {1} values", max.Key, max.Value); 

結果是

837799 generates 525 values