c# - 双线性序列给出奇怪的结果

Question

我正在努力使我的表演技巧(不存在)达到标准，但在将公式写入代码时遇到了问题。这是我要尝试的公式 - 引用取消引用 - “转换”为代码。

Consider a sequence u where u is defined as follows:

The number u(0) = 1 is the first one in u. For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in u too. There are no other numbers in u. Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on...

这就是我目前所拥有的:

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        Console.WriteLine(DblLinear(10));
        //Expected result: 22
        Console.WriteLine(DblLinear(20));
        //Expected result: 57
        Console.WriteLine(DblLinear(30));
        //Expected result: 91
        Console.WriteLine(DblLinear(50));
        //Expected result: 175
    }
    public static int DblLinear (int n) 
    {
        List<int> linArr = new List<int>();
        linArr.Add(1);

        int i = 0;
        while(linArr.Count < n)
        {
            linArr.Add((2 * linArr[i]) + 1);
            linArr.Add((3 * linArr[i]) + 1);
            linArr.Sort();
            i++;
        }
        return linArr[n - 1];
    }
}

在达到 27 之前计算都是正确的。在那之后它就乱七八糟了，我不知道它做错了什么。

Answer 1

您从序列中取出一项并产生两项。所以你真的需要一些数据结构来存储它们，因为它们的数量会增加。堆将是最好的。如果您想直接使用 .net 中的内容，可以使用 SortedSet。

public static IEnumerable<int> DblLinear2()
{
    SortedSet<int> seq = new SortedSet<int> { 1 };

    while (true)
    {
        int min = seq.First();
        seq.Remove(min);
        yield return min;
        seq.Add(min * 2 + 1);
        seq.Add(min * 3 + 1);
    }
}

结果:

1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, 28, 31, 39, 40, 43, 45, 46, 55, 57, 58, 63, 64, 67, 79, 81, 82, 85, 87...