C#技术咨询：如何寻找百万以内最长Collatz序列并排序

原代码存在的核心问题 #

• 破坏循环遍历逻辑：直接修改for循环的迭代变量i，导致遍历顺序完全混乱，会重复处理或跳过大量数值。必须用临时变量生成当前起始值的序列，不能改动i。
• 列表创建位置错误：每次进入while循环都新建列表，导致之前的序列元素全部丢失，每个起始值的列表应在while循环外初始化。
• 条件判断逻辑错误：两个独立的if会让一次循环内执行两次计算（比如偶数除以2得到奇数后，会立刻执行奇数的运算），违反Collatz序列规则，需改用if-else结构。
• 内存浪费严重：存储所有完整序列会占用极大内存，实际上我们只需要记录每个起始值的序列长度即可。
• 无性能优化：暴力计算会重复处理大量子序列（比如多数值都会走到4→2→1），缺乏记忆化缓存会导致效率极低。

基础修正版（可运行但效率一般） #

这个版本修复了逻辑错误，仅记录序列长度，避免内存浪费：

int maxLength = 0;
int startingNumber = 0;

// 遍历所有小于100万的起始值
for (int i = 2; i < 1000000; i++)
{
    long current = i; // 用long避免中间值溢出int范围
    int length = 1; // 起始值本身算序列第一个元素

    // 生成当前起始值的Collatz序列
    while (current != 1)
    {
        if (current % 2 == 0)
        {
            current /= 2;
        }
        else
        {
            current = current * 3 + 1;
        }
        length++;
    }

    // 更新最长序列记录
    if (length > maxLength)
    {
        maxLength = length;
        startingNumber = i;
    }
}

Console.WriteLine($"最长序列的起始值：{startingNumber}，序列长度：{maxLength}");

高效记忆化版本（推荐） #

通过缓存已计算的序列长度，避免重复计算子序列，大幅提升处理100万级数据的效率：

int targetMax = 1000000;
// 缓存数组：索引对应数值，值为该数值的Collatz序列长度
int[] sequenceLengthCache = new int[targetMax + 1];
sequenceLengthCache[1] = 1; // 已知1的序列长度为1

int maxLength = 0;
int startingNumber = 0;

for (int i = 2; i < targetMax; i++)
{
    long current = i;
    int tempLength = 0;

    // 当current未被缓存且大于等于当前起始值i时，继续计算
    while (current != 1 && current >= i)
    {
        if (current % 2 == 0)
        {
            current /= 2;
        }
        else
        {
            current = current * 3 + 1;
        }
        tempLength++;
    }

    // 缓存当前起始值的序列长度：临时步数 + 已缓存的后续序列长度
    sequenceLengthCache[i] = tempLength + sequenceLengthCache[current];

    // 更新最长序列记录
    if (sequenceLengthCache[i] > maxLength)
    {
        maxLength = sequenceLengthCache[i];
        startingNumber = i;
    }
}

Console.WriteLine($"最长序列的起始值：{startingNumber}，序列长度：{maxLength}");

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