Strona główna » Algorytmy » Artykuły » Łączenie Liczb w Pangramy
 

Łączenie Liczb w Pangramy

https://mattomatti.com/a0252

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(n2k), 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:

C++C#
Python
  1. def CzyPangramZlaczenie(a, b):
  2. cyfry = [False for i in range(10)]
  3. while (a > 0):
  4. cyfry[a % 10] = True
  5. a //= 10
  6. while (b > 0):
  7. cyfry[b % 10] = True
  8. b //= 10
  9. return not False in cyfry

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:

C++C#
Python
  1. def PoliczParyPangramow(dane):
  2. ilepar = 0
  3. for i in range(len(dane)):
  4. for j in range(i + 1, len(dane)):
  5. if (CzyPangramZlaczenie(dane[i], dane[j])):
  6. ilepar += 1
  7. return ilepar

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 00001111102, a 567890 to 11111000012. Wykonując operację lub na tych wartościach otrzymujemy 11111111112 = 1023 = 0x3FF. Dla pary, która nie tworzy pangramu tj. (12345, 910) = (00001111102, 10000000112) wartość ta będzie inna. W tym przypadku 10001111112 = 575.

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

C++C#
Python
  1. def CzyPangramZlaczenie(a, b):
  2. cyfry = [False for i in range(10)]
  3. while (a > 0):
  4. cyfry[a % 10] = True
  5. a //= 10
  6. while (b > 0):
  7. cyfry[b % 10] = True
  8. b //= 10
  9. return not False in cyfry

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.

C++C#
Python
  1. def PoliczParyPangramow(dane):
  2. ilepar = 0
  3. for i in range(len(dane)):
  4. for j in range(i + 1, len(dane)):
  5. if (CzyPangramZlaczenie(dane[i], dane[j])):
  6. ilepar += 1
  7. return ilepar

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(n2).

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.

C++C#
Python
  1. print("Podaj liczby:")
  2. dane = [int(x) for x in input().split()]
  3. ilepar = PoliczParyPangramow(dane)
  4. print("Par:", ilepar)