Syklusdeteksjon i simuleringer
Hopp fremover når tilstanden gjentar seg
Syklusdeteksjon i simuleringer er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Når stegene gjentar seg
Noen simuleringer ber Dem finne tilstanden etter et enormt antall steg, for eksempel én billion. Det ville aldri blitt ferdig i tide å ta ett steg om gangen. ⏳
Tilstandene er endelige
Hvis antallet mulige tilstander er begrenset, må simuleringen før eller siden besøke en tilstand på nytt. Derfra gjentar den seg for alltid i en syklus.
Slik ser en syklus ut
Banen har en hale som leder inn i en løkke som gjentas. Når De finner løkken, kan De hoppe forbi milliarder av steg.
Husk hvor De har vært
Lagre hver tilstand i en ordbok som knytter den til stegnumeret da De så den første gang. Når De ser den igjen, har De funnet syklusen.
seen = {}Finn gjentakelsen
Før hvert steg må De kontrollere om den nåværende tilstanden allerede finnes i seen. Hvis den gjør det, har De nettopp lukket løkken.
if state in seen:
start = seen[state]Mål sykluslengden
Lengden er det nåværende steget minus steget da De så denne tilstanden første gang. Så mange steg tar det før tilstanden kommer tilbake.
length = step - seen[state]Hopp fremover med modulo
Trekk fra halen, og ta deretter de resterende stegene modulo sykluslengden. Nå trenger De bare å simulere en liten rest.
rem = (N - start) % lengthUtfør de resterende stegene
Kjør simuleringen i bare de gjenværende stegene fra starten av syklusen. Den endelige tilstanden samsvarer nøyaktig med tilstanden ved steg N.
for _ in range(rem):
state = step_fn(state)Hold tilstanden hashbar
Nøkler i en ordbok må være hashbare, så gjør om lister til tupler før De lagrer dem. En muterbar tilstand kan ikke brukes som nøkkel.
key = tuple(row)Floyd's uten minne
Hvis tilstandene er for store til å lagre, finner Floyd's skilpadde og hare en syklus ved hjelp av to pekere og nesten ikke noe ekstra minne.
Hvorfor dette redder dagen
Syklusdeteksjon gjør en umulig løkke på én billion steg om til noen få tusen steg. Hele trikset er å gjenkjenne gjentakelser.
Rask kontroll
De så den nåværende tilstanden første gang ved steg s, og nå er De ved steg t.
Oppsummering
Når tilstander gjentar seg, lagrer De hver av dem i en ordbok, finner sykluslengden, hopper fremover med modulo og simulerer bare de resterende stegene. 🚀
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Syklusdeteksjon i simuleringer» gratis?
Ja – hele teksten i «Syklusdeteksjon i simuleringer» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Syklusdeteksjon i simuleringer»?
Hopp fremover når tilstanden gjentar seg Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «Syklusdeteksjon i simuleringer»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Modeller tilstand og gå fremover
- Rutenettbevegelser og retningsvektorer
- Syklusdeteksjon i simuleringer
- Få kontroll på vanskelige spesialtilfeller