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:
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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
//program sprawdzający, czy dwa słowa są anagramami //Kosiński Łukasz #include <iostream> #include <algorithm> #include <string> using namespace std; void sortuj(string &napis) { for(int i=0, zamiany=1; i<napis.length()-1 && zamiany!=0; i++) { zamiany=0; for(int j=0; j<napis.length()-1; j++) if(napis[j]>napis[j+1]) { swap(napis[j], napis[j+1]); zamiany++; } } } string formatuj(string s){ //funkcja zamieniajaca na male litery i usuwajaca biale znaki string s1 = ""; for(auto& c : s){ if(c == ' '){ continue; } s1 += (char)tolower(c); } return s1; } bool czy_anagramy(string napis1, string napis2) { if(napis1.length()!=napis2.length()) return false; sortuj(napis1); sortuj(napis2); if(napis1==napis2) return true; else return false; } int main() { string a, b; cout << "Podaj pierwszy napis: "; getline(cin, a); cout << "Podaj drugi napis: "; getline(cin, b); a = formatuj(a); b = formatuj(b); cout << czy_anagramy(a, b) << endl;// funkcja zwróci 1 jeśli napisy są anagramami //a 0 jeśli nie są system("pause"); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
package matura; import java.util.Scanner; public class Main { public static String sortWord(String s) { //tworzymy metodę sortującą znaki w słowie - korzystamy tutaj z sortowania bąbelkowego char[] characters = s.toCharArray(); for(int i = 0, changes = 1; i < characters.length-1 && changes != 0 ; i++) { changes = 0; for(int j = 0; j < characters.length-1; j++) { if(characters[j] > characters[j+1]) { char pom = characters[j+1]; characters[j+1] = characters[j]; characters[j] = pom; changes++; } } } System.out.println(new String(characters)); return new String(characters); } public static boolean czyAnagramy(String x, String y) { if(x.length() != y.length()) { // jeżeli słowa nie są tej samej długości, to na pewno nie są anagramami return false; } return sortWord(x).equals(sortWord(y)); //zwracamy, czy posortowane wyrazy wygladaja tak samo } public static void main(String[] args) { Scanner sc = new Scanner(System.in); // tworzymy instancję Scanner'a - będzie on pobierał słowa od użytkownika System.out.println("Program sprawdzający czy podane wyrazy są anagramami."); System.out.println("Podaj pierwsze słowo:"); String s1 = sc.nextLine().toLowerCase().replaceAll(" ", ""); // pobieramy słowo od użytkownika, jednocześnie zamieniając wszystko na małe litery i pozbywając się spacji System.out.println("Podaj drugie słowo:"); String s2 = sc.nextLine().toLowerCase().replaceAll(" ", ""); // pobieramy słowo od użytkownika, jednocześnie zamieniając wszystko na małe litery i pozbywając się spacji System.out.println("Podane wyrazy " + (czyAnagramy(s1, s2) ? "są" : "nie są") + " anagramami"); sc.close(); //zwalniamy zasoby } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
def sortujSlowo(slowo): #definujemy funkcje sorutjaca slowo - wykorzystujemy tutaj sortowanie babelkowe s = list(slowo) #poniewaz w Pythonie nie da sie modyfikowac stringa jako tablicy, potrzebujemy zapisac go jako liste zmian = 1 for i in range(len(s) - 1): if zmian == 0: break zmian = 0 for j in range(len(s) - 1): if s[j] > s[j + 1]: s[j], s[j + 1] = s[j + 1], s[j] zmian += 1 return s def czyAnagramy(x, y): if len(x) != len(y): #jezeli sa roznej dlugosci, to z gory wiadomo ze nie sa anagramami return False return sortujSlowo(x) == sortujSlowo(y) #w przeciwnym wypadku wystarczy sprawdzic, czy po posortowaniu sa identyczne print("Program sprawdzajacy czy dwa slowa sa anagramami") print("Podaj pierwsze slowo") s1 = input() #pobieramy pierwsze slowo print("Podaj drugie slowo") s2 = input() #pobieramy drugie slowo print("Podane slowa " + ("sa " if(czyAnagramy(s1, s2)) else "nie sa ") + "anagramami") |
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.