A fost nevoie de un algoritm "rapid" pentru a sorta toate alocările posibile ale unităților K în categoriile N. Un google puțin, dar nu a găsit niciodată algoritmi fără bucle duble imbricate. Și, la urma urmei, ar fi de dorit să primim funcția de "dezvoltare" a unei combinații următoare pe baza celor precedente. Da, și stocați unități și zerouri, de preferință nu în linii (octet), ci în numere de mai multe cifre (biți). În acest caz, desigur, apare problema numărului de cifre al cifrelor, ca o restricție asupra parametrului N. Apoi vom folosi numerele digitale 64, 128, 256 de biți etc. De exemplu, puteți utiliza clasa big_int în biblioteca Boost. Estimăm toate variantele posibile de plasare a 3 unități în categorii de 5 cifre și ordinea de căutare a acestor variante:
Descrierea algoritmului
Total 10 opțiuni (numărul de combinații de cinci până la trei). Din punct de vedere vizual, algoritmul arata ca ruleaza de la unitatea din stanga la dreapta. Să o descriem formal folosind recursul:
1) Dacă caracterul din dreapta este "0", atunci vom găsi cea mai dreaptă dintre toate unitățile și o mutați cu o poziție în dreapta.
2) Dacă simbolul din dreapta este "1", atunci tăiați caracterul din dreapta și trimiteți combinația rezultată (lungimea N-1 cu unitățile K-1) la algoritmul 1. În valoarea obținută, găsim cea mai dreaptă unitate și inserați unitatea care a fost tăiată imediat după aceasta.
Setați operațiile necesare în C ++
Când stocăm o combinație în variabile multi-biți, avem nevoie de următoarele operații:
a) Funcția de determinare a valorii celei mai puțin semnificative cifre
b) Funcționarea deplasării spre dreapta celui mai mic unitate, cu inviolabilitatea cifrelor mai vechi.
c) Funcționarea adăugării unei unități la dreapta unității inferioare.
Acum, metoda de generare a primei combinații. Unitățile K sunt deplasate spre dreapta prin pozițiile (N-K).
Principala metodă de calcul al combinației este realizată prin algoritmul descris de noi:
plus
1) În locul funcțiilor (b) și (c), puteți utiliza macrocomenzi.
(Fii atent cu apelul imbricat de macro-uri - a fugit in el totusi)
2) Exact cu tipurile de constante:
(1 <<48) не равно (0x01000000000000)
(__int64 (1) <<48) равно (0x01000000000000)
Recomand foarte mult acest material: hack-uri de tip Twiddling
Trimiteți-le prietenilor: