How to resolve the algorithm Catalan numbers step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

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) for n > 0 and catalan3(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 to 15 and prints the Catalan number calculated using each method for each iteration.

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