0Pricing
Competitive Programming Academy · Lekcja

Wykrywanie cykli w symulacjach

Pomijanie kroków naprzód, gdy stan się powtarza

Wykrywanie cykli w symulacjach to bezpłatna lekcja Competitive Programming Academy 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 Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy 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) % length

Wykonaj 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 Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Wykrywanie cykli w symulacjach”?

Pomijanie kroków naprzód, gdy stan się powtarza Ćwiczysz Competitive Programming Academy 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ąć Competitive Programming Academy?

Nie wymagamy żadnego doświadczenia. Competitive Programming Academy 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 Competitive Programming Academy?

Tak. Każda lekcja Competitive Programming Academy 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

  1. Modelowanie stanu i przechodzenie dalej
  2. Przejścia po siatce i wektory kierunku
  3. Wykrywanie cykli w symulacjach
  4. Opanowanie trudnych przypadków brzegowych
← Powrót do Competitive Programming Academy