Algorytmy, C++, Matura z informatyki - nauka i materiały.

Anagramy – algorytm i implementacja w C++

anagramy

Kolejnym z algorytmów, który warto znać podchodząc do matury z informatyki jest algorytm sprawdzający, czy dwa napisy lub wyrazy są anagramami. Znając taki algorytm już na starcie możemy oszczędzić nieco maturalnego czasu, a ten jest na wagę złota. Algorytm na anagramy lepiej, więc poznać zawczasu, aby przypadkiem się na nim nie potknąć.

Czym są anagramy?

Anagramy są słowami lub zdaniami, które tworzy się przestawiając znaki innego wyrazu. Anagramy zawsze więc mają taką samą długość i składają się z tych samych znaków.  Wiele osób spotyka się ze słowami będącymi anagramami nawet nie wiedząc, że tak się poprawnie je określa. Przykładowymi anagramami są:

  • „matura” i „trauma”
  • „arbuz” i „burza”
  • „Tom Marvolo Riddle” i „I am Lord Voldemort”
  • „101101” i  „111001” – liczby też mogą być anagramami

Jak widać wszystkie te wyrazy można ułożyć przestawiając znaki drugiego wyrazu z pary.

 

Jak sprawdzić, czy dwa wyrazy są anagramami?

Chcąc sprawdzić, czy dwa wyrazy to anagramy, już na samym początku należy porównać ich długość. Jeśli długości są różne to wyrazy nie są swoimi anagramami. Krótka piłka. Następnie oba wyrazy sortujemy alfabetycznie (bądź od najmniejszej do największej jeśli mowa o liczbach). Jeśli po posortowaniu wyrazy wyglądają identycznie to znaczy, że są anagramami.

Weźmy na przykład słowa „trauma” i „matura”. Oba są długie na 5 liter. Po posortowaniu oba będą wyglądały w ten sposób: „aamrtu”, więc są anagramami.

Tak za pomocą pseudokodu można przedstawić algorytm sprawdzający, czy dwa słowa są anagramami.

 

wczytaj wartość pierwszego napisu

wczytaj wartość drugiego napisu

jeżeli napisy są różnej długości

                zwróć fałsz

jeżeli napisy są równej długości

                posortuj pierwszy napis

                posortuj drugi napis

                jeżeli posortowane napisy są sobie równe

                               zwróć prawdę

                w przeciwnym wypadku

                               zwróć fałsz

 

 

Program sprawdzający, czy dwa słowa są anagramami.

Program pisałem w oparciu o algorytm sortowania bąbelkowego, które już omawiałem. Leciutko przerobiłem program z wpisu o tej metodzie sortowania, aby teraz operował na stringach.

Funkcja czy_anagramy pobiera dwa stringi i zwraca true – 1, jeśli są anagramami oraz false – 0, jeżeli nie są.

 

 

Program może niepoprawnie działać dla całych zdań lub słów o różnej wielkości znaków. Wystarczy przerobić obecny program w ten sposób, aby funkcja usuwała białe znaki ze stringa i transformowała wszystkie litery do tej samej wartości. Mój wewnętrzny leń zabronił mi jednak zaprzątać sobie tym głowy 😉

 

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *