Łączenie Liczb w Pangramy

Zadanie

Napisz algorytm, który w podanej tablicy liczb policzy ile jest par, które po złączeniu razem tworzą pangram. Dla przypomnienia liczba pangram zawiera wszystkie możliwe cyfry (w danym systemie liczbowym). Przyjmujemy, że podana tablica wartości zawiera tylko dodatnie liczby naturalny złożone z maksymalnie 10 cyfr.

Przykład

Przykładowo dana jest tablica 4 liczb: 12345, 567890, 12345678 oraz 910. Można tutaj znaleźć dokładnie 3 pary, które tworzą pangramy. Są to (12345, 567890), (567890, 12345678) oraz (12345678, 910). Pozostałe 3 pary nie tworzą pangramów. Przykładowo połączenie (12345, 12345678) upraszcza się do 12345678 i nadal brakuje cyfr 0 i 9.

Implementacja

Rozwiązanie Proste

Głównym problemem w zadaniu jest szybkie określenie czy dwie liczby tworzą pangram. (Wybierania kolejnych par liczb nie można przyśpieszyć). Jedna z metod polega na przygotowaniu tablicy cyfr i oznaczaniu, które cyfry występują w obydwu liczbach, a które nie. Jeśli chociaż jedna cyfra nie występuje to oczywiście nie jest to pangram. Obliczanie takiej tablicy dla każdej pary nie jest zbyt optymalne, ponieważ każda liczba należy do n-1 par i tyle razy musi być ona ponownie przeanalizowana. Oznacza to, że złożoność takiego algorytmu ma złożoność O(n²k), gdzie n to ilość liczb, a k określa długość najdłuższej liczby.

Przykładowy kod funkcji do sprawdzania czy obydwie liczby złączone tworzą pangram wygląda następująco:

1. bool CzyPangramZlaczenie(int a, int b) {
2.   bool cyfry[10] = { false };
3.   while (a > 0) {
4.     cyfry[a % 10] = true;
5.     a /= 10;
6.   }
7.   while (b > 0) {
8.     cyfry[b % 10] = true;
9.     b /= 10;
10.   }
11.   for (int i = 0; i < 10; i++)
12.     if (!cyfry[i])
13.       return false;
14.   return true;
15. }

Dla obydwu liczb deklarowana jest tablica 10 wartości logicznych, a następnie na podstawie cyfr w obu liczbach oznaczane są występujące cyfry. Na koniec zwracana jest wartość prawda jeśli wszystkie wartości są prawdą.

Do tego algorytmu potrzebna jest odpowiednia funkcja, która wywoła poprzednią funkcję dla każdej pary:

1. int PoliczParyPangramow(vector<int> dane) {
2.   int ilepar = 0;
3.   for (int i = 0; i < dane.size(); i++) {
4.     for (int j = i + 1; j < dane.size(); j++) {
5.       if (CzyPangramZlaczenie(dane[i], dane[j])) {
6.         ilepar++;
7.       }
8.     }
9.   }
10.   return ilepar;
11. }

Na początku inicjalizowany jest licznik, a następnie wybierane są wszystkie kolejne pary. Na koniec wystarczy zwrócić wartość licznika.

Rozwiązanie Optymalne

Sprawdzanie czy dwie liczby tworzą pangram można przyśpieszyć poprzez odpowiednią funkcję skrótu. Dla każdej liczby chcemy wiedzieć jakie cyfry występują (tylko czy cyfra występuje czy nie, a nie ile razy), więc można przygotować wartość, gdzie na i-tej pozycji jeśli wystąpi wartość 1 to znaczy, że cyfra i występuje. Potem przy sprawdzaniu wystarczy wykonać operację lub na skrótach obu wartości i porównać do wartości złożonej z 10 bitów 1, która oznacza, że wszystkie cyfry występują. W zapisie heksadecymalnym taka wartość wynosi 0x3FF, a w dziesiętnym 1023.

Przykładowo liczba 12345 to 0000111110₂, a 567890 to 1111100001₂. Wykonując operację lub na tych wartościach otrzymujemy 1111111111₂ = 1023 = 0x3FF. Dla pary, która nie tworzy pangramu tj. (12345, 910) = (0000111110₂, 1000000011₂) wartość ta będzie inna. W tym przypadku 1000111111₂ = 575.

Takie podejście zmienia nieznacznie szkielete programu. Funkcja Hashuj() nie zwraca wartości logicznej, a konkretną wartość liczbową:

1. bool CzyPangramZlaczenie(int a, int b) {
2.   bool cyfry[10] = { false };
3.   while (a > 0) {
4.     cyfry[a % 10] = true;
5.     a /= 10;
6.   }
7.   while (b > 0) {
8.     cyfry[b % 10] = true;
9.     b /= 10;
10.   }
11.   for (int i = 0; i < 10; i++)
12.     if (!cyfry[i])
13.       return false;
14.   return true;
15. }

Początkowo wszystkie bity wartości są ustawione na 0, a następnie odpowiednie bity są ustwiane na wartość 1 na podstawie pobieranych cyfr z liczby.

Z kolei funkcja PoliczParyPangramow() przed rozpoczęciem pętli przygotowuje tablicę gotowych skrótów, a dopiero później rozpoczyna poszukiwania par.

1. int PoliczParyPangramow(vector<int> dane) {
2.   int ilepar = 0;
3.   for (int i = 0; i < dane.size(); i++) {
4.     for (int j = i + 1; j < dane.size(); j++) {
5.       if (CzyPangramZlaczenie(dane[i], dane[j])) {
6.         ilepar++;
7.       }
8.     }
9.   }
10.   return ilepar;
11. }

Dzięki takiemu zabiegowi koszta sprawdzania czy wybrana para liczb pozwoli na utworzenie pangramu spada do O(1), a więc złożoność całego algorytmu spadła do O(n²).

Testowanie funkcji

W celu przetestowania napisanego kodu można skorzystać z poniższej funkcji, która wczytuje odpowiednie liczby, a następnie wypisuje dane na ekran.

1. int main() {
2.   int n, tmp;
3.   cout << "Ile liczb?\n n = ";
4.   cin >> n;
5.   vector<int> dane;
6.   while (n--) {
7.     cin >> tmp;
8.     dane.push_back(tmp);
9.   }
10.   int ilepar = PoliczParyPangramow(dane);
11.   cout << "Par: " << ilepar;
12.   system("pause");
13.   return 0;
14. }

• Kod źródłowy Implementacja