C中的Terras猜想＃

Question

我在生成Terras號碼序列時遇到問題。

這裏是我的失敗嘗試：

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

namespace Terras 
{ 
    class Program 
    { 
     public static int Terras(int n) 
     { 
      if (n <= 1) 
      { 
       int return_value = 1; 
       Console.WriteLine("Terras generated : " + return_value); 

       return return_value; 
      } 
      else 
      { 
       if ((n % 2) == 0) 
       { 
        // Even number 
        int return_value = 1/2 * Terras(n - 1); 
        Console.WriteLine("Terras generated : " + return_value); 

        return return_value; 
       } 
       else 
       { 
        // Odd number 
        int return_value = 1/2 * (3 * Terras(n - 1) + 1); 
        Console.WriteLine("Terras generated : " + return_value); 

        return return_value; 
       } 
      } 
     } 
     static void Main(string[] args) 
     { 
      Console.WriteLine("TERRAS1"); 
      Terras(1); // should generate 1 

      Console.WriteLine("TERRAS2"); 
      Terras(2); // should generate 2 1 ... instead of 1 and 0 

      Console.WriteLine("TERRAS5"); 
      Terras(5); // should generate 5,8,4,2,1 not 1 0 0 0 0 

      Console.Read(); 
     } 
    } 
} 

我在做什麼錯？

我知道遞歸的基礎知識，但我不明白爲什麼這不起作用。

我注意到序列的第一個數字實際上是你傳入的數字，後面的數字是零。

Answer 1

變化1/2 * Terros(n - 1);到Terros(n - 1)/2;

而且1/2 * (3 * Terros(n - 1) + 1);到(3 * Terros(n - 1) + 1)/2;

1/2 * ...簡直是0 * ...與int數學。

---

[編輯]

遞歸是錯和式是誤引導。簡單迭代

public static void Terros(int n) { 
    Console.Write("Terros generated :"); 
    int t = n; 
    Console.Write(" " + t); 
    while (t > 1) { 
    int t_previous = t; 
    if (t_previous%2 == 0) { 
     t = t_previous/2; 
    } 
    else { 
     t = (3*t_previous+1)/2; 
    } 
    Console.Write(", " + t); 
    } 
    Console.WriteLine(""); 
} 

「n是偶數」應該是「t（下標n-1）是偶數」 - 對於「n是奇數」是相同的。

Answer 2

int return_value = 1/2 * Terros(n - 1); 
    int return_value = 1/2 * (3 * Terros(n - 1) + 1); 

不幸的是，您已經遇到了人們使用整數犯的常見錯誤。

（INT）1 /（INT）2將始終爲0

Answer 3

由於1/2是整數divison它總是;爲了糾正數學，只需 交換條款：不是1/2*n但n/ 2;而不是1/2* (3 * n + 1)把(3 * n + 1)/2。

另一個問題：不要把計算（Terros）和輸出（Console.WriteLine）在 相同的功能

public static String TerrosSequence(int n) { 
    StringBuilder Sb = new StringBuilder(); 

    // Again: dynamic programming is far better here than recursion 
    while (n > 1) { 
    if (Sb.Length > 0) 
     Sb.Append(","); 

    Sb.Append(n); 

    n = (n % 2 == 0) ? n/2 : (3 * n + 1)/2; 
    } 

    if (Sb.Length > 0) 
    Sb.Append(","); 

    Sb.Append(n); 

    return Sb.ToString(); 
} 


// Output: "Terros generated : 5,8,4,2,1" 
Console.WriteLine("Terros generated : " + TerrosSequence(5)); 

Answer 4

現有的答案引導你在正確的方向，但目前還沒有最終的一個。我認爲總結和增加細節可以幫助你和未來的訪問者。

問題名稱

這個問題的原始的名字是「Terros的關頭」。首先，它是conjecture，其次，對原始Collat​​z序列的修改來自Riho Terras *（不是Terros！）誰證明了Terras Theorem說，幾乎所有t 0認爲∃n∈ℕ：tₙ< t 0。您可以在MathWorld和chux’s question on Math.SE上閱讀更多信息。

*當搜尋誰是R. TERRAS上MathWorld提到，我發現不僅record on Geni.com，而且還創紀錄的可能作者，他的侄女阿斯特麗德TERRAS和her family’s genealogy。只爲真正好奇的人。 ☺

公式

你得到的公式錯在你的問題。由於不同的t 0的序列表顯示，您應該測試t 012- 1而不是n的parity。從MathWorld採取

公式。

而且第二個表列標題是錯誤的，它應該讀T·，T1，T2，...爲T·上市了。

您重蹈覆轍與測試ň，而不是在你的代碼tₙ₋₁了。如果您的程序的輸出被精確地指定（例如，當由自動裁判員檢查時），請再想一想您是否應該輸出t0或不。

整數VS浮點運算

使得與兩個整數的操作時，你會得到一個整數。如果涉及浮點數，則結果爲浮點數。在你的條件的兩個分支，則計算該形式的表達式：

1/2 * … 

1和2是整數，因此該除法是整數除法。整數除法總是舍入，所以表達式實際上是

0 * … 

這是（幾乎*）總是零。謎團已揭開。但如何解決它？

而不是乘以一半，你可以除以二。在偶數分支中，除以2除以餘數。在奇數分支中，tₙ1是奇數，所以3·tₙₙ1也是奇數。奇+ 1是偶數，因此除以2總是在兩個分支中產生等於零的餘數。整數劃分就足夠了，結果是精確的。

此外，您可以使用浮動分區，只需將1替換爲1.0即可。但是這可能不會給出正確的結果。你看，序列的所有成員都是整數，並且你得到浮點結果！所以與Math.Round()四捨五入並轉換爲整數？那......如果可以的話，總是使用花車逃避。對於他們來說，很少有用例，我想大多數情況下與圖形或數值算法有關。大多數時候你並不需要他們，他們只是介紹round-off errors。

*零時間也可能產生NaN，但讓我們忽略來自特殊浮點值的「無論」的可能性。我只是迂腐。

遞歸解決方案

從上面提到的問題

除此之外，你的整個遞歸方法是有缺陷的。顯然你打算Terras(n)是tₙ。這並不是非常糟糕。但是你忘記了你提供了t 0並且搜索n而不是其他方式。

要解決你的方法，你需要建立一個「全球性」變量int t0將被設置爲所給T·和Terras(0)返回。然後Terras(n)真的會返回tₙ。但是當序列停止時，您仍然不知道n的值。您只能重複越來越大的n，破壞時間複雜性。

等等。如何緩存中間Terras()調用ArrayList<int> t的調用結果？ t[i]將包含Terras(i)的結果，如果未初始化，則爲零。在Terras()的頂部，您將添加if (n < t.Count() && t[n] != 0) return t[n];以便在緩存時立即返回值並且不重複計算。否則，計算是真的讓，只是在返回前，結果被緩存：

if (n < t.Count()) { 
    t[n] = return_value; 
} else { 
    for (int i = t.Count(); i < n; i++) { 
     t.Add(0); 
    } 
    t.Add(return_value); 
} 

還是不夠好。節省了時間複雜度，但增加了空間複雜性。嘗試跟蹤（最好手動，鉛筆&紙）的計算爲t0 = 3; t.Add(t0);。你事先不知道最後的n，所以你必須從1上去，直到Terras(n)返回1.

注意到任何東西？首先，每次增加n並進行新的Terras()調用時，都需要在高速緩存末尾添加計算值（t）。其次，你總是隻看一個項目。你從下往上計算整個序列，你不需要那麼大的笨蛋ArrayList但始終只是它的最後一項！

迭代求解

OK，讓我們忘了複雜的遞歸解決方案試圖遵循自上而下的定義，並移動到從原方案的逐步完善彈出的自下而上的方法。遞歸不再需要，它只是混亂整個事情，並放慢速度。

序列結束仍通過遞增Ñ和計算tₙ，暫停時tₙ= 1找到。變量t商店tₙ,t_previous商店以前的tₙ（現在tₙ0.01）。其餘的應該是顯而易見的。

public static void Terras(int t) { 
    Console.Write("Terras generated:"); 
    Console.Write(" " + t); 
    while (t > 1) { 
     int t_previous = t; 
     if (t_previous % 2 == 0) { 
      t = t_previous/2; 
     } else { 
      t = (3 * t_previous + 1)/2; 
     } 
     Console.Write(", " + t); 
    } 
    Console.WriteLine(""); 
} 

從chux的答案中取得的變量名稱，只是爲了可比性。

這可以被認爲是原始實例dynamic-programming技術。這種解決方案的演變對於所有這類問題都是常見的。緩慢的遞歸，調用結果緩存，動態的「自下而上」的方法。當你對動態編程更有經驗時，即使在更復雜的問題中也可以直接看到它，甚至不用考慮遞歸。