Strona główna » Algorytmy » Artykuły » Pangram
 

Pangram

https://mattomatti.com/a0094

Definicja

Pangram to takie wyrażenie, które zawiera wszystkie litery alfabetu co najmniej raz. Oczywiście najtrudniej jest znaleźć pangram, który zawiera dokładnie każdą literę tylko raz.

Przykładem panagramu w języku polskim jest wyrażenie "Mężny bądź, chroń pułk twój i sześć flag." (autor nieznany). Z kolei w języku angielskim najczęściej używanym panagramem (np. podczas wybierania czcionki) jest "The quick brown fox jumps over the lazy dog.".

Zadanie

Napisz program, który wczyta od użytkownika jedną linijkę tekstu ze standardowego wejścia, a następnie wypisze czy dane wyrażenie jest pangramem. Przetestuj działanie napisanego programu.

Strategia

Przed przystąpieniem do oceny czy występują wszystkie znaki należy poznać jak wygląda pełny alfabet. Informację tę można wpisać do programu na stałe, albo wczytać od użytkownika za każdym razem. Pozwoli to wtedy sprawdzać pangramy w różnych językach. W dalszym rozwiązaniu przyjmuje się, że sprawdzany będzie pangram utworzony z liter alfabetu łacińskiego (tj. nie będzie polskich znaków diaktrycznych).

Rozwiązanie proste

Znając długość alfabetu można zadeklarować tablicę wartości logicznych. Podczas przeglądania każdej litery po kolei odpowiednia pozycja w tablicy będzie aktualizowana na wartość prawda. Po przejrzeniu całego słowa można sprawdzić czy w tablicy występuje wartość fałsz co by znaczyło, że nie wszystkie znaki wystąpiły. Poniżej został przedstawiony kod, który sprawdza czy przekazane wyrażenie str jest panagramem. Zwracana jest wartość logiczna.

C++
C#
  1. bool czyPangram(string str) {
  2.   string alfabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  3.   bool* wystapienia = new bool[alfabet.length()];
  4.   for (int i = 0; i < alfabet.length(); i++)
  5.     wystapienia[i] = false;
  6.   for (int i = 0; i < str.length(); i++) {
  7.     int poz = alfabet.find(str[i]);
  8.     if (poz != string::npos)
  9.       wystapienia[poz] = true;
  10.   }
  11.   bool wynik = true;
  12.   for (int i = 0; i < alfabet.length(); i++)
  13.     wynik = wynik & wystapienia[i];
  14.   delete wystapienia;
  15.   return wynik;
  16. }

(2.) Określ alfabet i (3. - 5.) utwórz tablicę zaznaczając na początek, że żaden znak nie wystąpił. Potem (6.) dla każdej litery: (7.) znajdź jej pozycję w alfabecie i (8.) jeśli występuje to (9.) oznacz to. Na koniec (11. - 13.) sprawdź czy wszystkie znaki wystąpiły.

Rozwiązanie optymalne

Wcześniejszy kod można przyśpieszyć poprzez eliminację drugiej pętli. Jak to można osiągnąć? Podczas oznaczania danej litery jako, że wystąpiła, pod warunkiem, że nie została wcześniej oznaczona, należy zwiększyć ile różnych znaków zostało znalezionych. Na koniec wystarczy porównać licznik różnych znaków do długości alfabetu i zwrócić wynik porównania. Dodatkowym rozwiązaniem poprawienie wydajności algorytmu polega na sprawdzeniu długości wyrażenia na początku funkcji. Jeśli długość tekstu str jest mniejsza niż alfabetu to nie ma szans, aby wystąpiły wszystkie znaki.

Uwzględniając przedstawione poprawki kod przedstawia się następująco:

C++
C#
  1. bool czyPangram(string str) {
  2.   string alfabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  3.   bool* wystapienia = new bool[alfabet.length()];
  4.   for (int i = 0; i < alfabet.length(); i++)
  5.     wystapienia[i] = false;
  6.   int roznych = 0;
  7.   for (int i = 0; i < str.length(); i++) {
  8.     int poz = alfabet.find(str[i]);
  9.     if (poz != string::npos & !wystapienia[poz]) {
  10.       roznych++;
  11.       wystapienia[poz] = true;
  12.     }
  13.   }
  14.   delete wystapienia;
  15.   return roznych == alfabet.length();
  16. }

(2.) Określ alfabet i (3. - 5.) utwórz tablicę zaznaczając na początek, że żaden znak nie wystąpił i (6.) zadeklaruj licznik ile różnych znaków znaleziono. Potem (7.) dla każdej litery: (8.) znajdź jej pozycję w alfabecie i (9.) jeśli występuje po raz pierwszy to (10.) zwiększ licznik i (11.) oznacz to. Na koniec zwróć porównanie licznika ile znaleziono różnych znaków oraz długość alfabetu. Jeśli są równe to znaczy, że w zmiennej str przekazano panagram.

Testowanie funkcji

Obydwa przedstawione kodu funkcji czyPanagram() można sprawdzić przy pomocy poniższego fragmentu kodu. Oczywiście należy pamiętać, że obie funkcje czyPangram() rozpoznają tylko duże litery alfabetu łacińskiego, a wszystkie pozostałe znaki ignorują.

C++
C#
  1. int main () {
  2.   string str;
  3.   cout << "Podaj wyrazenie do sprawdzenia: ";
  4.   getline(cin, str);
  5.   bool w = czyPangram(str);
  6.   cout << "To " << (w ? "" : "nie ") << "jest panagram";
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Napisz funkcję czyPangram(), która sprawdzi czy dane wyrażenie jest pangramem. Funkcja powinna wypisać odpowiedni komunikat na ekran: "Nie panagram", gdy nie jest panagram, "Dopracowany Panagram", gdy każda litera występuje dokładnie raz i jest to panagram, w pozostałych przypadkach tylko "Panagram". Przetestuj działanie programu.

Przykładowo dla "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG" program powinien wypisać:

  1. Panagram