Le problème de l'escalier

Cette semaine, c'est Loïc qui vous propose un #KataOfTheWeek : Le problème de l'escalier

Briefing du Kata : J’ai devant moi un escalier qui comporte N marches. En montant, je peux à chaque fois décider entre :

• Monter une marche
• Monter deux marches

Soit P le nombre de possibilités de gravir cet escalier.

Implémenter la fonction computeOptions(int N) dans le langage de votre choix (ou en pseudo code) qui permet de retourner P en fonction de N.
Discuter de la solution retenue et de ses limites si limite il y a.

Saurez-vous résoudre le problème ?

Bon courage !

Et voici une solution proposée par l'auteur :

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;
}

Votre équipe TakiVeille