Zadanie 1. Anagramy

Dwa napisy są anagramamianagramanagramami, jeśli pierwszy z nich można utworzyć przez przestawienie liter z drugiego, używając jego wszystkich znaków.

W pliku danych napisy.txt znajduje się 1000 par napisów, z których każdy jest długości od $2$ do $20$ znaków, składających się z wielkich liter alfabetu łacińskiego (26 liter od A do Z). Każda para napisów jest zapisana w osobnym wierszu, a napisy oddzielone są pojedynczym znakiem odstępu.

Napisz program, który dla danych z pliku napisy.txt wyznaczy liczbę wierszy zawierających napisy będące swoimi anagramami. Wynik zapisz w pliku anagramy.txt.

Do oceny oddajesz:

• plik anagramy.txt zawierający odpowiedź (liczbę par napisów zapisanych w pliku napisy.txt będących anagramami),

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie

Chcąc sprawdzić, czy podane dwa słowa są anagramami, wystarczy w obu słowach posortować litery w kolejności alfabetycznej. Jeżeli powstałe słowa będą identyczne, oznacza to, że oryginalne słowa są anagramami. W omawianym algorytmie skorzystamy z sortowania bąbelkowego.

Na początku zainicjalizujmy potrzebne zmienne i wczytajmy dane z pliku. Zmienna n będzie przechowywać liczbę par napisów do odczytania z pliku i zbadania. Zmienna anagramy będzie przechowywać liczbę wierszy z anagramami. Tablicę indeksujemy od zera, tak jak w językach programowania dostępnych na egzaminie maturalnym:

n ← 1000 # liczba par napisów w pliku
anagramy ← 0
napisy[0..n - 1][0..1] ← wczytaj dane z pliku "napisy.txt"

Zapisujemy pętlę, w której będziemy sprawdzać występowanie anagramów dla każdego wiersza. Skorzystamy z funkcji długość(), którą możemy zaimplementować w każdym z dostępnych na maturze języków programowania. Jeżeli długości wyrazów są różne, możemy pominąć sortowanie, ponieważ słowa na pewno nie są anagramami, i przejść do następnej pary:

n ← 1000 # liczba par napisów w pliku
anagramy ← 0
napisy[0..n - 1][0..1] ← wczytaj dane z pliku "napisy.txt"

dla i = 0, 1, ..., n - 1 wykonuj:
	jeżeli długość(Napisy[i][0]) != długość(Napisy[i][1]):
		przejdź do kolejnej iteracji

Następnym krokiem będzie posortowanie obu wyrazów z pary za pomocą sortowania bąbelkowego i sprawdzenie, czy są takie same. Implementację sortowania przeanalizujemy po głównej części programu. Posortowane kopie zapisujemy do zmiennych wyraz_pierwszy oraz wyraz_drugi:

n ← 1000 # liczba par napisów w pliku
anagramy ← 0
napisy[0..n - 1][0..1] ← wczytaj dane z pliku "napisy.txt"

dla i = 0, 1, ..., n - 1 wykonuj:
	jeżeli długość(napisy[i][0]) != długość(napisy[i][1]):
		przejdź do kolejnej iteracji

	wyraz_pierwszy ← sortowanie(napisy[i][0])
	wyraz_drugi ← sortowanie(napisy[i][1])

Jeżeli posortowane napisy są sobie równe, inkrementujemy zmienną anagramy:

n ← 1000 # liczba par napisów w pliku
anagramy ← 0
napisy[0..n - 1][0..1] ← wczytaj dane z pliku "napisy.txt"

dla i = 0, 1, ..., n - 1 wykonuj:
	jeżeli długość(napisy[i][0]) != długość(napisy[i][1]):
		przejdź do kolejnej iteracji

	wyraz_pierwszy ← sortowanie(napisy[i][0])
	wyraz_drugi ← sortowanie(napisy[i][1])
	
	jeżeli wyraz_pierwszy = wyraz_drugi:
		anagramy ← anagramy + 1

Po zakończeniu pętli zapisujemy wartość zmiennej anagramy do pliku wynikowego i zamykamy pliki.

n ← 1000 # liczba par napisów w pliku
anagramy ← 0
napisy[0..n - 1][0..1] ← wczytaj dane z pliku "napisy.txt"

dla i = 0, 1, ..., n - 1 wykonuj:
	jeżeli długość(napisy[i][0]) != długość(napisy[i][1]):
		przejdź do kolejnej iteracji

	wyraz_pierwszy ← sortowanie(napisy[i][0])
	wyraz_drugi ← sortowanie(napisy[i][1])
	
	jeżeli wyraz_pierwszy = wyraz_drugi:
		anagramy ← anagramy + 1

zapisz anagramy do pliku "anagramy.txt"
zamknij plik "napisy.txt"
zamknij plik "anagramy.txt"

Przejdźmy do implementacji algorytmu sortowania bąbelkowego. Na początek inicjujemy pętlę, odpowiedzialną za wykonywanie kolejnych cykli sortowania. W każdym cyklu sortowania jeden element zostanie ustawiony na odpowiednim miejscu w tablicy lub ciągu. Oznacza to, że pętla ta musi się wykonać n - 1 razy, gdzie n jest długością sortowanego ciągu. Gdy posortujemy n - 1 elementów, ostatni element również będzie znajdował się w odpowiednim miejscu. Definiujemy także zmienną zamiana, służącą do przechowywania informacji, czy w danej serii porównań nastąpiła zamiana. Ustawiamy jej wartość na fałsz:

sortowanie(napis)
	n ← długość(napis)
	dla i = 0, 1, 2, ... n - 2 wykonuj:
		zamiana ← fałsz

Następnie zapisujemy drugą pętlę, w której zmienna sterującazmienna sterująca w pętli (iterator)zmienna sterująca będzie iterować po wszystkich znakach napisu oprócz pierwszego (ponieważ każdy znak będziemy porównywać z jego sąsiadem na lewo) oraz tych, które już znajdują się na właściwych pozycjach (zatem pominiemy i - końcowych pozycji). W celu ustalenia kolejności znaków w poszczególnych wierszach będziemy porównywać ich kody ASCIIASCIIASCII. W niektórych językach programowania, takich jak np. Python, Java i C++ (w wyrażeniach logicznych instrukcji warunkowych i pętli), możemy po prostu zapisać  znaki, a komputer porówna ich kody ASCII bez dodatkowych działań z naszej strony.  Inne języki programowania mogą potrzebować konwersji znaku do kodu ASCII. Dla ujednolicenia notacji w miejscach, w których używany będzie kod ASCII znaku, zastosujemy funkcję ascii(), zwracającą kod ASCII podanego jej znaku (funkcja taka jest łatwa do zaimplementowania – w większości języków wystarczy zwrócić znak przekonwertowany do typu całkowitoliczbowego). Jeżeli znak na pozycji o mniejszym indeksie ma większy kod ASCII, zamieniamy elementy i ustawiamy wartość zmiennej zamiana na: prawda.

sortowanie(napis)
	n ← długość(napis)
	dla i = 0, 1, 2, ... n - 2 wykonuj:
		zamiana ← fałsz

		dla j = 1, 2, ..., n - i - 1 wykonuj:
			jeżeli ascii(napis[j - 1]) > ascii(napis[j]):
				zamień napis[j - 1] z napis[j]
				zamiana ← prawda

Jeżeli w serii porównań w wewnętrznej pętli nie wystąpiła zamiana (wartość zmiennej zamiana jest równa fałsz), to oznacza, że elementy są już posortowane i można przerwać działanie pętli. Po zakończeniu sortowania zwracamy uporządkowaną kopię napisu:

sortowanie(napis)
	n ← długość(napis)
	dla i = 0, 1, 2, ... n - 2 wykonuj:
		zamiana ← fałsz

		dla j = 1, 2, ..., n - i - 1 wykonuj:
			jeżeli ascii(napis[j - 1]) > ascii(napis[j]):
				zamień napis[j - 1] z napis[j]
				zamiana ← prawda
		jeżeli zamiana = fałsz:
			przerwij pętlę
	zwróć napis

Odpowiedź dla danych z pliku napisy.txt

Słownik