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

Un bon moyen de commencer est toujours de calculer les premiers termes de la suite.

  • N = 1 ==> P = 1
  • N = 2 ==> P = 2 (une et une, ou deux marches)
  • N = 3 ==> P = 3 (une et deux, deux et une, une et une et une)
  • N = 4 ==> P = 5
  • N = 5 ==> P = 8

Instinctivement on peut reconnaitre un pattern (ça ressemble à Fibonacci: F(n+2) = F(n+1) + F(n)), ou continuer de calculer les termes suivants pour le trouver.

Dès qu'on l'a, il ne faut pas chercher à aller plonger dans ses souvenirs de maths, on peut faire une simple récursion (fonction computeOptionsRecursive). Attention, si elle a l'avantage d'être simple, elle peut aussi générer un StackOverflow si le nombre est trop grand.

On peut donc aussi faire une version itérative, qui, elle, ne génère pas de stack overflow (fonction computeOptionsIterative :)

int computeOptionsRecursive(int n) {
  if (n > 2) {
    return computeOptionsRecursive(n-1) + computeOptionsRecursive(n-2);
  }
  // N is either 2, 1 or <= 0
  switch (n) {
    case 1:
      return 1;
    case 2:
      return 2;
    default:
      throw new IllegalArgumentException("N cannot be <= 0");
  }
}

int computeOptionsIterative(int n) {
  if (n <= 0) {
      throw new IllegalArgumentException("N cannot be <= 0");
  }
  // prev1 <=> F(N-1)
  // prev2 <=> F(N-2)
  // f <=> Fibonacci
  int prev2 = 1, f = 0, prev1 = 0;
  for (int k = 1; k <= n; ++k) {

    f = prev2 + prev1; // update F(N) = F(N-1) + F(N-2)
    prev2 = prev1;
    prev1 = f;
  }
  return f;
}

A bientôt pour un nouveau #KataOfTheWeek !