我的加泰羅尼亞號碼邏輯有什麼問題？

Question

我想寫Catalan數 .Catalan數字被定義如下代碼：

C(n) = 2n C n/(n+1)。但是，而不是計算(2n C n)我想計算Catalan數自下而上使用以下事實：

Catalan(n) =  
2n! /n! * n! * (n+1) 

Catalan(n+1) = 
2*(n+1) 
--------------------------- =  
(n+1)! * (n+1)! * ((n+1)+1) 

(2n+2) * (2n+1) * 2n!  
------------------------------- = 
(n+1) * n! * (n+1) * n! * (n+2)  

(2n+2) * (2n+1) * 2n!  
----------------------------------- =  
(n+1) * (n+2) * n! * n! * (n+1)  

(2n+2) * (2n+1)  
--------------- * Catalan(n)  
(n+1) * (n+2) 

現在利用上述事實，這是我下面的代碼：

int catalan(int n) 
{ 
    if (n == 1) 
     return 1 //since c(1)=1 is my base case 
    else 
     return (((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan(n-1) 
} 

現在，我的問題是，爲什麼當我的輸入是4時，上述函數返回12，它應該返回14，因爲c（4）= 14。

任何人都可以幫助我嗎？

Answer 1

您的公式中存在錯誤。你的公式是用於計算c（n + 1），但你的輸入是n。這可以是固定的通過減小n的值由一個在計算中使用它之前：

int catalan(int n) 
{ 
    if (n == 1) 
     return 1 //since c(1)=1 is my base case 
    else 
     n=n-1 
     return (((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan(n) 
} 

編輯：正如abeln指出的那樣，上面的代碼將失敗由於整數除法丟棄其餘部分。使用下面的代碼來代替：

int catalan(int n) 
{ 
    if (n == 1) 
     return 1 //since c(1)=1 is my base case 
    else 
     n=n-1 
     return ((catalan(n) * (2*n+2) * (2*n+1))/((n+1)*(n+2))) 
} 

Answer 2

根據http://en.wikipedia.org/wiki/Catalan_number遞推公式是：

C(n+1)=2(2n+1)/(n+1) * C(n)或C(n)=2(2(n-1)+1)/n * C(n-1)

我想你已經忘記了從C(n+1)這一轉變過程中C(n)。

Answer 3

在您的公式，你有

  (2n)! 
C(n) = ---------------- 
     (n+1)! * n! * n! 

的時候，其實加泰羅尼亞號碼被定義爲

  (2n)! 
C(n) = ---------------- 
     (n+1)! * n! 

即你有一個階乘的分母太大

Answer 4

當你去從數學表達式到代碼，您都隱式地用加泰羅尼亞語（）中的n-1替換n，但不是在表達式本身中。所以你正在計算N的乘數並乘以C（N-1）。嘗試在您的公式中用N-1代替N，導致：

int catalan(int n) 
{ 
    if (n == 1) 
     return 1 //since c(1)=1 is my base case 
    else 
     return (((2*n) * (2*n-1))/((n)*(n+1))) * catalan(n-1) 
} 

Answer 5

即使原始表達式爲C(n)可能是錯誤的，實際復發

是正確。

您可以進一步簡化，以

但是，讓你在C(n+1)的C(n)條款。你想要的是C(n)根據C(n-1)。插上n-1得到

還要注意的是，爲了防止整數除法從截斷你的結果，你需要先乘，然後分。

int catalan(int n) { 
    if (n == 1) 
    return 1; 
    else 
    return 2 * (2*n - 1) * catalan(n-1)/(n+1); 
} 

編輯：如果需要頻繁使用，而不僅僅是計算一次的的值，它可能使用memoization，避免計算它們不止一次一個好主意。

此外，請注意，由於增長率較高，加泰羅尼亞語數字會快速溢出C中的任何預定義整數數據類型。