雙線性序列給出奇數結果

Question

我試圖讓我的表演技巧（不存在）達到標準，但遇到了將公式寫入代碼的問題。這是我正在嘗試的公式 - 引用未引用 - 「轉換」爲代碼。

考慮其中u被定義爲序列u如下：

數u(0) = 1是u第一個。 對於u中的每個x，則y = 2 * x + 1和z = 3 * x + 1也必須在u中。 u中沒有其他的數字。 例如：u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

1給3和4，然後3給7和10，4給9和13，然後7給15和22等等......

而這就是我目前爲止：

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 ...

Answer 2

問題在於您使用單個索引來構建您的值。

當您根據您的示例得到i == 27時，第一個系列產生55，第二個系列產生82。但第一個應該也產生了57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81之前第二個產生82爲您的序列正確計算。

您需要運行兩個單獨的索引，並且每個索引只在各個系列產生的值最低（或等於另一個）時遞增。

這是我會怎麼做：

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