排序规则序列-减去错误

本文关键字：错误 规则 排序 | 更新日期: 2023-09-27 17:59:14

以下迭代序列是为正整数集定义的：

n→n/2（n为偶数）

n→3n+1（n为奇数）

使用上面的规则并从13开始，我们生成以下序列：

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

可以看出，这个序列（从13开始，到1结束）包含10个术语。虽然它还没有被证明（Collatz问题），但人们认为所有的起始数字都以1结束。

哪个起始数字，低于一百万，产生最长的链？

这是我解决手头问题的办法。

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++之后，只是为了检查我的代码是否正确运行。它会正确运行，但在某个时刻，它开始运行负数。我不确定我的代码哪里出了问题。

排序规则序列-减去错误

这是一个整数溢出。如果您使用更大的类型（如Long），它应该可以正常工作。

在解决问题（跟踪序列）时，您将遇到数字

56991483520

它大于int.MaxValue，因此您将有溢出；我建议序列成员使用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
相关文章：