Powtórzenie informacji o tablicach dwuwymiarowych

Tablice jednowymiarowe służą do przechowywania danych tego samego typu, takich jak liczby, napisy itd.

Tablice dwuwymiarowetablica dwuwymiarowaTablice dwuwymiarowe są w istocie tablicami jednowymiarowymi, których komórki zawierają inne tablice jednowymiarowe. Tablice dwuwymiarowe są zatem tablicami tablic jednowymiarowych.

Przykładem tablicy dwuwymiarowej jest tablica jednowymiarowa przechowująca trzy pomiary temperatur wykonane przez ostatnie 10 dni. Przykładowo, w języku C++ deklaracja takiej tablicy dwuwymiarowej może wyglądać następująco:

int temperatury[10][3];

Analogiczna deklaracja w języku Java:

int [][] temperatury = new int [10][];
for(int i = 0; i < 10; i++){
 	temperatury[i] = new int[3];
}

I deklaracja w języku Python:

temperatury = [[0 for x in range(3)] for y in range(10)]

W informatyce w postaci tablicy dwuwymiarowej bardzo często przedstawia się macierzemacierzmacierze, np.:

[1][7][3]
[0][2][5]
[4][9][7]
[5][8][3]

Zadanie 1. Piksele (11 pkt.)

Treść zadania

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ń.

Przygotowanie

Każde z zadań, które omówimy, wymaga wczytania danych z załączonego pliku. Dane będziemy umieszczać w tablicy przechowującej liczby całkowite składającej się z 200 wierszy. Każdy wiersz zbudowany będzie z 320 kolumn (zgodnie z definicją pliku zawartą w poleceniu).

Zaczynamy od zadeklarowania tablicy. Tablicę będziemy indeksować od 0. Każdą z jej komórek wypełniamy wartością 0.

piksele[200][320]  //deklaracja nowej tablicy liczb całkowitych

dla i = 0, 1, ... 199 wykonuj:
    dla j = 0, 1, ... 319 wykonuj:
        piksele[i][j] = 0

Następnie w trybie do odczytu otwieramy plik. Odczytujemy z niego kolejne wiersze, dzielimy tekst na pojedyncze liczby i uzupełniamy tablicę piksele zamienionymi na liczby całkowite wartościami.

piksele[200][320]  //deklaracja nowej tablicy liczb całkowitych

dla i = 0, 1, ... 199 wykonuj:
    dla j = 0, 1, ... 319 wykonuj:
        piksele[i][j] = 0

plik = otwórz plik "dane.txt"

dla numerWiersza = 0, 1, ... 199 wykonuj:
    wiersz = odczytaj z plik wiersz o numerze numerWiersza
    liczby = podziel wiersz na części rozdzielone przy pomocy znaku " " (spacji)
    dla numerKolumny = 0, 1, ... 319 wykonuj:
        piksele[numerWiersza][numerKolumny] = liczbaCałkowita(liczby[numerKolumny])

zamknij plik

Rozwiązując kolejne zadania, będziemy zakładali, że tablica piksele została uzupełniona danymi z pliku.

Zadanie 1.1

Podaj jasność najjaśniejszego i jasność najciemniejszego piksela.

Rozwiązanie

Zadanie polega na odnalezieniu w całej tablicy wartości największej i najmniejszej. Implementację rozwiązania zaczniemy od zadeklarowania dwóch zmiennych: min i max. Obie zainicjalizujemy wartością znajdującą się w tablicy piksele pod indeksem 0, 0.

min = max = piksele[0][0]

Tworzymy dwie zagnieżdżone pętle dla. Zadaniem pętli zewnętrznej będzie wskazywanie, który wiersz jest aktualnie przetwarzany, z kolei wewnętrzna wskazuje przetwarzaną kolumnę.

min = max = piksele[0][0]

dla wiersz = 0, 1, ... 199 wykonuj:
    dla kolumna = 0, 1, ... 319 wykonuj:

Wewnątrz pętli dodajemy dwie instrukcje warunkowe. Pierwsza będzie sprawdzać, czy wartość zmiennej min jest większa od wartości kryjącej się w piksele[wiersz][kolumna]. Jeżeli warunek zostanie spełniony, oznacza to, że znaleźliśmy nową najmniejszą wartość – zapisujemy ją do zmiennej min.

Druga instrukcja warunkowa porównuje wartość zapisaną w piksele[wiersz][kolumna] z wartością max. Jeżeli max jest mniejszy od piksele[wiersz][kolumna], wówczas zapisujemy do zmiennej max wartość pobraną z tablicy – jest to nowa wartość największa.

min = max = piksele[0][0]

dla wiersz = 0, 1, ... 199 wykonuj:
    dla kolumna = 0, 1, ... 319 wykonuj:
        jeżeli min > piksele[wiersz][kolumna] wykonaj:
            min = piksele[wiersz][kolumna]
        
        jeżeli max < piksele[wiersz][kolumna] wykonaj:
            max = piksele[wiersz][kolumna]
   

Po wykonaniu kodu zmienna min przechowuje wartość najmniejszą, z kolei max największą. Ostatnią operacją, jaką musimy wykonać, jest wydrukowanie wyniku.

min = max = piksele[0][0]

dla wiersz = 0, 1, ... 199 wykonuj:
    dla kolumna = 0, 1, ... 319 wykonuj:
        jeżeli min > piksele[wiersz][kolumna] wykonaj:
            min = piksele[wiersz][kolumna]
        
        jeżeli max < piksele[wiersz][kolumna] wykonaj:
            max = piksele[wiersz][kolumna]

wypisz "Najciemniejszy piksel: " + min
wypisz "Najjaśniejszy  piksel: " + max

Schemat oceniania:

Poprawna odpowiedź:

Wartość najjaśniejszego piksela 221.

Wartość najciemniejszego piksela 7.

Schemat punktowania:

• 2 pkt – za prawidłową odpowiedź, w tym 1 pkt za podanie wartości najjaśniejszego piksela i 1 pkt za podanie wartości najciemniejszego piksela.

• 0 pkt – za odpowiedź błędną albo za brak odpowiedzi.

Zadanie 1.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 \le i \le 320$.

Rozwiązanie

Zadanie można rozwiązać na wiele sposobów. W zaprezentowanym rozwiązaniu wykorzystamy fakt, że każda linia, która nie powinna zostać usunięta musi być palindromem. Aby rozwiązać zadanie będziemy porównywać i‑ty piksel z lewej strony z jego odpowiednikiem z prawej. Jeżeli którakolwiek z badanych par nie będzie identyczna oznacza to, że linia nie posiada pionowej osi symetrii – należy ją usunąć.

Zaczniemy od stworzenia i zainicjalizowania dwóch zmiennych. Pierwsza: ileUsunac będzie zliczać, ile wierszy należy zgodnie z poleceniem usunąć, aby obraz miał pionową oś symetrii. Druga zmienna: polowa posłuży nam do wskazania numeru kolumny, na której powinniśmy zakończyć sprawdzanie. Zapisujemy do niej wartość wynikającą z działania $320 : 2$ (liczba kolumn w wierszu dzielona przez dwa).

ileUsunac = 0

polowa = 320 / 2

Tworzymy dwie zagnieżdżone pętle dla. Pierwsza będzie wskazywać numer przetwarzanego wiersza, druga numer badanej kolumny. Zauważmy, że iterator wewnętrznej pętli kolumna będzie przyjmował wartości z zakresu <0, polowa).

ileUsunac = 0

polowa = 320 / 2

dla wiersz = 0, 1, ... 199 wykonuj:
    dla kolumna = 0, 1, ... polowa wykonuj:

Korzystając z instrukcji warunkowej, porównujemy dwie wartości: i‑tą z lewej strony (tę wartość odczytujemy z piksele[wiersz][kolumna]), z i‑tą z prawej strony (piksele[wiersz][320 - 1 - kolumna]). Jeżeli wartości są różne, wówczas zwiększamy wartość zmiennej ileUsunac oraz przerywamy wewnętrzną pętlę.

ileUsunac = 0

polowa = 320 / 2

dla wiersz = 0, 1, ... 199 wykonuj:
    dla kolumna = 0, 1, ... polowa wykonuj:
        jeżeli piksele[wiersz][kolumna] != piksele[wiersz][320 - 1 - kolumna] wykonaj:
            ileUsunac = ileUsunac + 1
            przerwij wewnętrzną pętlę

Poza pętlami drukujemy wynik – wartość zmiennej ileUsunac.

ileUsunac = 0

polowa = 320 / 2

dla wiersz = 0, 1, ... 199 wykonuj:
    dla kolumna = 0, 1, ... polowa wykonuj:
        jeżeli piksele[wiersz][kolumna] != piksele[wiersz][320 - 1 - kolumna] wykonaj:
            ileUsunac = ileUsunac + 1
            przerwij wewnętrzną pętlę

wypisz ileUsunac

Schemat oceniania:

Poprawna odpowiedź:

149

Schemat punktowania:

• 2 pkt – za prawidłową odpowiedź.

• 0 pkt – za odpowiedź błędną albo za brak odpowiedzi.

Uwaga: nie przyznaje się 1 pkt.

Słownik