Rilevare cicli nelle simulazioni
Saltare in avanti quando lo stato si ripete
Rilevare cicli nelle simulazioni è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Quando i passi si ripetono
Alcune simulazioni chiedono lo stato dopo un numero enorme di passi, ad esempio mille miliardi. Procedere un passo alla volta non permetterebbe mai di terminare in tempo. ⏳
Gli stati sono finiti
Se il numero di possibili stati è limitato, la simulazione prima o poi dovrà visitarne nuovamente uno. Da quel momento si ripeterà per sempre in un ciclo.
Come appare un ciclo
Il percorso ha una coda iniziale, seguita da un ciclo che si ripete. Individuare il ciclo permette di saltare miliardi di passi.
Ricordi dove è già passato
Memorizzi ogni stato in un dizionario che lo associa al numero del passo in cui è stato visto per la prima volta. Rivederlo rivela il ciclo.
seen = {}Rilevi la ripetizione
Prima di ogni passo, verifichi se lo stato corrente è già presente in seen. Se lo è, ha appena chiuso il ciclo.
if state in seen:
start = seen[state]Misuri la lunghezza del ciclo
La lunghezza è il passo corrente meno il passo in cui questo stato è stato visto per la prima volta. Tanti passi riportano esattamente allo stato iniziale.
length = step - seen[state]Salti avanti usando il modulo
Sottragga la coda, poi calcoli i passi rimanenti modulo la lunghezza del ciclo. A questo punto deve simulare solo un piccolo numero di passi residui.
rem = (N - start) % lengthCompleti i passi rimanenti
Esegua la simulazione solo per quei passi rimanenti a partire dall'inizio del ciclo. Lo stato finale coincide esattamente con quello al passo N.
for _ in range(rem):
state = step_fn(state)Mantenga lo stato hashable
Le chiavi dei dizionari devono essere hashable, quindi trasformi le liste in tuple prima di memorizzarle. Uno stato mutabile non può essere usato come chiave.
key = tuple(row)Floyd senza memoria
Se gli stati sono troppo grandi per essere memorizzati, l'algoritmo del Floyd della tartaruga e della lepre trova un ciclo usando due puntatori e quasi nessuna memoria aggiuntiva.
Perché questo risolve il problema
Il rilevamento dei cicli trasforma un ciclo di mille miliardi di passi, altrimenti impossibile, in poche migliaia di passi. Il trucco consiste interamente nel riconoscere le ripetizioni.
Verifica rapida
Ha visto per la prima volta lo stato corrente al passo s e ora si trova al passo t.
Riepilogo
Quando gli stati si ripetono, memorizzi ciascuno in una mappa, trovi la lunghezza del ciclo, salti avanti usando il modulo e simuli solo i passi rimanenti. 🚀
Domande Frequenti
La lezione «Rilevare cicli nelle simulazioni» è gratuita?
Sì — il testo completo di «Rilevare cicli nelle simulazioni» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Rilevare cicli nelle simulazioni»?
Saltare in avanti quando lo stato si ripete Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Rilevare cicli nelle simulazioni»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Modellare lo stato e procedere per passi
- Percorsi su griglia e vettori di direzione
- Rilevare cicli nelle simulazioni
- Gestire i complessi casi limite