Permutaatiot ja N-kuningattaren idea
Sijoita alkiot ja peruuta ristiriidoissa
Permutaatiot ja N-kuningattaren idea on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Osajoukoista järjestyksiin
Permutaatio on kaikkien alkioiden järjestäminen johonkin järjestykseen. Niiden muodostaminen on osajoukkojen jälkeen seuraava takaisinhaun taito. 🔀
Kuinka monta permutaatiota on
n alkiolla on n-kertoma permutaatiota, koska ensimmäiseen paikkaan on n vaihtoehtoa, seuraavaan n − 1 ja niin edelleen. Määrä kasvaa nopeasti.
Sijoittakaa yksi alkio kerrallaan
Rekursio täyttää paikat vasemmalta oikealle. Valitkaa jokaisessa vaiheessa yksi käyttämätön alkio, sijoittakaa se paikalleen ja jatkakaa rekursiota jäljellä olevilla alkioilla.
Seuratkaa käytettyjä alkioita
Totuusarvoinen käytettyjen alkioiden taulukko merkitsee jo sijoitetut alkiot, joten jokainen esiintyy täsmälleen kerran jokaisessa permutaatiossa.
Permutaatiot koodissa
Tämä takaisinhaku sijoittaa käyttämättömän arvon, kutsuu rekursiota ja vapauttaa arvon sitten seuraavaa haaraa varten.
def perm(cur):
if len(cur) == n:
out.append(cur[:]); return
for x in a:
if x not in cur:
perm(cur + [x])Käyttäkää itertoolsia, kun se on sallittua
Nopeissa kilpailutehtävissä Pythonin itertools.permutations antaa kaikki järjestykset ilman, että kirjoitatte rekursiota itse.
from itertools import permutations
for p in permutations(a):
print(p)N-Queens-ongelma
N-Queens -tehtävässä n kuningatarta sijoitetaan n × n -laudalle niin, etteivät ne uhkaa toisiaan. Se on klassinen takaisinhakupulma. 👑
Yksi kuningatar riville
Koska kaksi kuningatarta ei voi olla samalla rivillä, sijoittakaa täsmälleen yksi kuningatar riville ja valitkaa vain sen sarake. Näin hakua voidaan supistaa huomattavasti.
Tarkistakaa kolme ristiriitaa
Ennen sijoittamista hylätkää kaikki vaihtoehdot, joissa sarake tai diagonaali on jo käytössä. Seuratkaa käytettyjä sarakkeita ja molempia diagonaalisuuntia joukoissa.
if c in cols or r-c in d1 or r+c in d2:
continueTehkää takaisinhaku umpikujassa
Jos millään sarakkeella ei voi sijoittaa kuningatarta riville, haara epäonnistuu. Tehkää takaisinhaku, poistakaa viimeinen kuningatar ja kokeilkaa sen seuraavaa vaihtoehtoa.
Yhteinen toimintamalli
Permutaatioilla ja N-Queens-tehtävällä on sama rakenne: valitse, rekursioi, kumoa. Kun tunnistatte tämän, useimmat sijoittelupulmat ratkeavat samalla mallilla.
Pikatarkistus
Miksi N-Queens-tehtävässä sijoitetaan vain yksi kuningatar riville?
Kertaus: valitse, rekursioi, kumoa
Muodostitte permutaatiot sijoittamalla käyttämättömiä alkioita ja opitte, että N-Queens käyttää samaa valitse–rekursioi–kumoa-mallia ristiriitojen tarkistuksineen. 🎯
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Permutaatiot ja N-kuningattaren idea” ilmainen?
Kyllä – oppitunnin ”Permutaatiot ja N-kuningattaren idea” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Permutaatiot ja N-kuningattaren idea”?
Sijoita alkiot ja peruuta ristiriidoissa Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.
Kuinka kauan ”Permutaatiot ja N-kuningattaren idea”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Ajattele rekursiivisesti: kanta ja rekursio
- Kaikkien osajoukkojen generointi
- Permutaatiot ja N-kuningattaren idea
- Karsi selvitäksesi aikarajasta