Un petit souvenir des séminaires avec les nombres de Catalan - Solution

On se retrouve aujourd'hui pour la solution du précédent #KataOfTheWeek proposé par Alexandre en début de semaine !

Voici un exemple d'implémentation en Java:

import java.math.BigInteger;

public class Katalan {

    private static BigInteger C0 = BigInteger.ONE;

    public static void main(String... args) {
        BigInteger cn;
        long n = 15, startTime, elapsedTime;
        System.out.println("KATA-LAN -  n = " + n);

        //CAS RÉCURSIF
        startTime = System.nanoTime();
        cn = catalanRecursive(n);
        elapsedTime = System.nanoTime() - startTime;
        System.out.println("CAS RÉCURSIF: Cn = " + cn + " (" + elapsedTime / 1000 + "ms)");

        //CAS RÉCURSIF BIS
        startTime = System.nanoTime();
        cn = catalanRecursiveBis(n);
        elapsedTime = System.nanoTime() - startTime;
        System.out.println("CAS RÉCURSIF BIS: Cn = " + cn + " (" + elapsedTime / 1000 + "ms)");

        //CAS ANALYTIQUE
        startTime = System.nanoTime();
        cn = catalanAnalytic(n);
        elapsedTime = System.nanoTime() - startTime;
        System.out.println("CAS ANALYTIQUE: Cn = " + cn + " (" + elapsedTime / 1000 + "ms)");
    }

    public static BigInteger catalanRecursive(long n) {
        if (n == 0) return C0;
        BigInteger sum = BigInteger.ZERO;
        for (long i = 0; i < n; i++) {
            sum = sum.add(catalan_recursive(i).multiply(catalanRecursive(n - 1 - i)));
        }
        return sum;
    }

    public static BigInteger catalanRecursiveBis(long n) {
        if (n == 0) return C0;
        return BigInteger.valueOf(2 * (2 * n - 1))
                .multiply(catalanRecursiveBis(n - 1))
                .divide(BigInteger.valueOf(n + 1));
    }

    public static BigInteger catalanAnalytic(long n) {
        return factorial(2 * n).divide(factorial(n + 1).multiply(factorial(n)));
    }

    private static BigInteger factorial(long n) {
        if (n <= 1 ) return BigInteger.ONE;
        return BigInteger.valueOf(n).multiply(factorial(n - 1));
    }
}

A bientôt pour un nouveau #KataOfTheWeek !