1

カタラン数のコードを書きたかったのです。カタラン数は次のように定義されています。

C(n) = 2n C n/(n+1)。しかし、計算する代わりに(2n C n)、次の事実を使用してカタラン数をボトムアップで計算したかったのです。

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を返すのはなぜですか。c（4）= 14であるため、14を返す必要があります。

誰か助けてもらえますか？

4

5 に答える 5

9

の元の表現は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てください。

于 2011-04-19T14:38:36.207 に答える
4

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)。

于 2011-04-19T14:06:45.693 に答える
3

数式からコードに移行すると、Catalan() 部分で n を暗黙的に n-1 に置き換えますが、式自体では置き換えません。したがって、値 N の乗数を計算し、それを C(N-1) で乗算しています。式の N を N-1 に置き換えてみると、次のようになります。

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)
}
于 2011-04-19T14:23:40.323 に答える
3

数式にエラーがあります。あなたの式は c(n+1) を計算するためのものですが、入力は n です。これは、計算で使用する前に n の値を 1 減らすことで修正できます。

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)))
}
于 2011-04-19T14:35:41.687 に答える
0

あなたの式では、

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

実際、カタロニア語の数字は次のように定義されています

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

つまり、分母に階乗が 1 つ多すぎます。

于 2011-04-19T14:10:37.260 に答える