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

Question

我正在努力使我的表演技巧（none 达到标准），但运行遇到了将公式写入代码的问题。这是我正在尝试的公式 - 引用取消引用 - "convert" 编码。

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

问题在于您使用单一索引来构建您的值。

当您到达 i == 27 时，根据您的示例，第一个系列生成 55，第二个生成 82。但是第一个也应该在第二个产生 82 之前产生 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81 以便正确计算你的序列。

您需要运行两个单独的索引，并且仅在各自系列产生的值最低（或等于另一个）时才增加每个索引。

我会这样做：

public static IEnumerable<int> DblLinear()
{
    Func<int, int> fxy = x => 2 * x + 1;
    Func<int, int> fxz = x => 3 * x + 1;

    var intermediate = new System.Collections.Generic.SortedSet<int>();

    Action<int> safeAdd = x =>
    {
        if (!intermediate.Contains(x))
        {
            intermediate.Add(x);
        }
    };

    safeAdd(1);

    while (true)
    {
        var x = intermediate.First();
        safeAdd(fxy(x));
        safeAdd(fxz(x));
        intermediate.Remove(x);
        yield return x;
    }
}

现在可以使用它来生成整个序列，因此最好使用 LINQ .Take(...) 运算符。

你可以这样使用它：

Console.WriteLine(String.Join(", ", DblLinear().Take(20)));

...这给了我：

1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, 28, 31, 39, 40, 43, 45, 46, 55

您的测试代码一旦被修改以处理列表，就可以正常工作了：

    Console.WriteLine(DblLinear().Skip(10).First());
    //Expected result: 22
    Console.WriteLine(DblLinear().Skip(20).First());
    //Expected result: 57
    Console.WriteLine(DblLinear().Skip(30).First());
    //Expected result: 91
    Console.WriteLine(DblLinear().Skip(50).First());
    //Expected result: 175

Answer 2

你从序列中取出一个项目并产生两个。所以你真的需要一些数据结构来存储它们，因为它们的数量会增加。堆将是最好的。如果您想直接使用我们在 .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...

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

Double linear sequence gives odd results

c#

performance

formula

sequence