Colecție (Pbinfo #1388)

Link către problema Colecție

O primă metodă de rezolvare ar fi să stocăm aparițiile fiecărui număr într-un vector clasic de frecvență, însă realizăm că folosirea acestuia ar depăși limita de memorie impusă de problemă, fiind o soluție ineficientă.

O optimizare adusă soluției de mai sus constă în utilizarea a doi vectori caracteristici, în schimbul vectorului de frecvență. Știind că o vedere unică are un singur număr atribuit, e de ajuns stocarea a două apariții. Dacă o vedere apare de două sau mai multe ori, aceasta nu mai respectă condiția pentru a fi în colecție. Chiar și cu această optimizare, obținem tot 0 puncte fiindcă am consumat toată memoria.

Secretul este să folosim bitset în schimbul vectorului clasic caracteristic. Bitset este un vector cu elemente de tip bool, doar că fiecare element din acesta nu va ocupa un octet ci un bit, astfel consumându-se mult mai puțină memorie.

Pentru utilizarea acestuia este necesară includerea librăriei bitset #include <bitset>. Declararea se va face astfel:

bitset <N> nume; //N reprezentand numarul de elemente

Fiecare element al acestuia se accesează asemănător vectorilor și pot lua doar valorile de 0 sau 1, asemănător tipului de data bool.

#include <iostream>
#include <bitset> //Pentru folosirea bitset-ului este necesara includerea librariei bitset

using namespace std;

int main()
{
    //Declaram un bitset cu 100 de elemente
    bitset <100> E;

    //Elementele pot lua doar valorile de 1 sau 0 (la fel ca tipul de data bool)
    E[0]=1;
    E[3]=0;

    //Afisam valoarea
    cout<<E[0];

    return 0;
}

O implementare în C++:

O altă variantă a soluției descrisă mai sus este implementarea hard-code a bitset-ului. Utilizăm doi vectori de tip unsigned int cu numele f1 și f2, fiecare având lungimea de n/32+1 elemente. Știm că fiecare element al vectorului are 32 de biți (un octet are 8 biți, iar știind că o variabilă de tip unsigned int ocupă 4 octeți, vom avea disponibili 8*4=32 biți per element). Astfel, un element din unul dintre cei doi vectori ia rolul de „vector caracteristic” cu 32 de elemente.

Ca exemplu, apariția numărului 3 se va afla în elementul f1[0], pe al 3-lea bit al acestuia. (3/32=0 – elementul în care se află bit-ul, 3%32=3 – al câtelea bit va fi marcat din acel element). Apariția numărului 33 se va afla în elementul f1[1], pe bit-ul 1 al acestuia. Deci formula generală pentru a determina atât poziția bit-ului în vector, cât și ce bit va trebui să schimbâm va fi:

X/32 elementul vectorului în care se află bit-ul ce trebuie schimbat

X%32bit-ul ce va trebui să îl schimbăm

unde X reprezintă numărul vederii din colecție.

Pentru a verifica și a seta biții, ne vom folosi de propietățile operațiilor pe biți:

  • Pentru a seta valoarea bit-ului i, vom folosi următoarea operație: n | (1<<i)
  • Pentru a afisa bit-ul i, vom folosi următoarea operație: ( (n>>i) & 1))

Instrucțiunea (1<<i) se echivalează cu \({2}^{i}\).

Pentru ușurința realizării operațiilor de mai sus, vom stoca valorile puterilor lui 2 într-un vector cu 32 de elemente (după cum am menționat, fiecare element al vectorului de tip unsigned int are 32 de biți)

Împărțim fiecare element al vectorului de tip unsigned int într-un „vector caracteristic” fiecare având 32 de elemente.

Implementare în C++:

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *

Acest site folosește Akismet pentru a reduce spamul. Află cum sunt procesate datele comentariilor tale.

octombrie 2018
L Ma Mi J V S D
1234567
891011121314
15161718192021
22232425262728
293031