Skip to content

[C++] Zadanie – Anagram

Posted in Nauka, and Programowanie

Dziś postanowiłem się podzielić z wami jednym z moich rozwiązań odnośnie zadania maturalnego z informatyki, zakres rozszerzony.

Ktoś kiedyś powiedział, że aby zaliczyć z wysokim wynikiem maturę z informatyki rozszerzonej potrzeba posiadać umiejętności posługiwania się sortowaniem bąbelkowym jak i znać się operacjach związanych ze zmianą zawartości plików .txt oraz wczytywaniem z nich informacji.

To prawda – warto też znać zasadę działania tablic, bo coś trzeba w końcu sortować. Do tego jednak musimy jeszcze dołożyć nasz pomysł na rozwiązanie zadania, choć i tak wiele już nam mówią w treści polecenia.
Dzisiejsza lektura będzie dotyczyć zadania pod tytułem „Anagram”.

Anagram to słowo powstałe z innego słowa przez przestawienie liter. Przez słowo rozumiemy
w tym zadaniu dowolny ciąg liter alfabetu łacińskiego.
W pliku tekstowym anagram.txt znajduje się 200 wierszy zawierających po 5 słów
w każdym wierszu. Słowa oddzielone są znakiem odstępu. Długość każdego ze słów wynosi
od 1 do 20 znaków.
Napisz program w wybranym przez siebie języku programowania, za pomocą którego
wykonasz poniższe polecenia:
a) Wyszukaj w pliku anagram.txt te wiersze, w których wszystkie słowa znajdujące się
w danym wierszu mają taką samą liczbę znaków. Zapisz te wiersze w pliku
odp_4a.txt.
b) Wyszukaj w pliku anagram.txt wszystkie wiersze tekstu, w których wszystkie słowa
są anagramami pierwszego słowa w danym wierszu. Zapisz te wiersze w pliku
odp_4b.txt.

Dane do zadania : pobierz plik anagram.txt .

Zadanie 4a – rozwiązanie

Tu mamy intuicyjnie proste – nie musimy praktycznie zwracać uwagi co za znaki są w wierszach. Po prostu liczymy każdy wyraz osobno.

Biblioteki, które się przydadzą:

fstream – operacje na plikach zewnętrznych
iostream – podstawowa biblioteka
string – biblioteka, która ułatwi nam znacznie operacje na wyrazach
cstdlib – przyda się przy kompilacji całego programu

Po zadeklarowaniu tych 4 bibliotek musimy wykonać kilka rutynowych czynności

utworzymy klasę typu fstream, aby wczytywanie danych i zapisywanie nowych można było robić za pomocą strumieni „<<” i „>>” .
zbierzemy wszystkie wyrazy z każdego wiersza i porównamy, czy wiersze są prawidłowe.

Tak w teorii wydaje się do być proste. W praktyce też takie jest o ile dobrze znasz podstawy C++.
Tutaj wyjąłem gotowy kod ze źródła programu, który daje nam odpowiedzi do 4a i 4b. Komenatarzami zaznaczyłem to co poniżej Ci wyjaśnię, mam nadzieję, przejrzyście.

1. Tworzymy klasy typu fstream; dzięki temu mamy możliwość operacji na plikach za pomocą strumieni
2. Są to formuły, dzięki którym otwieramy pliki – w nawiasach jest podana nazwa nazwa pliku oraz parametry z biblioteki fstream na jakich zasadach ma być otwarty i na co przygotowany.

UWAGA – ten sposób zapisu pliku zadziała tylko wtedy, jeżeli plik, który chcesz wczytać znajduje się w tym samym katalogu co plik wykonywalny .exe. , np. plik anagram.txt i nasz program z rozwiązaniem.exe znajdują się na pulpicie.

Przy pliku anagram.txt ustawiliśmy tryby, że „plik musi istnieć wcześniej i chcemy z niego tylko czytać”.

Plik odp_4a.txt musimy sami utworzyć, więc nadaliśmy mu tryby, że „plik można samemu utworzyć, jeżeli takowy nie istniał, jeżeli istniał to stara treść jest zachowana, a kolejne informacje do niego dopisywane będą na końcu zawartości plik”.

3. Tworzymy 5 obiektów typu string, które odpowiednio nazwałem skrótowo wx, gdzie w to skrót od słowa wyraz, a x to liczba porządkowa : 1,2,3,4,5, … . Gdybyśmy zdecydowali się nie posługiwać tablicami z klasy string ( tak – wyrazy to tablice znaków, a string jest tablicą dynamiczną ) to musielibyśmy deklarować coś w stylu

tego typu konstrukcja jest dopuszczalna i operacje sortowania w drugiej części zadania będą przebiegać identycznie lecz jest jeden minus – te tablice mogą niepotrzebnie zajmować miejsce.

Zauważ, że gdy w wierszach trafi nam się np.: 5-znakowy wyraz to niepotrzebnie zadeklarowaliśmy sobie jeszcze 15 miejsc ( C-stringi posiadają jeszcze tzw. znak null kończący wyraz ),

4. Tu tworzymy pętlę, która sprawi, że przeszukamy całą zawartość pliku anagram.txt – dużym ułatwieniem było dla nas podanie ile jest tych wierszy.

Podczas jednego wykonania pętli pobieramy odpowiednio z jednego wiersza po jednym wyrazie i spacji za pomocą strumienia „>>” . Następnie sprawdzamy za pomocą prostego if’a ( patrz //5 ) i funkcji ze stringów size(), czy liczba znaków się zgadza. Jako, że wszystkie wyrazy muszą być tej samej długości najprostszą metodą będzie porównanie każdego wyrazu do pierwszego i zestawienie warunków w koniunkcji ” && „. Gdy w danym wierszu będą się zgadzać wszystkie wyrazy zapisujemy je w wierszu do naszego pliku odp_4a.txt, pamiętając o tym, by zostawić na końcu przejście do nowego wiersza.

Następnie wszystkie obiekty typu string czyścimy funkcją clear();

Tutaj dla dociekliwych konstrukcja funkcji size() i clear().

W przypadku posługiwania się obiektami typu string możemy stosować równolegle funkcję length(), ponieważ w tej klasie rozmiar i długość to to samo.

Gdy opuścimy już pętle pozostaje nam zamknięcie pliku, komendą .close() i formalne zakończenie programu formułą:

Przypominam – powyżej pokazałem Ci zawartość main() .

Zadanie 4b – rozwiązanie

Zadanie 4b wymaga od nas już znajomości sortowania – bez niego praktycznie nie ukończymy zadania nawet w 150 minut, które mamy na 3 zadania.

Sortowanie na jakie się zdecydujesz zależy wyłącznie od Ciebie – ja pokażę Ci tutaj skorzystanie z najprostszego sortowania – sortowania bąbelkowego.

Sortowanie bąbelkowe w skrócie.

Zasada działania sortowania jest bardzo prosta – porównujemy dwie informacje z tablicy obok siebie – jeżeli informacja stojąca bliżej ( dla przykładu t1 ) jest większe od tej stojącej po lewej stornie ( t2 ) to następuje przesunięcie informacji z t2 w miejsce t1 ( czyli w prawo ), a t1 wędruje na t2.

Wiem zaplątałem trochę tym tekstem, ale słownie jest to trochę trudne do zobrazowania – pokażę Ci zaraz sortowanie jedno z 5, które musisz utworzyć w programie i objaśnię krok po kroku jak to działa w ( mam nadzieję ) łatwiejszej, prostszej i bardziej przejrzystej formie.

Pierwsza tablica odpowiada za wymuszenie działania drugiej tablicy. Chodzi o to, by sortowania odbyło się n^2  razy. W ten sposób mamy 100% pewności, że posortowane zostaną wszystkie wyrazy.

Dalej mamy już if’a, który działa następująco:
– jeżeli liczba w1[j] jest większa od tej stojącej w w1[j+1] to zamień je miejscami.


By Swfung8Praca własna, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14953478Ten gif z wikipedii pokaże Ci jak to wygląda w praktyce.

No dobra ale Ty tu piszesz o liczbach i na gif’ie też są liczby – my tu mamy do posortowania litery.
Zgadza się lecz nie zapominajmy, że litery mają przypisane wartości liczbowe w kodzie ASII – pamiętasz ten program o tym jaka wartość kryje się pod znakami?

Teraz, kiedy posortowaliśmy wyrazy wystarczy je porównać za pomocą zwykłych operatorów logicznych i instrukcją if:

jeżeli powyższy przypadek zachodzi to zapiszemy te znaki posortowane do pliku.
Nie mam do końca pewności ale jeżeli egzaminator nie chciałby zobaczyć posortowanych znaków tylko oryginalne zapisy możemy się wyposażyć w pomocnicze kolejne stringi, które nam przechowają oryginały. Musimy wtedy pamiętać, aby w pętli je też wyczyścić.

Czas połączyć odpowiedzi w całość

Nie ma sensu tworzyć dwóch osobnych programów do tego zadania – dlatego też wręczam Ci w linku gotowy już kodu z odpowiedzią do dwóch zadań, aby zaoszczędzić tu pisania kodu.

Tutaj możesz zobaczyć gotowy, połączony plik.

 

Aktualizacja wpisu

Z początku maja, kiedy się wylegiwałem w Wołominie dostałem maila, w którym poproszono mnie o przedstawienie rozwiązania w związku z tym zadaniem, ponieważ moje wyniki tutaj są drukowane jako posortowane. Fakt nie doczytałem zadania i oto co zaproponowałem.

„Aby uniknąć wysyłania do pliku posortowanych wyrazów musimy pracować wewnątrz innej funkcji, która zwróci nam prawdę lub fałsz dla każdego wiersza. Z tym, że musimy pracować na tzw. „kopii tymczasowej”, aby nie naruszyć oryginalnej wartości zmiennych. „

Utworzymy funkcję Bool’owską, która sprawdzi po posortowaniu, czy dane słowa, to anagram, czy nie:

Z tego miejsca

Jeszcze raz wielkie dzięki, że takie, czy to wiadomości, czy w komentarzach napływają do mnie informacje. To buduje morale i daje informację, że komuś się mój wkład na coś przydał.

4 komentarze

  1. Witaj, program napisany przez Ciebie bardzo mi pomógł, ponieważ przygotowuję się do matury z informatyki. Liczę na więcej programów tego typu (i chciałabym wspomnieć o deklarowaniu "int" w pętlach for, przed zmiennymi i,j czy f).
    Dziękuję i pozdrawiam 🙂

    18 października 2015
    |Reply
    • Dzięki, będzie to uwzględnione – po prostu dawniej miałem wygodniej, gdy widziałem wszystkie zmienne wcześniej, zanim zabrałem się za pisanie kodu – najpierw szkic w głowie/na kartce dopiero przelanie na maszynę 🙂

      19 października 2015
      |Reply
  2. Anonimowy
    Anonimowy

    Bardzo przejrzyście i dokładnie wytłumaczone, wielkie dzięki 😉

    12 kwietnia 2016
    |Reply

Dodaj komentarz

%d bloggers like this: