如何用C#高效检测Collatz猜想中的无限循环问题

运行100万次Collatz猜想计算时，有432个数字疑似陷入无限循环，无法判断是仍在计算还是特殊情况。之前为每个数字添加计时器导致程序速度减慢3-4倍，以下是更高效的优化方案，实现单个数字处理超时后询问用户是否继续或跳过的功能：

优化后的代码 #

using System;
using System.Collections.Generic;

int amount = 1000000;
int verifiedCount = 0;
// 缓存已验证能到达1的数字，避免重复计算
HashSet<long> verifiedNumbers = new HashSet<long> { 1, 2, 4 };
// 单个数字的超时阈值：3分钟（单位：毫秒）
int timeoutMs = 3 * 60 * 1000;

for (int i = 1; i <= amount; i++)
{
    long current = i;
    bool isVerified = false;
    DateTime startTime = DateTime.Now;
    int stepCount = 0;

    while (current > 1)
    {
        // 若当前数字已被验证过，直接终止计算
        if (verifiedNumbers.Contains(current))
        {
            isVerified = true;
            break;
        }

        // 每1000步检查一次超时，减少性能损耗
        if (stepCount % 1000 == 0)
        {
            TimeSpan elapsed = DateTime.Now - startTime;
            if (elapsed.TotalMilliseconds > timeoutMs)
            {
                Console.Write($"数字 {i} 处理已超时，是否继续？(Y/N): ");
                var key = Console.ReadKey();
                Console.WriteLine();
                if (key.Key == ConsoleKey.N)
                {
                    Console.WriteLine($"已跳过数字 {i}");
                    break;
                }
                // 重置计时，继续计算
                startTime = DateTime.Now;
            }
        }

        // Collatz核心计算逻辑
        current = current % 2 == 0 ? current / 2 : current * 3 + 1;
        stepCount++;
    }

    // 标记已验证并更新缓存
    if (isVerified || current == 1 || current == 2 || current == 4)
    {
        verifiedCount++;
        verifiedNumbers.Add(i);
    }
}

Console.WriteLine($"{verifiedCount} of {amount} numbers were verified.");

关键优化点 #

• 避免数值溢出：将原代码的int替换为long，大数字计算时不会溢出导致错误循环，这可能是你遇到“疑似无限循环”的原因之一
• 缓存复用结果：用HashSet存储已验证的数字，后续遇到相同数字直接终止计算，大幅减少重复运算
• 低开销超时检测：每处理1000步才检查一次时间，避免频繁调用时间函数导致的性能下降，比单独为每个数字开计时器高效得多
• 交互式超时处理：超时后询问用户选择，灵活处理疑似循环的数字，无需等待不确定的计算时间

内容的提问来源于stack exchange，提问作者user19519009