How to resolve the algorithm Catalan numbers step by step in the C programming language
How to resolve the algorithm Catalan numbers step by step in the C programming language
Table of Contents
Problem Statement
Catalan numbers are a sequence of numbers which can be defined directly: Or recursively: Or alternatively (also recursive):
Implement at least one of these algorithms and print out the first 15 Catalan numbers with each. Memoization is not required, but may be worth the effort when using the second method above.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Catalan numbers step by step in the C programming language
The provided C program calculates Catalan numbers using three different methods:
-
Binomial Formula:
catalan1(n) = binomial(2 * n, n) / (1 + n)
-
Recursive Summation:
catalan2(n) = sum(catalan2(i) * catalan2(n - 1 - i)) for i in range(0, n)
-
Explicit Recursion:
catalan3(n) = 2 * (2 * n - 1) * catalan3(n - 1) / (1 + n)
forn > 0
andcatalan3(0) = 1
The main
function tests these methods by printing the first 16 Catalan numbers using each method.
Here's a breakdown of the program:
-
The
binomial
function uses an iterative algorithm to calculate binomial coefficients efficiently. -
The
catalan1
function calculates Catalan numbers using the binomial formula. -
The
catalan2
function calculates Catalan numbers using recursive summation. -
The
catalan3
function calculates Catalan numbers using explicit recursion. -
In the
main
function:- It iterates from
0
to15
and prints the Catalan number calculated using each method for each iteration.
- It iterates from
Catalan numbers have applications in various mathematical and computer science areas, including:
- Counting binary trees, Dyck paths, and triangulations.
- Analyzing the time complexity of certain algorithms.
- Modeling random walks and queues.
Source code in the c programming language
#include <stdio.h>
typedef unsigned long long ull;
ull binomial(ull m, ull n)
{
ull r = 1, d = m - n;
if (d > n) { n = d; d = m - n; }
while (m > n) {
r *= m--;
while (d > 1 && ! (r%d) ) r /= d--;
}
return r;
}
ull catalan1(int n) {
return binomial(2 * n, n) / (1 + n);
}
ull catalan2(int n) {
int i;
ull r = !n;
for (i = 0; i < n; i++)
r += catalan2(i) * catalan2(n - 1 - i);
return r;
}
ull catalan3(int n)
{
return n ? 2 * (2 * n - 1) * catalan3(n - 1) / (1 + n) : 1;
}
int main(void)
{
int i;
puts("\tdirect\tsumming\tfrac");
for (i = 0; i < 16; i++) {
printf("%d\t%llu\t%llu\t%llu\n", i,
catalan1(i), catalan2(i), catalan3(i));
}
return 0;
}
You may also check:How to resolve the algorithm Arrays step by step in the Nanoquery programming language
You may also check:How to resolve the algorithm Ramer-Douglas-Peucker line simplification step by step in the Yabasic programming language
You may also check:How to resolve the algorithm Boolean values step by step in the 11l programming language
You may also check:How to resolve the algorithm Phrase reversals step by step in the PL/I programming language
You may also check:How to resolve the algorithm Sorting algorithms/Cocktail sort step by step in the Slate programming language