Zadanie 1. Anagramy

AnagramanagramAnagram to słowo utworzone z innego słowa poprzez przestawienie kolejności liter. Przez słowo rozumiemy tu dowolny ciąg liter alfabetu łacińskiego.

Przykłady anagramów:

• dla słowa barok – korba, robak, arobk, rokab, orkab...

• dla słowa ranty – tyran, narty, ntyra, natyr, ytnar...

Plik tekstowy anagram.txt zawiera 200 wierszy. W każdym wierszu znajduje się po pięć słów o długości od 1 do 20 znaków. Słowa oddzielone są znakiem spacji.

Napisz program, który w pliku anagram.txt wyszuka wszystkie wiersze, w których wszystkie słowa są anagramami pierwszego słowa w danym wierszu, i zapisze je do pliku znalezione.txt.

Do oceny oddajesz:

• plik znalezione.txt z odpowiedzią (plik tekstowy zawierający wiersze z pliku anagramy.txt, w których wszystkie słowa są anagramami pierwszego słowa z danego wiersza)

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

Rozwiązanie

Sprawdzenie, czy wyrazy są anagramami, możemy wykonać przez posortowanie znaków łańcuchów w kolejności alfabetycznej i porównanie wyników — jeżeli będą one takie same, to znaczy, że są anagramami.

Zaczniemy od napisania funkcji sortującej, której użyjemy w głównej części kodu. Przyjmie ona jeden argument będący łańcuchem znaków — czyli słowem, które chcemy posortować. Znaki w łańcuchach, podobnie jak tablice, indeksujemy od zera, tak jak jest to reprezentowane w komputerze. W programie skorzystamy z sortowania przez wybieranie.

funkcja sortowanie(wyraz)

Na początku zadeklarujemy zmienną n, która przyjmie wartość długości sortowanego ciągu znaków. Wartość tę pobierzemy za pomocą funkcji długość(), której implementacja dostępna jest w każdym języku programowania, jaki możemy wybrać na egzaminie maturalnym.

Następnie zapisujemy pętlę, która przeiteruje po wszystkich znakach słowa wyraz.

funkcja sortowanie(wyraz)
	n ← długość(wyraz)
    
	dla i = 0, 1, ..., n - 1 wykonuj:

Zainicjujemy teraz zmienną indeks, w której będziemy przechowywać indeks najmniejszego znaku z nieposortowanej części ciągu znaków. Nadamy jej wartość i.

Następnie zastosujemy kolejną pętlę, w której przeiterujemy po wartościach od i + 1 do n - 1. W tej pętli będziemy szukać indeksu najmniejszego znaku z nieposortowanej części tablicy.

funkcja sortowanie(wyraz)
	n ← długość(wyraz)
    
	dla i = 0, 1, ..., n - 1 wykonuj:
		indeks ← i
		dla j = i + 1, i + 2, ..., n - 1 wykonuj:

Wewnątrz funkcji porównujemy znaki pod indeksami j oraz indeks. W celu porównywania znaków użyjemy funkcji ascii() zwracającej liczbę odpowiadającą danemu znakowi w kodzie ASCII. Funkcja jest możliwa do zaimplementowania w każdym języku dostępnym na egzaminie maturalnym.

funkcja sortowanie(wyraz)
	n ← długość(wyraz)
    
	dla i = 0, 1, ..., n - 1 wykonuj:
		indeks ← i
		dla j = i + 1, i + 2, ..., n - 1 wykonuj:
			jeżeli ascii(wyraz[j]) < ascii(wyraz[indeks]):

Jeżeli znak pod indeksem j jest mniejszy od znaku o indeksie indeks, wówczas zmiennej indeks przypisujemy wartość j.

Po zakończeniu wewnętrznej pętli zamienimy znak wyraz[i] ze znakiem o najmniejszej wartości kodu ASCII z nieposortowanego ciągu znaków, czyli ze znakiem wyraz[indeks].

funkcja sortowanie(wyraz)
	n ← długość(wyraz)
    
	dla i = 0, 1, ..., n - 1 wykonuj:
		indeks ← i
		dla j = i + 1, i + 2, ..., n - 1 wykonuj:
			jeżeli ascii(wyraz[j]) < ascii(wyraz[indeks]):
				indeks ← j
        zamień wyraz[i] z wyraz[indeks]

Po wykonaniu się pętli zewnętrznej funkcja zwróci posortowany łańcuch znaków wyraz.

funkcja sortowanie(wyraz)
	n ← długość(wyraz)
    
	dla i = 0, 1, ..., n - 1 wykonuj:
		indeks ← i
		dla j = i + 1, i + 2, ..., n - 1 wykonuj:
			jeżeli ascii(wyraz[j]) < ascii(wyraz[indeks]):
				indeks ← j
        zamień wyraz[i] z wyraz[indeks]
	zwróć wyraz

Przejdźmy teraz do właściwej części rozwiązania. Zaczynamy od wczytania danych z pliku.

słowa[0...199][0...4] ← wczytaj dane z pliku "anagramy.txt"

Następnie tworzymy pętlę, która przejdzie po wszystkich wierszach. Wewnątrz deklarujemy zmienną anagram, która będzie przechowywać informację, czy wszystkie słowa z wiersza są anagramami. Ustawiamy jej wartość na prawdę. Deklarujemy również zmienną pierwsze przechowującą posortowane pierwsze słowo z wiersza.

słowa[0...199][0...4] ← wczytaj dane z pliku "anagramy.txt"

dla i = 0, 1, ..., 199 wykonuj
	anagram ← prawda
	pierwsze ← sortowanie(słowa[i][0])

W kolejnej pętli przechodzimy po wszystkich słowach z wiersza oprócz pierwszego. Jeżeli wynik sortowania danego słowa będzie różny od zmiennej pierwsze, oznacza to, że w wierszu tym na pewno nie występują same anagramy, więc ustawiamy wartość zmiennej anagram na fałsz i przerywamy pętlę.

słowa[0...199][0...4] ← wczytaj dane z pliku "anagramy.txt"

dla i = 0, 1, ..., 199 wykonuj:
	anagram ← prawda
	pierwsze ← sortowanie(słowa[i][0])

	dla j = 1, 2, ..., 4 wykonuj:
		jeżeli sortowanie(słowa[i][j]) != pierwsze:
			anagram ← fałsz
			przerwij pętlę

Po zakończeniu wewnętrznej pętli sprawdzamy wartość zmiennej anagram. Jeśli jest ona równa prawdzie, przepisujemy cały analizowany wiersz do pliku wynikowego.

słowa[0...199][0...4] ← wczytaj dane z pliku "anagramy.txt"

dla i = 0, 1, ..., 199 wykonuj:
	anagram ← prawda
	pierwsze ← sortowanie(słowa[i][0])
	dla j = 1, 2, ..., 4 wykonuj:
		jeżeli sortowanie(słowa[i][j]) != pierwsze:
			anagram ← fałsz
			przerwij pętlę
	jeżeli anagram = prawda:
		dopisz słowa[i] do pliku "znalezione".txt

Schemat oceniania

• 6 pkt – za poprawną zawartość pliku znalezione.txt zawierającego wszystkie wiersze z anagramami

• 2 pkt – za zawartość pliku znalezione.txt z jednym błędem (błędny jeden wiersz lub brak jednego wiersza)

• 0 pkt – za zawartość pliku znalezione.txt z dwoma błędami lub więcej albo brak odpowiedzi

Odpowiedź

Opowiedź do zadania dla danych z pliku anagramy.txt znajduje się w pliku znalezione.txt:

Słownik