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.
fstream plik; // 1
fstream plikodp2;
plik.open("anagram.txt", ios::in); //2
plikodp2.open("odp_4a.txt", ios::out | ios::app);
string w1, w2, w3, w4, w5; //3
for(f=0; f<=200 ; f++ ) //4
{
plik >> w1;
plik >> w2;
plik >> w3;
plik >> w4;
plik >> w5;
if( (w1.size() == w2.size()) && (w1.size()== w3.size()) && (w1.size() == w4.size()) && (w1.size() == w5.size())) //5
{
plikodp2 << w1 << " " << w2 << " " << w3 << " " << w4 << " " << w5 << " " << endl;
}
w1.clear();
w2.clear();
w3.clear();
w4.clear();
w5.clear();
}
plik.close();
plikodp.close();
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
char wyraz1[20];
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().
const char*.size() const char*.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.
const char*.length()
Gdy opuścimy już pętle pozostaje nam zamknięcie pliku, komendą .close() i formalne zakończenie programu formułą:
system("PAUSE");
return 0;
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.
for (i=0; i<w1.size()-1; i++) for (j=0; j<w1.size()-1; j++) if (w1[j]>w1[j+1]) (w1[j], w1[j+1]);
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 Swfung8 – Praca 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:
if( w1 == w2 && w1 == w3 && w1 == w4 && w1 == w5)
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:
bool anagram(string z1, string z2, string z3, string z4, string z5)
{
// Zaczynamy sortowanie wyrazów ; aby sprawdzic wynik sortowania odblokuj strumienie wyjscia w komentarzach
for (int i=0; i<z1.size()-1; i++)
for (int j=0; j<z1.size()-1; j++)
if (z1[j]>z1[j+1])
swap(z1[j], z1[j+1]);
//cout << w1 << endl;
for (int i=0; i<z2.size()-1; i++)
for (int j=0; j<z2.size()-1; j++)
if (z2[j]>z2[j+1])
swap(z2[j], z2[j+1]);
//cout << w2 << endl;
for (int i=0; i<z3.size()-1; i++)
for (int j=0; j<z3.size()-1; j++)
if (z3[j]>z3[j+1])
swap(z3[j], z3[j+1]);
//cout << w3 << endl;
for (int i=0; i<z4.size()-1; i++)
for (int j=0; j<z4.size()-1; j++)
if (z4[j]>z4[j+1])
swap(z4[j], z4[j+1]);
//cout << w4 << endl;
for (int i=0; i<z5.size()-1; i++)
for (int j=0; j<z5.size()-1; j++)
if (z5[j]>z5[j+1])
swap(z5[j], z5[j+1]);
//cout << w5 << endl;
if( z1 == z2 && z1 == z3 && z1 == z4 && z1 == z5)
{
return true;
}
}
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ł.