nCr esilaskettujen kertomien avulla
Laske kombinaatioita modulo alkuluvun
nCr esilaskettujen kertomien avulla on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 4/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.
Yhdistelmien laskeminen
Monissa tehtävissä kysytään, monellako tavalla r alkiota voidaan valita n alkiosta. Tätä merkitään nCr:llä. Kilpailuissa lukumäärä pyydetään usein alkulukumodulolla laskettuna. 🧮
Kertomakaava
Klassinen kaava on nCr = n! / (r! (n − r)!). Haasteena on, että jakaminen ei toimi moduloarvoilla tavalliseen tapaan.
# nCr = n! / (r! * (n-r)!)Kertomat kasvavat valtaviksi
Yksittäinen kertoma kasvaa tähtitieteellisen suureksi, joten laskekaa jokainen niistä modulo p:n suhteen. Näin arvot pysyvät pieninä ja kaava toimii modulossa täsmällisesti.
Esilaskekaa kaikki kertomat
Muodostakaa fact-taulukko kerran suurimpaan tarvittavaan n-arvoon asti. Jokainen alkio on edellinen alkio kerrottuna indeksillä, ja modulo p otetaan laskennan aikana.
fact[i] = fact[i-1] * i % MODJako tarvitsee käänteisluvut
Kaava jakaa kahdella kertomalla, joten tarvitsette niiden modulaariset käänteisluvut. Muistakaa, että käänteisluku muuttaa jaon siistiksi kertolaskuksi.
Laskekaa suurimman kertoman käänteisluku
Laskekaa suurimman kertoman käänteisluku vain kerran Fermat'n lauseen avulla käyttämällä pow-funktiota eksponentilla p − 2. Tämä yksi kutsu antaa lähtökohdan muille.
inv_fact[n] = pow(fact[n], MOD - 2, MOD)Laskekaa käänteiskertomat takaperin
Muodostakaa muut käänteiskertomat yhdellä takaperin etenevällä kierroksella, kullekin seuraavan alkion ja indeksin tulona. Muita pow-kutsuja ei tarvita.
inv_fact[i] = inv_fact[i+1] * (i+1) % MODMuodostakaa nCr
Nyt nCr on yksinkertaisesti fact[n] × inv_fact[r] × inv_fact[n − r], kaikki modulo p:n suhteen. Kyselyä kohti tarvitaan kolme hakua ja kaksi kertolaskua.
C = fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MODJokainen kysely on vakioaikainen
Esilaskennan jälkeen jokaisen yhdistelmän vastaus saadaan ajassa O(1). Siksi tämä menetelmä on tehokas, kun tehtävässä pyydetään tuhansia nCr-arvoja.
Käsitelkää reunatapaukset
Jos r on negatiivinen tai suurempi kuin n, vastaus on 0. Tarkistakaa rajat ensin, jotta ette koskaan käytä kertomataulukon ulkopuolista indeksiä.
if r < 0 or r > n: return 0Mitoittakaa taulukot väljästi
Asettakaa taulukon kooksi kaikkien kyselyiden suurin n-arvo ja lisätkää siihen hieman varaa. Liian pieni limit aiheuttaa täällä usein indeksivirheitä.
N = 200005Pikatarkistus
Kuinka nopeasti yksi nCr-kysely suoritetaan esilaskennan jälkeen?
Kertaus
Esilaskette kertomat ja niiden käänteisluvut kerran, minkä jälkeen jokainen nCr saadaan ajassa O(1) kolmella haulla. Tarkistakaa r:n rajat ja mitoittakaa taulukot riittävän suuriksi. 🏆
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 ”nCr esilaskettujen kertomien avulla” ilmainen?
Kyllä – oppitunnin ”nCr esilaskettujen kertomien avulla” 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 ”nCr esilaskettujen kertomien avulla”?
Laske kombinaatioita modulo alkuluvun 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 4/4.
Kuinka kauan ”nCr esilaskettujen kertomien avulla”-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
- Laskeminen alkuluvun moduloarvolla
- Nopea modulaarinen potenssilasku
- Modulaarinen käänteisluku Fermat'n avulla
- nCr esilaskettujen kertomien avulla