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膮zanie

Zadanie 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膮zanie

Zadanie 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膮zanie

Zadanie 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膮zanie

Zadanie 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 馃檪

Dodaj komentarz

Tw贸j adres email nie zostanie opublikowany. Pola, kt贸rych wype艂nienie jest wymagane, s膮 oznaczone symbolem *