主函数无法计算值链中的最大数量

Question

以下程序的函数没有返回正确的值。它将产生不正确的起始数值和不正确的计数值。

countCollatzChain

函数未返回正确的值。该函数正在查找超过 500 个项目链，但输出（请参阅输出会话）是错误的。

该程序的作用是找到函数生成的最长数字链。

using System;
using System.Collections.Generic;
using System.Linq;

class LambdaTest
{
    public const int MAX_NUM = 1000000;
    public const bool debug = false;
    static void Main(string[] args)
    {
        Func<int, int> evenN = x => x / 2;
        Func<int, int> oddN = x => 3 * x + 1;
        Func<int, int> nextN = x => ((x & 1) == 1) ? oddN(x) : evenN(x);
        int maxCnt = 0;
        int maxStart=1;
        var nlist = Enumerable.Range(1, MAX_NUM);
        foreach (int val in nlist)
        {
            int cnt = countCollatzChain(nextN, val);
            if(maxCnt < cnt){
                maxCnt = cnt;
                maxStart = val;
            }
        }
        Console.WriteLine("Start number {0} has max chain of {1} items. ", maxStart, maxCnt);
    }
    
    static int countCollatzChain(Func<int, int> f, int n){
        int count = 0;
        if(n == 1) { return 1; }
        while(n > 1){
            n = f(n);
            count++;
        }
        return count;
    }
}

你能指出哪里出了问题吗？代码显然没有优化，只是尝试以简单的方式解决问题。

起始编号 910107 的最大链数为 475 件。

Answer 1

您的程序的问题在于 countCollatzChain 函数。具体来说，该函数没有正确计算链中的初始数字，从而导致计数不正确。此外，条件 if(n == 1) { return 1; } 不是必需的，可以删除以简化。

这是 countCollatzChain 函数的更正版本：

static int countCollatzChain(Func<int, int> f, int n){
    int count = 1; // Start count at 1 to include the initial number
    while(n > 1){
        n = f(n);
        count++;
    }
    return count;
}

通过将计数初始化为 1，可以确保初始数字包含在计数中。这将为您提供正确的链条长度。

此外，您可能需要考虑通过使用记忆来存储先前计算的链长度来优化您的程序，这可以显着减少大数的计算时间。以下是如何实现记忆化的示例：

static Dictionary<int, int> memo = new Dictionary<int, int>();

static int countCollatzChain(Func<int, int> f, int n){
    if (memo.ContainsKey(n)) return memo[n];
    
    int original = n;
    int count = 1;
    while (n > 1){
        n = f(n);
        if (memo.ContainsKey(n)){
            count += memo[n];
            break;
        }
        count++;
    }
    memo[original] = count;
    return count;
}

通过这种方式，您可以存储已经计算出的数字的链长度，当这些数字再次出现在其他链中时可以重复使用。

尝试这些更改，看看是否可以解决链长度不正确的问题。如果您需要进一步的帮助，请告诉我！