JavaScript实现指定递推M序列 奇偶参数分支区分问题

需求说明 #

需要编码实现按如下规则定义的序列：

M(0) = 1,
M(1) = 1, 
M(2) = 2, 
M(2t) = M(t) + M(t + 1) + t (for t > 1), 
M(2t + 1) = M(t - 1) + M(t) + 1 (for t >= 1)

现有问题 #

已编写的代码运行结果错误，核心问题是不知道如何在代码逻辑中区分2t（偶数参数）和2t+1（奇数参数）两种递推场景，原有错误代码如下：

function seq(num)
{
    var num1=1;
    var num2=1;var num3=2
    var sum1;var sum2;
    var i=0;                                                             
    if (num>=1){                                                            
      for (i = 0; i < num; i++) {                           
        sum2=num1+num2+1;
        num1=num2;
        num2=sum2; } }                                                          
    if (num>1){
        for (i = 0; i < num; i++)
        {
        sum1=num1+num2+num;
        num1=num2;
        num2=sum1;
       }}
    return num2;
}

document.write("seq(1): "+seq(1)+"<br>");

解决方法 #

区分奇偶参数直接用取模运算%即可：

• 当计算的下标i满足i % 2 === 0时，为偶数场景，此时i = 2t，可算出t = i / 2，代入偶数递推公式计算
• 当计算的下标i满足i % 2 === 1时，为奇数场景，此时i = 2t + 1，可算出t = (i - 1) / 2，代入奇数递推公式计算

原有代码的问题是没有针对每个下标做奇偶判断和t值映射，而是用两个独立循环直接累加，完全不符合递推式的下标规则，因此结果错误。推荐用动态规划数组存储已计算的序列值，从最小下标开始递推到目标值，避免重复计算，正确实现代码如下：

function seq(n) {
    // 处理边界已知值
    if (n === 0 || n === 1) return 1;
    if (n === 2) return 2;
    // 数组存储已计算的M值，避免重复计算
    const dp = new Array(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    // 从3开始逐位计算到目标n
    for (let i = 3; i <= n; i++) {
        if (i % 2 === 0) {
            // 偶数场景：i=2t
            const t = i / 2;
            dp[i] = dp[t] + dp[t + 1] + t;
        } else {
            // 奇数场景：i=2t+1
            const t = (i - 1) / 2;
            dp[i] = dp[t - 1] + dp[t] + 1;
        }
    }
    return dp[n];
}

// 测试用例
document.write("seq(0): "+seq(0)+"<br>"); // 输出1
document.write("seq(1): "+seq(1)+"<br>"); // 输出1
document.write("seq(2): "+seq(2)+"<br>"); // 输出2
document.write("seq(3): "+seq(3)+"<br>"); // 输出3
document.write("seq(4): "+seq(4)+"<br>"); // 输出7
document.write("seq(5): "+seq(5)+"<br>"); // 输出4

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