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 !