Matura z informatyki 2018 – zadanie WEGA (C++)

Czas czytania: 4 minut

Postanowiłem, że obok wpisów na temat bardziej zaawansowanych zakamarków języka C++ postaram się przysłużyć co nieco maturzystom. A w związku z tym na blogu pojawi się niebawem seria wpisów, w których będziemy analizowali zadania maturalne z ubiegłych lat. Na pierwszy ogień pójdą polecenia wymagające programowania. Językiem, w którym będziemy kodowali rozwiązania będzie oczywiście C++. Jest to język prostszy, logiczniejszy i dający lepszą podstawę do nauki innych niż Python. Dlatego polecam właśnie C++ 🙂 No ale skończmy już te dyrdymały i przejdźmy do zadania na dziś 🙂

Arkusz dostępny jest tutaj. Odpowiedzi do niego natomiast: tutaj

Zadanie 4. WEGA – matura z informatyki 2018 CKE

W ramach projektu WEGA naukowcom udało się odczytać sygnały radiowe pochodzące z przestrzeni kosmicznej. Po wstępnej obróbce zapisali je do pliku sygnaly.txt

W pliku sygnaly.txt znajduje się 1000 wierszy. Każdy wiersz zawiera jedno niepuste słowo złożone z wielkich liter alfabetu angielskiego. Długość jednego słowa nie przekracza 100 znaków.

Napisz program(y) które dadzą odpowiedzi do poniższych zadań. Odpowiedzi zapisz w pliku wyniki4.txt, a każdą odpowiedź poprzedź numerem oznaczającym odpowiednie zadanie.

Uwaga:Plik przykład.txt zawiera dane przykładowe spełniające warunki zadania. Odpowiedzi dla danych z pliku przykład.txt są podane pod pytaniami.

Zadanie 4.1 (0-3)

Naukowcy zauważyli, że po złączeniu dziesiątych liter co czterdziestego słowa (zaczynając od słowa czterdziestego) otrzymamy pewne przesłanie. Wypisz to przesłanie.

Uwaga: Każde co czterdzieste słowo ma co najmniej 10 znaków.

Dla danych z pliku przykład.txt wynikiem jest: NIECHCIMATURALEKKABEDZIE

Rozwiązanie

Jest to dosyć proste zadanie. Najtrudniejszą częścią jest napisanie funkcji, która odczytuje prawidłowo dane z pliku. W kodzie powyżej odpowiada za to readFile. Dane przechowujemy w vectorze przechowującym stringi. Jest to najwygodniejsza metoda. W linijkach 11-16 otwieramy plik i sprawdzamy, czy udało nam się go właściwie otworzyć. Linijki 17-21 to clue funkcji readFile. Odczytujemy plik linia po linii. Pojedynczą linię tekstu przechowujemy w zmiennej tymczasowej line typu string. Gdy odczytamy linijkę tekstu, dodajemy ją na koniec vectora readen. Na samym końcu funkcji zwracamy ten vector.

W mainie realizujemy natomiast to, o co nas poprosili twórcy zadania. W pętli for przechodzimy co czterdzieste słowo. Iterator pętli – zmienna i wynosi na początku 39. Dlaczego? Ponieważ w treści zadania napisano, zaczynając od słowa 40.W informatyce wszystko numerujemy od zera. Czterdziestym słowem będzie więc te znajdujące się pod indeksem nr 39. Z tego samego powodu zwiększamy wartość zmiennej i za każdym razem o 40.

Co się dzieje wewnątrz pętli? Do zmiennej result typu string dodajemy dziesiątą literę tego słowa. (czyli tą znajdującą się pod indeksem nr 9).

I to by było na tyle. Odpowiedź do zadania znajduje się w zmiennej result. Możemy ją wyświetlić (tak jak w kodzie powyżej) lub zapisać do pliku. Robimy to, co jest dla nas wygodniejsze.

Może kolejne zadanie od CKE będzie nieco ambitniejsze? Zobaczmy 🙂

Zadanie 4.2 (0-4)

Znajdź słowo, w którym występuje największa liczba różnych liter. Wypisz to słowo i liczbę występujących w nim różnych liter. Jeśli słów o największej liczbie różnych liter jest więcej niż jedno, wypisz pierwsze z nich pojawiające się w pliku z danymi.

Dla danych z pliku przykład.txt wynikiem jest: AKLMNOPRSTWZA 12

Rozwiązanie

Jakie pułapki teraz zastawiła na nas CKE? Funkcji readFile nie omawiam, gdyż jest analogiczna jak w poprzednim zadaniu. Nic się nie zmieniło. 95% pracy wykonywane jest w ramach funkcji getTheMostDifferentWords. Zwraca ona parę, składającą się ze stringa (nasz ciąg znaków) oraz inta (liczba różniących się liter). Funkcja zaczyna się w linijce 35 definicją pary, w której będziemy przechowywali wynik.

W linijce 36 widzimy pętlę typu for-each. Przegląda ona linijka po linijce wszystkie pobrane wcześniej dane. Aktualnie analizowana linijka znajduje się w zmiennej word.

Linijka 37 to tablica zmiennych typu bool. Przechowujemy w niej informację o tym, czy dana litera wystąpiła w analizowanym słowie. Ważne w tym momencie jest to, że zmienne lokalne mają domyślne wartości losowe. Powinniśmy więc wyzerować tablicę, co robimy w kolejnym wierszu.

W następnych dwóch linijkach przechodzimy aktualnie analizowany wiersz tekstu, litera po literze. Każdą napotkaną literę oznaczamy jako używaną w tablicy exist. Możesz zadać pytanie, dlaczego odejmujemy 'A’? Ponieważ tekst, jak wiesz, przechowywany jest w komputerze w formie kodu ASCII. My natomiast potrzebujemy kodowania w formie A=0, B=1 … Z=25. Od kodu aktualnie analizowanej litery musimy więc odjąć literę A.

W linijce 42 wywołujemy funkcję calculateNumberOfDiffLetters. Jej definicja znajduje się w linijkach 27-33. Na czym polega ta funkcja? Po prostu zliczamy, ile elementów w tablicy exists ma wartość true. Jeśli ta wartość jest większa od aktualnej największej, przechowywanej w zmiennej theMostDifferent, to aktualizujemy wartości. W przeciwnym wypadku kończymy obieg pętli.

Co można powiedzieć o main? Nic specjalnego. Po prostu, wywołujemy wcześniej utworzone funkcje, a następnie wypisujemy na ekran wynik.

Zadanie 4.3. (0-4)

W tym zadaniu rozważmy odległość liter w alfabecie – np.: litery A i B są od siebie oddalone o 1, A i E o 4, F – D o 2, a każda litera od siebie samej oddalona jest o 0. Wypisz wszystkie słowa, w których każde dwie litery oddalone są od siebie w alfabecie co najwyżej o 10. Słowa wypisz w kolejności występowania w pliku sygnaly.txt, po jednym w wierszu.

Na przykład: CGECF jest takim słowem, ale ABEZA nie jest (odległość A-Z wynosi 25).

Tym razem za rozwiązanie naszego zadania odpowiada funkcja selectWordsDiffLessThan10. Przeanalizujmy ją 🙂

W linijce 29 stosujemy pętlę for-each. Przechodzimy vector przechowujący wszystkie odczytane z pliku słowa, przy czym aktualnie analizowane słowo znajduje się w zmiennej word.

W linijce 30 utworzyliśmy zmienną add typu bool. Za co ona odpowiada? Przechowujemy w niej informację o tym, czy dany wyraz spełnia warunki postawione przez CKE. Na samym początku przyjmujemy, że wyraz spełnia warunki. A potem szukamy argumentów za tym, aby tę hipotezę obalić 🙂

Linijka 31 i 32 to dwie pętle for. Dlaczego zastosowaliśmy akurat taką konstrukcję? Bo musimy przeanalizować każdą parę liter słowa. Pierwsza pętla przechodzi wszystkie litery słowa. Pierwsza pętla przechodzi cały wiersz, więc naszą granicą jest rozmiar słowa.

W drugiej pętli zaczynamy przechodzenie od i+1. Dlaczego? Moglibyśmy zaczynać od i=0. Program nadal generowałby prawidłową odpowiedź. Jednakże wtedy sprawdzamy pary liter, które już zostały zaakceptowane, co jest marnotrawieniem mocy procesora. Na przykład: skoro sprawdziliśmy, że litery znajdujące się na pozycjach 1 i 3 spełniają warunki zadania, to tak samo będą je spełniały litery znajdujące się na pozycjach 3 i 1 (gdyż to te same litery!). Skoro zaczynamy od i+1, to naszą granicą będzie rozmiar słowa-1. Dlaczego? Ponieważ w inny wypadku wyszlibyśmy poza zakres tablicy. (Rozważ przypadek, kiedy zewnętrzna pętla analizuje ostatnią literę słowa).

Linijka 33 clue rozwiązania problemu. Sprawdzamy, czy para liter spełnia warunek zadania. Wystarczy zwykłe odjęcie kodów liter. Możesz się zastanowić, po co funkcja abs? Z prostego powodu. Jeśli odejmiemy np.: Z od A, otrzymamy wynik dodatni. Lecz jeśli przeprowadzimy odejmowanie A-Z, wynik będzie miał przeciwny znak. Dla uproszczenia warunku lepiej zastosować funkcję abs, która wyciąga nam wartość bezwzględną z wyniku.

Linijki 34 i 39 – po znalezieniu pierwszego słowa niespełniającego warunku przerywamy pętlę. W linijce 41 dodajemy słowo do vectora wynikowego, oczywiście pod warunkiem, że spełnia warunek.

W funkcji main wywołujemy utworzone funkcje w odpowiedniej kolejności. Następnie wyprowadzamy wynik na ekran.

I to koniec

Rozwiązaliśmy zadanie SEGA z ubiegłorocznej (2018) matury. Zdobyliśmy 11 punktów. Prawda, że nie było źle? 🙂 Jeśli wpis ci się podobał, przeprowadzę podobną analizę zadań z programowania z ubiegłorocznych arkuszy. A następnie zaczniemy rozwiązywać zadania z Excela i baz danych.

Do zobaczenia 🙂 Życzę powodzenia na maturze 🙂

5 komentarzy do “Matura z informatyki 2018 – zadanie WEGA (C++)

  1. Dominik Szczepaniak Odpowiedz

    Trafiłem na to zadanie na maturze i wtedy potrafiłem rozwiązać jedynie pierwszą część. Fajnie tak powrócić do tego zadania po jakimś czasie i zobaczyć rozwiązanie…
    Dzięki za wpis! 🙂

  2. Dominik Odpowiedz

    Cześć!
    Przeglądam Twoje rozwiązania i nie mogę się zgodzić, że propozycja 4.3 jest poprawna.
    Wynik, który podaje Twoje rozwiązanie to 293. I nie jest ono poprawne. Przykładowo jako prawidłowy output Twój program podaje wyrazy:
    HLBW – Różnica między BW > 10
    ZA – Różnica między ZA > 10
    ABFQ – Różnica między AQ > 10
    ITP.
    Moim zdaniem, poprawnych wyników jest 66. Akceptowalna na 2pkt odpowiedź to 207 wyników. Ale nie jest to maks jaki można dostać za to zadanie.
    Hint: zerknij na zagnieżdżoną pętlę.

    P. S.
    Drobne uwagi.
    To nie są pętle for-each. Korzystasz z pętli range-based.
    Readen :). (trzecia forma, jeśli to chciałeś uzyskać, brzmi inaczej, tak wiem – działa)

    No i generalnie, wiem, że cke prawdopodobnie chce jednie poprawnego wyniku bez zważania na czas wykonywania i zużyte zasoby, ale podany przez Ciebie kod, jest piekielnie nieefektywny. For w forze w forze…aż prosi się o jakiś sensowny refaktor.

    Pzdr!

    • Karol Autor wpisuOdpowiedz

      Dzięki za uwagi 🙂 Masz rację, popełniłem błąd. Niebawem wstawię też bardziej optymalną wersję tego zadania 🙂

  3. Seoit Odpowiedz

    Bardzo fajny wpis i dokładny opis zadania. Mimo, że z C nie pracuję na co dzień to ta lektura pozwoliła mi trochę swoją wiedzę w tym temacie odświeżyć. Dzięki za ten artykuł. Pozdrawiam.

  4. Kuba Odpowiedz

    Ja próbuje zrozumieć i nadal mam błąd, Dominik mógłbyś rozwiać tajemniczą mgłę? Co jest nie poprawne w rozwiązaniu Karola? Proszę o pomoc i pozdrawiam!

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.