Algoritmus az összes kombinációra való rendezéshez
Szükség van egy "gyors" algoritmusra az N kategóriák összes K-egysé- gének elosztására. Egy kis google, de soha nem találtam algoritmust kétszer egymásba ágyazott hurkok nélkül. Végülis kívánatos lenne egy következő kombináció "fejlődésének" funkciója a korábbiak alapján. Igen, tárolja az egységeket és a nullákat, lehetőleg nem sorokban (byte), hanem több számjegyű számokban (bitben). Ebben az esetben természetesen felmerül a numerikus számkapacitás kérdése, mint a N. paraméter korlátozása. Ezután a számjegyek számát 64, 128, 256 bit stb. Használjuk. Például használhatod a big_int osztályt a Boost könyvtárban. Becsüljük meg, hogy az 5-jegyű kategóriákban 3 egységnyi elhelyezés lehetséges változatai és ezeknek a változatoknak a sorrendje:
Az algoritmus leírása
Összesen 10 lehetőség (a kombinációk száma öt-három). Vizuálisan az algoritmus úgy néz ki, mintha balról jobbra haladna. Lássuk le formálisan rekurzív módon:
1) Ha a legalapvetőbb karakter "0", akkor megtaláljuk a legrövidebbet az összes egység között, és jobbra mozgatjuk 1 pozíciót.
2) Ha a jobb oldali szimbólum "1", akkor vágja el a jobb szélső karaktert és küldje el az eredményül kapott kombinációt (az N-1 hosszúságú K-1 egységekkel) az 1. algoritmushoz. A kapott értékben megtaláljuk a jobb szélső egységet, és közvetlenül beillesztjük az előzőleg kivágott egységet.
Állítsa be a szükséges műveleteket a C ++-ban
Amikor egy kombinációt több bites változókba tárolunk, a következő műveletekre van szükségünk:
a) A legkisebb számjegy értékének meghatározása
b) A legalacsonyabb egység jobb oldalára való áthelyezés, a régebbi számjegyek sérthetetlenségével.
c) Egy egység csatlakoztatása a legalacsonyabb egység jobb oldalán.
Most az első kombináció létrehozásának módja. A K egységek jobb (N-K) pozícióval vannak eltolva.
A kombináció számításának fő módját az általunk leírt algoritmus valósítja meg:
kiegészítés
1) A (b) és (c) függvény helyett makrókat használhat.
(Legyen óvatos a makrók beágyazott hívásakor!)
2) Pontos a konstans típusokkal:
(1 <<48) не равно (0x01000000000000)
(__int64 (1) <<48) равно (0x01000000000000)
Nagyon ajánlom ezt az anyagot: Bit Twiddling Hacks