Wykrywanie cykli w symulacjach
Pomijanie kroków naprzód, gdy stan się powtarza
Wykrywanie cykli w symulacjach to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Gdy kroki się powtarzają
Niektóre symulacje wymagają znalezienia stanu po ogromnej liczbie kroków, na przykład bilionie. Wykonywanie ich pojedynczo nigdy nie zakończyłoby się na czas. ⏳
Liczba stanów jest skończona
Jeśli liczba możliwych stanów jest ograniczona, symulacja musi w końcu odwiedzić któryś z nich ponownie. Od tego momentu będzie się bez końca powtarzać w cyklu.
Jak wygląda cykl
Ścieżka ma ogon prowadzący do cyklu, a następnie pętlę, która się powtarza. Wykrycie pętli pozwala przeskoczyć miliardy kroków.
Pamiętaj, gdzie już byłeś
Przechowuj każdy stan w słowniku, przypisując mu numer kroku, w którym pojawił się po raz pierwszy. Ponowne znalezienie tego stanu ujawnia cykl.
seen = {}Wykryj powtórzenie
Przed każdym krokiem sprawdź, czy bieżący stan znajduje się już w seen. Jeśli tak, właśnie zamknąłeś pętlę.
if state in seen:
start = seen[state]Zmierz długość cyklu
Długość to bieżący numer kroku pomniejszony o numer kroku, w którym po raz pierwszy zobaczyłeś ten stan. Tyle kroków wystarczy, aby stan powrócił do tej samej wartości.
length = step - seen[state]Przeskocz dalej za pomocą modulo
Odejmij długość ogona, a następnie oblicz pozostałą liczbę kroków modulo długości cyklu. Teraz trzeba zasymulować tylko niewielką pozostałą część.
rem = (N - start) % lengthWykonaj pozostałe kroki
Uruchom symulację tylko na te pozostałe kroki, zaczynając od początku cyklu. Stan końcowy będzie dokładnie taki sam jak po kroku N.
for _ in range(rem):
state = step_fn(state)Zachowaj możliwość haszowania stanu
Klucze słownika muszą być haszowalne, dlatego przed zapisaniem zamień listy na krotki. Zmienny stan nie może być kluczem.
key = tuple(row)Algorytm Floyda bez pamięci
Jeśli stany są zbyt duże, aby je przechowywać, algorytm Floyda żółwia i zająca znajduje cykl za pomocą dwóch wskaźników i niemal bez dodatkowej pamięci.
Dlaczego to ratuje sytuację
Wykrywanie cyklu zamienia niemożliwą pętlę biliona kroków w kilka tysięcy kroków. Cały trik polega na rozpoznaniu powtórzeń.
Szybkie sprawdzenie
Po raz pierwszy zobaczył(a) Pan/Pani bieżący stan w kroku s, a teraz znajduje się w kroku t.
Podsumowanie
Gdy stany się powtarzają, zapisuj każdy z nich w mapie, znajdź długość cyklu, przeskocz dalej za pomocą modulo i zasymuluj tylko pozostałe kroki. 🚀
Często zadawane pytania
Czy lekcja „Wykrywanie cykli w symulacjach” jest bezpłatna?
Tak — pełny tekst „Wykrywanie cykli w symulacjach” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Wykrywanie cykli w symulacjach”?
Pomijanie kroków naprzód, gdy stan się powtarza Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Wykrywanie cykli w symulacjach”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Modelowanie stanu i przechodzenie dalej
- Przejścia po siatce i wektory kierunku
- Wykrywanie cykli w symulacjach
- Opanowanie trudnych przypadków brzegowych