Détection de Cycle (Floyd)
Algorithme du lièvre et de la tortue
Enonce
Implémenter la détection de cycle dans une liste chaînée avec l'algorithme de Floyd. Retourner True si un cycle existe.
⚠ Bonus : Trouver le nœud d'entrée du cycle.
Signature attendue
def detecter_cycle(tete) -> bool:Exemples
detecter_cycle(Maillon(1, Maillon(2, Maillon(3))))→Falsen = Maillon(1) ; n.suivant = n ; detecter_cycle(n)→True
📖 Rappel de cours
L'algorithme de Floyd utilise deux pointeurs : un lent (tortue, +1) et un rapide (lièvre, +2). S'il y a un cycle, ils se rencontreront.
Principe :
Si la liste a un cycle de longueur $\lambda$ commençant à la distance $\mu$ de la tête :
$\text{Rencontre après au plus } \mu + \lambda \text{ pas}$
Espace $O(1)$ — pas besoin d'ensemble de nœuds visités.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Algorithme glouton : rendu de monnaie
- Sac à dos (Programmation Dynamique)
- Plus Longue Sous-séquence Commune (LCS)
- Arbres Binaires — Parcours et Hauteur
- Arbre Binaire de Recherche (ABR)
- Tri par Tas (Heap Sort)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.