CATALAN NUMBERS IN C++ LANGUAGE
AMRUHA AHMED
28th November,2023.
Catalan Numbers are the sequence of numbers that are calculated using the formula:
(2n)!/(n+1)!n!
Where n=0,1,2,3….
Catalan Numbers prove to be extremely useful in calculating the number of binary search trees that can be made using 'n' nodes.
FUNCTIONS REQUIRED:
- fact(): a recursive function to return the factorial of the parameter passed
- main(): invokes fact() at appropriate intervals to calculate the desired number of catalan numbers
VARIABLES REQUIRED IN FACT FUNCTION:
- n : passed as a parameter
VARIABLES REQUIRED IN THE MAIN FUNCTION:
- ctr: stores the count of numbers to be generated
- term1: stores the value of (2n)!
- term2: stores the value of (n+1)!
- term3: stores the value of n!
- finalterm: gives final term=catalan number at i'th position
ALGORITHM FOR MAIN FUNCTION:
- 1.Start
- 2.Accept the count of catalan numbers to be generated and store in ctr
- 3. For i =0 till i is less than ctr, the steps from 4 to 8 need to be repeated otherwise go to step 9
- 4. Invoke fact() and pass 2*i as a parameter.Store the result in term1
- 5.Invoke fact() and pass i+1 as a parameter. Store the result in term2
- 6. Invoke fact() and pass i as a parameter. Store the result in term3
- 7. Calculate term1/(term2+term3) and store the resultant in finalterm
- 8. Display finalterm
- 9.Stop
PROGRAM:
#include<iostream>
using namespace std;
int fact(int n)//recursive function to calculate factorial of 'n'
{
if(n==0)
return 1;
else
return(n*fact(n-1));
}
int main()
{
int ctr;//stores the count of numbers to be generated
cout<<"\n Enter the count of catalan numbers to be generated:";
cin>>ctr;
cout<<"\n The first "<<ctr<<" Catalan Numbers are...\n";
for(int i=0;i<ctr;i++)
{
int term1=fact(2*i);//stores the value of (2n)!
int term2=fact(i+1);//stores the value of (n+1)!
int term3=fact(i);//stores the value of n!
int finalterm=(int)term1/(term2*term3);//gives final term=catalan number at i'th position
cout<<finalterm<<" ";
}
}
DRY RUN:
If ctr=5 then the following will be the values of i, term1, term2, term3 and finalterm:
OUTPUT:
Enter the count of catalan numbers to be generated: 5
The first 5 Catalan Numbers are...
1 1 2 5 14