Escalade d’Escaliers en Python : Résolvez cette Question d’Entretien

Introduction

L’escalade d’escaliers est un problème classique en algorithmes, souvent utilisé dans les entretiens techniques pour évaluer les compétences de programmation des développeurs. Ce problème présente des concepts clés tels que la récursion, la programmation dynamique et la manipulation des suites mathématiques. Dans cet article, nous examinerons différentes approches pour résoudre le problème, mettrons en évidence leur efficacité et leur complexité, et fournirons des exemples de code Python.

Comprendre le problème

Le problème de l’escalade d’escaliers peut être défini comme suit : on vous donne un escalier avec un certain nombre de marches, par exemple n marches. À chaque étape, vous pouvez choisir de monter soit 1 marche, soit 2 marches. L’objectif est de déterminer combien de façons distinctes il est possible de grimper jusqu’au sommet.

Scénario typique

Imaginez que vous êtes devant un escalier de n marches :
– Si n = 1, il y a 1 façon de le grimper (une seule marche).
– Si n = 2, il y a 2 façons de le grimper (1+1 ou 2).

La question est de savoir combien de combinaisons sont possibles pour n’importe quel nombre de marches n.

Approches de résolution

Approche 1 : Récursion simple

L’approche la plus intuitive utilise la récursion. Le problème peut être modélisé de manière récursive en définissant que pour atteindre la n-ième marche, vous devez être venu soit de la (n-1)-ième, soit de la (n-2)-ième marche :

def escalade_recursion(n):
    if n <= 1:
        return 1
    return escalade_recursion(n-1) + escalade_recursion(n-2)

# Exemple
print(escalade_recursion(5))  # Sortie : 8

Analyse de complexité

• Temporelle: Cette approche a une complexité temporelle exponentielle, O(2^n), car elle fait de nombreux calculs redondants.
• Spatiale: La complexité spatiale est O(n) en raison de la profondeur de la pile d’appels récursifs.

Approche 2 : Récursion avec Mémorisation

La mémorisation résout le problème de calculs redondants en stockant les résultats intermédiaires pour les réutiliser.

def escalade_memorisation(n, memo=None):
    if memo is None:
        memo = {}

    if n in memo:
        return memo[n]
    if n <= 1:
        return 1

    memo[n] = escalade_memorisation(n-1, memo) + escalade_memorisation(n-2, memo)
    return memo[n]

# Exemple
print(escalade_memorisation(5))  # Sortie : 8

Comparaison avec la récursion simple

• Améliore considérablement la complexité temporelle à O(n).
• La complexité spatiale reste O(n) due au stockage des résultats intermédiaires.

Approche 3 : Programmation dynamique

La programmation dynamique offre une solution itérative, évitant la récursion.

def escalade_dynamique(n):
    if n <= 1:
        return 1

    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1

    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

# Exemple
print(escalade_dynamique(5))  # Sortie : 8

Avantages

• Temporelle: O(n)
• Spatiale: Peut être optimisée à O(1) en utilisant seulement deux variables pour stocker les derniers résultats.

Approche 4 : Formule mathématique (Nombre de Fibonacci)

Ce problème est en fait lié à la séquence de Fibonacci. La n-ième marche peut être résolue en utilisant une formule fermée basée sur les nombres de Fibonacci.

def escalade_fibonacci(n):
    from math import sqrt
    phi = (1 + sqrt(5)) / 2
    psi = (1 - sqrt(5)) / 2
    return int((phi**(n+1) - psi**(n+1)) / sqrt(5))

# Exemple
print(escalade_fibonacci(5))  # Sortie : 8

Efficacité

• Temporelle: O(log n) dû à la puissance
• Spatiale: O(1)

Comparaison des approches

Le choix de l’approche dépend du contexte et des contraintes spécifiques à votre scénario.

Cas d’utilisation et extensions

Ce problème peut être généralisé en autorisant des mouvements de taille variable, comme 1, 2, ou même 3 marches. D’autres contraintes peuvent inclure des marches spécifiques qui ne peuvent pas être utilisées, rendant le problème similaire à des scénarios réels tels que la planification de chemin avec obstacles.

Exercices pratiques

Pour renforcer votre compréhension, essayez les exercices suivants :
– Résoudre le problème pour différentes valeurs de n.
– Adapter les approches pour des mouvements de taille variable, par exemple {1, 3, 5}.
– Considérer des variantes où certaines marches sont cassées et ne peuvent pas être utilisées.

Conclusion

Nous avons exploré diverses méthodes pour résoudre le problème de l’escalade d’escaliers, une question fréquemment posée dans les entretiens techniques. Comprendre ces approches et savoir quand les appliquer est essentiel. Pratiquez régulièrement ces concepts pour améliorer votre habileté à résoudre des problèmes algorithmiques.

Ressources supplémentaires

• Tutoriels Python sur la récursion : Learn Python Recursion
• Cours en ligne sur la programmation dynamique : Dynamic Programming
• Livres recommandés : « Introduction to Algorithms » par Cormen et al.

Appel à l’action

Nous vous invitons à partager vos solutions ou variantes dans la section des commentaires. N’hésitez pas à poser des questions pour des éclaircissements supplémentaires. Explorez, expérimentez et perfectionnez vos compétences algorithmiques !