What is wrong with my Catalan Number logic?
I wanted to write a code for Catalan Numbers.Catalan Numbers are defined as follows:
C(n) = 2n C n/(n+1)
. But instead of computing (2n C n)
I wanted to calculate the catalan numbers bottom up using the following facts:
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!
---------------开发者_Go百科---------------- =
(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)
Now utilizing the above fact this is my following code:
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)
}
Now,my question is why does the above function return 12 when my input is 4 .It should return 14 because c(4)=14.
Can anyone help me, please?
Even though the original expression for C(n)
might be wrong, the actual recurrence
is correct.
You can further simplify that to
But that gives you C(n+1)
in terms of C(n)
. What you want is C(n)
in terms of C(n-1)
. Plug in n-1
to get
Also note that in order to prevent the integer division from truncating your result, you need to multiply first and then divide.
int catalan(int n) {
if (n == 1)
return 1;
else
return 2 * (2*n - 1) * catalan(n-1) / (n+1);
}
EDIT: if the values of the
need to be used frequently and not just calculated once, it's probably a good idea to use memoization, to avoid calculating them more than once.Additionally, notice that due to the large growth rate, the Catalan numbers quickly overflow any of the predefined integer data types C
has.
According to http://en.wikipedia.org/wiki/Catalan_number the recurrence formula is:
C(n+1)=2(2n+1)/(n+1) * C(n)
or C(n)=2(2(n-1)+1)/n * C(n-1)
I think you have forgotten this transformation from C(n+1)
to C(n)
.
There is an error in your formula. Your formula is for calculating c(n+1) yet your input is n. This can be fixed by decreasing the value of n by one before using it in the calculation:
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)
}
Edit: As pointed out by abeln, the code above will fail due to integer division dropping the remainder. Use the code below instead:
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)))
}
When you go from the mathematical expression to code, you are implicitly replacing n with n-1 in the Catalan() parts, but not in the expression itself. So you are computing the multiplier for value N and multiplying it by C(N-1). Try substituting N-1 for N in your equation, which leads to:
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)
}
In your formula, you have
(2n)!
C(n) = ----------------
(n+1)! * n! * n!
when in fact the Catalan Numbers are defined as
(2n)!
C(n) = ----------------
(n+1)! * n!
i.e. you have one factorial on the denominator too much
精彩评论