anagramy

Anagramy – algorytm i implementacja w C++, Java, Python

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

Tak wygląda schemat blokowy tego algorytmu:

anagramy - schemat blokowy
grupa wsparcia matura z informatyki

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.

Funkcje pobierają dwa stringi i zwracają true (1), jeśli są anagramami oraz false (0), jeżeli nie są.

C++

Java

Python

You Might Also Like
1 Comment
  • Avatar photo
    windows95
    says:

    „Weźmy na przykład słowa „trauma” i „matura”. Oba są długie na 5 liter.” 😀
    btw, fajne materiały na tej stronce, szczególnie prosty do zrozumienia kod.

Dodaj komentarz

icon