Détection de cycles dans les simulations
Avancer rapidement lorsque l’état se répète
Détection de cycles dans les simulations est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Quand les étapes se répètent
Certaines simulations demandent l’état après un nombre énorme d’étapes, par exemple mille milliards. Avancer une étape à la fois ne finirait jamais à temps. ⏳
Les états sont en nombre fini
Si le nombre d’états possibles est limité, la simulation devra forcément repasser par l’un d’eux. À partir de là, elle se répète indéfiniment selon un cycle.
À quoi ressemble un cycle
Le parcours possède une partie initiale qui mène à une boucle, puis cette boucle se répète. Repérer la boucle permet d’ignorer des milliards d’étapes.
Souvenez-vous de vos passages précédents
Stockez chaque état dans un dictionnaire qui l’associe au numéro de l’étape où vous l’avez vu pour la première fois. Le revoir révèle le cycle.
seen = {}Détectez la répétition
Avant chaque étape, vérifiez si l’état actuel se trouve déjà parmi les états vus. Si c’est le cas, vous venez de fermer la boucle.
if state in seen:
start = seen[state]Mesurez la longueur du cycle
La longueur correspond à l’étape actuelle moins l’étape où vous avez vu cet état pour la première fois. Ce nombre d’étapes ramène exactement à cet état.
length = step - seen[state]Avancez rapidement avec le modulo
Soustrayez la partie initiale, puis prenez les étapes restantes modulo la longueur du cycle. Vous n’avez plus qu’un tout petit nombre d’étapes à simuler.
rem = (N - start) % lengthTerminez les étapes restantes
Exécutez la simulation uniquement pendant ces étapes restantes à partir du début du cycle. L’état final correspond exactement à l’étape N.
for _ in range(rem):
state = step_fn(state)Conservez un état hachable
Les clés d’un dictionnaire doivent être hachables : transformez donc les listes en n-uplets avant de les stocker. Un état mutable ne peut pas servir de clé.
key = tuple(row)Floyd sans mémoire
Si les états sont trop volumineux pour être stockés, l’algorithme de Floyd, avec sa tortue et son lièvre, trouve un cycle à l’aide de deux pointeurs et de presque aucune mémoire supplémentaire.
Pourquoi cela vous sauve la mise
La détection de cycle transforme une boucle de mille milliards d’étapes impossible en quelques milliers d’étapes. Reconnaître les répétitions est toute l’astuce.
Vérification rapide
Vous avez vu l’état actuel pour la première fois à l’étape s et vous êtes maintenant à l’étape t.
Récapitulatif
Lorsque les états se répètent, enregistrez chacun dans une table de correspondance, trouvez la longueur du cycle, avancez rapidement avec le modulo et simulez uniquement les étapes restantes. 🚀
Questions Fréquemment Posées
La leçon « Détection de cycles dans les simulations » est-elle gratuite ?
Oui — le texte complet de « Détection de cycles dans les simulations » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Détection de cycles dans les simulations » ?
Avancer rapidement lorsque l’état se répète Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Détection de cycles dans les simulations » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Modéliser l’état et avancer étape par étape
- Parcours de grille et vecteurs de direction
- Détection de cycles dans les simulations
- Maîtriser les cas limites délicats