Permutacje i idea N hetmanów
Umieszczanie elementów i wycofywanie się przy konfliktach
Permutacje i idea N hetmanów 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.
Od podzbiorów do uporządkowań
Permutacja to ułożenie wszystkich elementów w określonej kolejności. Ich generowanie jest kolejną umiejętnością z zakresu przeszukiwania z nawrotami po podzbiorach. 🔀
Ile istnieje permutacji
Istnieje n silnia permutacji n elementów, ponieważ pierwsze miejsce można obsadzić na n sposobów, kolejne na n minus 1 sposobów i tak dalej. Liczba ta szybko rośnie.
Umieszczaj po jednym elemencie
Rekurencja wypełnia pozycje od lewej do prawej. Na każdym kroku wybierają Państwo nieużyty element, umieszczają go i wywołują rekurencję dla pozostałych.
Śledzenie użytych elementów
Tablica wartości logicznych used array oznacza, które elementy zostały już umieszczone, dzięki czemu każdy pojawia się dokładnie raz w każdej permutacji.
Permutacje w kodzie
To przeszukiwanie z nawrotami umieszcza nieużytą wartość, wykonuje rekurencję, a następnie zwalnia ją dla kolejnej gałęzi.
def perm(cur):
if len(cur) == n:
out.append(cur[:]); return
for x in a:
if x not in cur:
perm(cur + [x])Używaj itertools, gdy jest to dozwolone
W szybkich rozwiązaniach konkursowych Pythonowe itertools.permutations generuje każde uporządkowanie, dzięki czemu nie trzeba samodzielnie pisać rekurencji.
from itertools import permutations
for p in permutations(a):
print(p)Problem N-Queens
Problem N-Queens polega na umieszczeniu n hetmanów na planszy n na n tak, aby żadne dwa się nie atakowały. To klasyczna łamigłówka wykorzystująca przeszukiwanie z nawrotami. 👑
Jeden hetman w każdym wierszu
Ponieważ żadne dwa hetmany nie mogą znajdować się w tym samym wierszu, umieszcza się dokładnie jednego hetmana w każdym wierszu i wybiera tylko jego kolumnę. To znacznie zmniejsza przestrzeń wyszukiwania.
Sprawdzanie trzech rodzajów konfliktów
Przed umieszczeniem hetmana należy odrzucić każdą zajętą kolumnę lub przekątną. Zajęte kolumny oraz oba kierunki przekątnych należy śledzić w zbiorach.
if c in cols or r-c in d1 or r+c in d2:
continueCofanie po ślepej uliczce
Jeśli wiersz nie ma żadnej dostępnej kolumny, gałąź kończy się niepowodzeniem. Należy wykonać nawrót, usunąć ostatniego hetmana i wypróbować jego kolejną możliwość.
Wspólny schemat
Permutacje i problem N-Queens mają tę samą strukturę: wybierz, wykonaj rekurencję, cofnij wybór. Gdy dostrzegą Państwo ten schemat, większość problemów z umieszczaniem elementów można rozwiązać za pomocą tego samego szablonu.
Szybkie sprawdzenie
Dlaczego w problemie N-Queens umieszcza się tylko jednego hetmana w każdym wierszu?
Podsumowanie: wybierz, wykonaj rekurencję, cofnij wybór
Wygenerowali Państwo permutacje, umieszczając nieużyte elementy, i dowiedzieli się, że problem N-Queens wykorzystuje ten sam schemat wybierz-wykonaj rekurencję-cofnij wybór wraz ze sprawdzaniem konfliktów. 🎯
Często zadawane pytania
Czy lekcja „Permutacje i idea N hetmanów” jest bezpłatna?
Tak — pełny tekst „Permutacje i idea N hetmanów” 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 „Permutacje i idea N hetmanów”?
Umieszczanie elementów i wycofywanie się przy konfliktach Ć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 „Permutacje i idea N hetmanów”?
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
- Myślenie rekurencyjne: baza i rekurencja
- Generowanie wszystkich podzbiorów
- Permutacje i idea N hetmanów
- Przycinanie, aby zmieścić się w limicie czasu