Witajcie drodzy czytelnicy 🙂 Kontynuujemy temat matur. Tym razem zajmiemy się zadaniem „Piksele” sprzed dwóch lat. Pamiętam je dobrze gdyż właśnie w 2017 r. sam zdawałem maturę z informatyki. Jest to jeden z egzaminów, który wspominam najlepiej. Jedynie fizyka z (przedmiotów rozszerzonych) pozwoliła mi na osiągnięcie równie dobrego wyniku. Gotowi? No to zaczynamy 🙂 Rozwiążmy zadanie piksele z matury 2017 🙂
Arkusz możesz zobaczyć w tym miejscu. Natomiast zasady oceniania dostępne są tutaj.
Zadanie 6. Piksele
W pliku dane.txt znajduje się 200 wierszy. Każdy wiersz zawiera 320 liczb naturalnych z przedziału od 0 do 255, oddzielonych znakami pojedynczego odstępu (spacjami). Przedstawiają one jasności kolejnych pikseli czarno-białego obrazu o wymiarach 320 na 200 pikseli (od 0 – czarny do 255 – biały).
Napisz program(y) który(e) da(dzą) odpowiedzi do poniższych zadań. Odpowiedzi zapisz w pliku wyniki6.txt, a każdą odpowiedź poprzedź numerkiem oznaczającym odpowiednie zadanie.
Uwaga: plik przykład.txt zawiera dane przykładowe spełniające warunki zadania (obraz ma takie same rozmiary). Odpowiedzi dla danych z pliku przykład.txt podane są pod poleceniami.
Kod wspólny dla wszystkich zadań
Częścią wspólną dla każdego zadania będzie odczyt z pliku. Informacje powinniśmy przechowywać w tablicy dwuwymiarowej, o rozmiarach 200 na 320, przechowującej liczby całkowite (int). W przeciwieństwie do rozwiązania użytego w poprzednim artykule serii, gdzie użyliśmy getline’a, tym razem użyjemy zwykłych strumieni.
1 2 3 4 5 6 7 8 9 10 11 12 | void readFile(string filename,int data[][320]) { fstream file; file.open(filename); if(!file.is_open()) { cout<<"Nie udało się otworzyć pliku przyklad.txt"<<endl; } for(unsigned int i = 0;i<200;i++) { for(unsigned int j = 0;j<320;j++) { file>>data[i][j]; } } } |
Zacznijmy od listy argumentów. Przekazujemy nazwę pliku, który chcemy otworzyć oraz int data[][320]. Co oznacza drugi argument? Właśnie w taki sposób przekazujemy tablicę dwuwymiarową do funkcji. Możemy (ale nie musimy) pominąć jeden wymiar tablicy.
Ale dlaczego przekazujemy tablicę jako argument? Przecież funkcja readFile ma stworzyć tę tablicę i wypełnić ją liczbami z pliku. Nie prościej byłoby utworzyć ją jako zmienną lokalną a następnie zwrócić za pomocą return (modyfikując wcześniej odpowiednio sygnaturę funkcji)? Otóż, takie coś by nie zadziałało. Dlaczego? Staroświecka tablica w stylu C jest po prostu wskaźnikiem na pierwszy element tej tablicy. Zwracając ją zwracalibyśmy wskaźnik na jej pierwszy element. Natomiast treść zostałaby wykasowana wraz z zakończeniem działania funkcji. Dlatego musimy przekazać tablicę jako argument funkcji. Czy zmiany w tablicy będą widoczne na zewnątrz funkcji? Tak, gdyż przekazujemy ją niejako „przez wskaźnik”. Zmiany dokonywane są na oryginale a nie na kopii danych.
Wiersze 2-6 to standardowa obsługa operacji otworzenia pliku. Próbujemy otworzyć plik za pomocą metody open. Następnie sprawdzamy, czy ta niezbędna dla maturzysty operacja powiodła się czy nie. Sprawdzenia nie musimy wykonywać. Niemniej, dobrym zwyczajem jest zabezpieczanie się przed każdą kryzysową sytuacją. Ułatwia to rozwiązywanie błędów w sytuacji, kiedy aplikacja nie działa tak jak byśmy tego chcieli.
Założenia postawione przez twórcę zadania mocno upraszczają operację właściwego odczytu informacji z pliku. Istnieje 200 wierszy, a każdy z nich zawiera 320 liczb (w dalszej części tekstu będziemy je nazywali kolumnami) W celu odczytania danych wykorzystujemy dwie pętle for. Pętla zewnętrzna przechodzi po wierszach, natomiast wewnętrzna po kolumnach. Do odczytywania kolejnych liczb najprościej wykorzystać strumień, który odwala za nas całą brudną robotę związaną z konwersją odczytanej z pliku danej na odpowiedni rodzaj zmiennej.
Zadanie 6.1 (0-2)
Podaj jasność najjaśniejszego i jasność najciemniejszego piksela.
Dla danych z pliku przykład.txt wynikiem jest 255 (najjaśniejszy) i 0 (najciemniejszy).
Rozwiązanie
Najprostsze rozwiązanie to po prostu znalezienie minimum i maksimum spośród wszystkich pikseli.
22 23 24 25 26 27 28 29 30 | int findMinPixel(int data[200][320]) { int min = 256; for(int i = 0;i<200;i++) { for(int j = 0;j<320;j++) { if(min>data[i][j]) min=data[i][j]; } } return min; } |
Funkcja przedstawiona na powyższym listingu znajduje najmniejszą wartość piksela. Na początku widzimy zmienną min. Jaką ona ma rolę? Będziemy w niej przechowywać najmniejszy znaleziony element. Aby algorytm działał prawidłowo, zmienna min musi mieć na początku wartość większą od jakiejkolwiek wartości która pojawi się w przeszukiwanych danych. W linijkach 24 i 25 widzimy dwie pętle for. Jest to standardowe podejście służące do przeszukiwania tablicy dwuwymiarowej. Najważniejszą częścią algorytmu jest linijka 26. Sprawdzamy, czy aktualna wartość jest większa od minimalnej. Jeśli tak, to ustawiamy nowe minimum. Na samym końcu zwracamy to minimum z funkcji.
Funkcja służąca do wyszukiwania maksimum będzie wyglądała analogicznie. Pełne rozwiązanie znajduje się poniżej. Możesz je rozwinąć, klikając odpowiedni przycisk.
Zadanie 6.1 - pełne rozwiązanieZadanie 6.2 (0-2)
Podaj, ile wynosi najmniejsza liczba wierszy, które należy usunąć, żeby obraz miał pionową oś symetrii. Obraz ma pionową oś symetrii, jeśli w każdym wierszu i-ty piksel od lewej strony przyjmuje tę samą wartość, co i-ty piksel od prawej strony, dla dowolnego 1<=i<=320.
Dla danych z pliku przykład.txt wynikiem jest 3.
Rozwiązanie
32 33 34 35 36 37 38 39 | int makeSimmetrical(int data[][320]) { int minRowsToRemove = 0; for(int i = 0;i<200;i++) { bool isRowSym = isRowSymmetrical(data[i]); if(!isRowSym) minRowsToRemove++; } return minRowsToRemove; } |
Funkcją odpowiadającą za rozwiązanie zadania jest makeSimmetrical. Przyjmujemy tylko jeden argument – tablicę dwuwymiarową zawierającą piksele. W zmiennej lokalnej minRowsToRemove przechowujemy ilość wierszy, które musimy usunąć, aby obraz był symetryczny. Na początku wartość ta wynosi oczywiście zero.
W pętli for przechodzimy cały obraz po wierszach. Dla każdego wiersza wywołujemy funkcję isRowSymmetrical, która sprawdza czy wiersz jest symetryczny wg algorytmu, który omówiliśmy na samym początku. Jeśli wiersz nie jest symetryczny to powinniśmy go usunąć.
22 23 24 25 26 27 28 29 30 31 | bool isRowSymmetrical(int data[]) { int i = 159; int j = 160; while(i!=0 && j!=320) { if(data[i]!=data[j]) return false; i--; j++; } return true; } |
Pomysł na napisanie funkcji isRowSymmetrical został podany w poleceniu. Musimy sprawdzać kolejne liczby. Zaczynając od środka, idziemy jednocześnie do lewej i prawej krawędzi. Tu kryje się pułapka, na której można polec i łatwo stracić 2pkt. Jak wyznaczyć środek? Mamy parzystą ilość liczb – 320. Jest to trudniejszy przypadek. Środek będą stanowiły dwie liczby. Jak znaleźć je w najprostszy sposób? Oczywiście – średnią arytmetyczną.
Ale zaraz, daje nam ona wynik: (0+319)/2=159.5. Jak wyznaczyć środkowe elementy? Będą to dwie liczby: element na który wskazuje średnia (bez części ułamkowej) oraz kolejny. Czyli podsumowując, środkiem naszego wiersza będą piksele kryjące się pod indeksami 159 i 160.
Zajmijmy się teraz algorytmem. Zawarty jest on w linijkach 25-29. Jeśli elementy po lewej i prawej stronie tablicy są różne, to znaczy że wiersz nie jest symetryczny. W takim wypadku przerywamy pętlę i zwracamy fałsz. Jeśli wszystko nam się zgadza kontynuujemy pętlę i sprawdzamy kolejne elementy. Robimy tak aż do momentu, gdy dotrzemy z jednej strony do początku, a z drugiej do końca wiersza.
Warty zauważenia jest fakt, że dla przykładowych danych i nieprawidłowych początkowych wartości i i j program może zwrócić prawidłowy wynik. Sprawdź np.: jak zachowa się aplikacja kiedy podasz i=158 i j=159. Dlatego uważam to zadanie za mocno podchwytliwe.
Zadanie 6.2 - pełne rozwiązanieZadanie 6.3 (0-3)
Sąsiednie piksele to takie, które leżą obok siebie w tym samym wierszu lub w tej samej kolumnie. Dwa sąsiednie piksele nazywamy kontrastującymi, jeśli ich wartości różnią się o więcej niż 128. Podaj liczbę wszystkich takich pikseli, dla których istnieje przynajmniej jeden kontrastujący z nim sąsiedni piksel.
Dla danych z pliku przyklad.txt wynikiem jest 5.
Rozwiązanie
Na samym początku napiszmy sobie króciutką funkcję porównującą dwa piksele.
22 23 24 25 | bool isPixelContrasting(int pixel1,int pixel2) { if(abs(pixel1-pixel2)>128) return true; else return false; } |
Prawda, że nie ma tutaj nic trudnego? Funkcja isPixelContrasting zwraca true, jeśli piksele kontrastują ze sobą (zgodnie z treścią zadania) lub false w przeciwnym wypadku. Dlaczego użyliśmy abs? Ponieważ musimy sobie w jakiś sposób poradzić z ujemnymi wartościami. Nie wiemy, czy będziemy odejmowali mniejszy piksel od większego, czy na odwrót. Dla nas ważna jest tylko i wyłącznie różnica między wartościami dwóch różnych liczb. Funkcja abs, która wyciąga wartość bezwzględną sprawdzi się w tym miejscu idealnie.
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | int countContrastingPixels(int data[][320]) { int contrastingPixels = 0; for(int i = 0;i<200;i++) { for(int j = 0;j<320;j++) { if(i>0 && isPixelContrasting(data[i-1][j],data[i][j])) { contrastingPixels++; } else if(i<199 && isPixelContrasting(data[i+1][j],data[i][j])) { contrastingPixels++; } else if(j>0 && isPixelContrasting(data[i][j-1],data[i][j])) { contrastingPixels++; } else if(j<319 && isPixelContrasting(data[i][j+1],data[i][j])) { contrastingPixels++; } } } return contrastingPixels; } |
Funkcja znajdująca się na listingu powyżej realizuje kluczową treść zadania. Podobnie jak w poprzednim wyzwaniu, także i tutaj znajduje się jeden kruczek. Mianowicie: musimy pamiętać o przypadkach brzegowych. Piksel kontrastujący może znajdować się powyżej, poniżej, na lewo lub nad prawo od aktualnie analizowanego. Jednakże, co w sytuacji, kiedy analizujemy na przykład ten znajdujący się na pozycji [0,0]? Wtedy nie możemy sprawdzać co jest powyżej, gdyż po prostu nic tam nie ma. W ten sposób da się jedynie doprowadzić jedynie do powstania błędnego wyniku. Za sprawdzanie przypadków brzegowych odpowiadają cztery ify, znajdujące się w linijkach 30,33,36 i 39.
Powstaje pytanie, czy nie jest błędem, że w tym samym ifie sprawdzamy czy współrzędna ma odpowiednią wartość oraz (jednocześnie) czy piksel nie jest kontrastujący? Oczywiście, że nie! Dzieje się tak dlatego, gdyż aplikacja nie sprawdza drugiego warunku, jeśli pierwszy nie został spełniony. Takie są zasady działania operatora AND (&&) w C/C++. Upraszcza to nieco kod programu.
Jeśli współrzędne są odpowiednie oraz piksel jest kontrastujący, to po prostu zwiększamy ilość kontrastujących pikseli o 1. Na samym końcu zwracamy obliczoną ilość kontrastujących pikseli. Jest to jednocześnie nasza odpowiedź do zadania.
Na dobrą sprawę moglibyśmy te wszystkie cztery ify skrócić do jednego. Polecam przećwiczyć i ulepszyć ten program w ten sposób 🙂
Zadanie 6.3 - kompletne rozwiązanieZadanie 6.4 (0-4)
Podaj długość najdłuższej linii pionowej (czyli ciągu kolejnych pikseli w tej samej kolumnie obrazka), złożonej z pikseli tej samej jasności.
Dla danych z pliku przyklad.txt wynikiem jest 198.
Rozwiązanie
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | int findLongestLine(int data[][320]) { int longestLine = 1; for(int i = 0;i<320;i++) { int longestInColumn = 1; int actLongestInColumn = 1; for(int j = 1;j<200;j++) { if(data[j][i]==data[j-1][i]) actLongestInColumn++; else { if(longestInColumn<actLongestInColumn) { longestInColumn = actLongestInColumn; } actLongestInColumn = 1; } } if(longestLine<longestInColumn) { longestLine = longestInColumn; longestInColumn = 1; } } return longestLine; } |
Jest to zdecydowanie najdłuższa z funkcji, które do tej pory omawialiśmy. I jednocześnie jest najbardziej skomplikowana. Co tutaj w ogóle się dzieje?
Naszym celem jest znalezienie najdłuższych linii pionowych. Sugeruje to, że musimy przeszukiwać obrazek w inny sposób niż robiliśmy to dotychczas. W poprzednich zadaniach pierwsza, zewnętrzna pętla for iterowała po wierszach, a wewnętrzna po kolumnach. W wypadku tego zadania taki sposób byłby niepoprawny. Musimy znajdować najdłuższe ciągi pikseli o tych samych jasnościach w liniach pionowych, co wymusza przechodzenie najpierw po kolumnach. Dla każdej kolumny przechodzimy cały obrazek od góry do dołu, szukając ciągów spełniających warunki naszego zadania.
Zmienna longestLine przechowuje najdłuższy ciąg pikseli o tej samej jasności znaleziony do tej pory. Wewnętrzna pętla for iterująca po wierszach ma dwie pomocnicze zmienne. longestInColumn oraz actLongestInColumn. Pierwsza pełni zadanie podobne do longestLine. Przechowuje najdłuższy do tej pory znaleziony ciąg w kolumnie. actLongestInColumn wykorzystywane jest natomiast do znalezienia nowego, lepszego, dłuższego ciągu.
26 27 28 29 30 31 32 33 34 35 36 | ... for(int j = 1;j<200;j++) { if(data[j][i]==data[j-1][i]) actLongestInColumn++; else { if(longestInColumn<actLongestInColumn) { longestInColumn = actLongestInColumn; } actLongestInColumn = 1; } } ... |
Skupmy się na pętli przechodzącej obrazek z góry na dół. Spójrz na pierwszego ifa. Porównujemy aktualny piksel z tym znajdującym się jedno oczko wyżej. Wyjaśnia to, dlaczego inicjujemy zmienną j na 1 w pętli. Gdyby j było równe zero, program działałby źle dla pierwszego piksela. Pierwszy piksel leżący na współrzędnych [0][i] byłby porównywany z tym który znajduje się na pozycji [-1][i] – takie porównanie musiałoby skończyć się strasznie.
Jeśli if jest prawdziwy, to znaczy że musimy zwiększyć długość ciągu o 1. Jeśli warunek nie jest spełniony, sprawdzamy czy aktualnie analizowany ciąg jest większy od znalezionego do tej pory. Jeśli tak, to nowy ciąg staje się najdłuższym ciągiem w kolumnie. Pamiętajmy o tym, że bez względu na wszystko musimy wyjedynkować zmienną actLongestInColumn.
29 30 31 32 33 34 35 36 37 38 39 40 41 | ... for(int i = 0;i<320;i++) { int longestInColumn = 1; int actLongestInColumn = 1; for(int j = 1; j<200;j++) { ... } if(longestLine<longestInColumn) { longestLine = longestInColumn; longestInColumn = 1; } } .... |
Skończyliśmy analizowanie pojedynczej linii pionowej. Teraz musimy sprawdzić, czy najdłuższy ciąg pikseli w tej obecnie analizowanej linii jest większy od tego znalezionego do tej pory w wyniku analizy poprzednich linii pionowych. Analogicznie do algorytmu wyszukiwania maksimum zastosowanego w zadaniu 6.1 – jeśli tak, to nowa długość staje się nową największą. Jeśli nie – no cóż, jeśli tylko się da to musimy szukać dalej 🙂
W momencie gdy przeszukamy cały obraz zmienna longestLine przechowuje wynik naszych obliczeń, który zwracamy z funkcji.
Zadanie 6.4 - pełne rozwiązanieZadanie 6.4 – możliwe do popełnienia błędy
W tym zadaniu można popełnić kilka błędów, które mogą wypaczyć wynik.Przede wszystkim zwróćmy uwagę na jedną rzecz: Zmienne obliczające najdłuższy ciąg mają domyślnie wartość 1. Dlaczego? Ponieważ samotny piksel o pewnej jasności, otoczony takimi o innej jasności nadal jest pojedynczym pikselem. Nadal jest ciągiem pikseli o tej samej jasności, tyle że o długości 1.
Jest jeszcze inny chochlik, który mógł wkraść się w nasz kod – zapomnienie o tym, że w jednej linii pionowej może być kilka ciągów pikseli o tej samej jasności. Jeśli przerywalibyśmy wyszukiwanie po znalezieniu pierwszego takiego ciągu, wynik byłby nie poprawny i tracilibyśmy 4 pkt za „prawie” dobre (czyli złe – haha) rozwiązanie.
Skończyliśmy
Omówiliśmy zadanie z programowania z matury Anno Domini 2017. Mam nadzieję, że pomoże to tobie, drogi czytelniku, w lepszym przygotowaniu się do egzaminu dojrzałości z tego przedmiotu 🙂
Jeśli masz jakieś uwagi lub komentarze, pisz 🙂 Przyjmę każdą opinię, jeśli tylko jest ona merytoryczna.
Do zobaczenia i powodzenia 🙂