Zadanie 1. 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ź numerem oznaczającym odpowiednie zadanie.

Uwaga: plik przyklad.txt zawiera dane przykładowe spełniające warunki zadania (obraz ma takie same rozmiary). Odpowiedzi dla danych z pliku przyklad.txt są podane pod poleceniami.

Plik przyklad.txt:

Plik dane.txt:

Zadanie 1.1

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

Dla danych z pliku przyklad.txt wynikiem jest 255 (najjaśniejszy) i 0 (najciemniejszy).

Do oceny oddajesz:

• plik wyniki6.txt zawierający odpowiedź (numer zadania, wartości najjaśniejszego i najciemniejszego piksela, zapisane w osobnych liniach),

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie

Zaczniemy od wczytania danych z pliku do tablicy dwuwymiarowej dane[200][320] (C++, Java) lub listy list (Python).

W języku Java dane z pliku czytamy wiersz po wierszu, liczby z każdego odczytanego wiersza otrzymujemy w postaci tablicy lub listy zwracanej za pomocą funkcji split(), która dzieli podany ciąg znaków za pomocą podanego separatora.

W języku Java możemy skorzystać z klasy Scanner lub klasy BufferedReader, która buforuje odczytywane dane i jest wydajniejsza, kiedy plik odczytujemy wiersz po wierszu.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        // 2-wymiarowa tablica
        int[][] dane = new int[200][320];
        BufferedReader plik = new BufferedReader(new FileReader("dane.txt"));
        String wiersz;
    
        for (int i = 0; i < 200; i++) {
            wiersz = plik.readLine();
            String[] liczby = wiersz.split(" ");
            for (int j = 0; j < 320; j++)
                // odczytywanie liczb z wiersza
                dane[i][j] = Integer.parseInt(liczby[j]);
        }
        plik.close();
    
        // wypisanie odczytanych liczb
        for (int i = 0; i < 200; i++) {
            for (int j = 0; j < 320; j++)
                System.out.print(dane[i][j] + " ");
            System.out.println(" ");
        }
    
    }

}

Znalezienie piksela o najmniejszej wartości (najciemniejszego) i o największej wartości (najjaśniejszego)

MIN ← dane[0][0]
MAX ← dane[0][0]

dla i = 0, 1, 2, ..., 199 wykonuj
  dla j = 0, 1, 2, ..., 319 wykonuj
    jeżeli dane[i][j] > MAX
      MAX ← dane[i][j]
    jeżeli dane[i][j] < MIN
      MIN ← dane[i][j]

Najpierw ustalamy początkowe wartości zmiennych MIN i MAX. W obu przypadkach będzie to wartość pierwszego elementu tablicy.

Następnie iterujemy po tablicy dwuwymiarowej dane[200][320] i w przypadku, gdy znajdziemy wartość większą od wartości MAX, nadpisujemy wartość zmiennej MAX, nadając jej wartość równą dane[i][j].

Szukanie najciemniejszego piksela jest bardzo podobne. Sprawdzamy, czy aktualnie iterowany element tablicy dwuwymiarowej jest mniejszy od MIN – jeżeli tak, nadpisujemy wartość zmiennej MIN (nadajemy jej wartość dane[i][j])

Oto cały pseudokod:

dane[0..199][0..319]

dla i = 0, 1, 2, ..., 199 wykonuj
    wczytaj kolejną linię z pliku
    dla j = 0, 1, 2, ..., 319 wykonuj
      dane[i][j] ← wczytaj kolejną liczbę z linii

     MIN ← dane[0][0]
     MAX ← dane[0][0]

dla i = 0, 1, 2, ..., 199 wykonuj
   dla j = 0, 1, 2, ..., 319 wykonuj
     jeżeli dane[i][j] > MAX
        MAX ← dane[i][j]
     jeżeli dane[i][j] < MIN
        MIN ← dane[i][j]

Poprawna odpowiedź

Wartość najjaśniejszego piksela 221.

Wartość najciemniejszego piksela 7.

Prawidłowa odpowiedź do zadania 1.1 dla danych zapisanych w pliku dane.txt tekstowym znajduje się w załączniku:

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 ≤ i ≤ 320. Dla danych z pliku przyklad.txt wynikiem jest 3.

Do oceny oddajesz:

• plik wyniki6.txt zawierający odpowiedź (numer zadania i liczba wierszy do usunięcia w osobnych wierszach, dopisane do pliku utworzonego w zadaniu 1.1),

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie

Operujemy na tablicy dwuwymiarowej dane[200][320], do której zostały zapisane dane z pliku tekstowego (wczytanie danych przedstawione jest w rozwiązaniu zadania 1.1).

doUsuniecia ← 0

dla i = 0, 1, 2, ..., 199 wykonuj
k ← 319
dla j = 0, 1, 2, ..., 159 wykonuj
jeżeli dane[i][j] ≠ dane [i][k]
doUsuniecia ← doUsuniecia + 1
wyjdź z pętli
k ← k - 1

Deklarujemy zmienną doUsuniecia, która będzie zliczać linie niespełniające kryterium pionowej osi symetrii. Jako wartość początkową nadajemy jej wartość 0.

Następnie w pętli zewnętrznej przeglądamy kolejne wiersze tablicy dwuwymiarowej dane[200][320]. W pętli wewnętrznej sprawdzamy symetryczność analizowanego wiersza pikseli. Oznacza to, że musimy sprawdzić symetryczność par pikseli równoodległych od badanej pionowej osi symetrii, czyli zweryfikować, czy te wiersze są palindromami. Liczba par do sprawdzenia jest równa połowie rozmiaru wiersza, co wyznacza również ograniczenie wartości iteratora pętli.

• element o indeksie 0 z elementem o indeksie 319;

• element o indeksie 1 z elementem o indeksie 318;

• element o indeksie 3 z elementem o indeksie 317;

...

• element o indeksie 159 z elementem o indeksie 160.

Jeżeli wykryjemy, że elementy porównywane nie są równe, oznacza to, że dana para zaburza oś symetrii i cały wiersz jest do usunięcia. Wówczas dokonujemy inkrementacji zmiennej doUsuniecia oraz wychodzimy z pętli (ponieważ w danym wierszu nie ma już potrzeby, aby sprawdzać inne wartości pikseli).

Schemat punktowania

• 2 pkt – za poprawną odpowiedź

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

Uwaga: Nie przyznaje się 1 pkt.

Poprawna odpowiedź

149

Dla zainteresowanych

W sytuacji, kiedy nie znamy liczby wierszy oraz liczby liczb zapisanych w poszczególnych wierszach pliku wejściowego do przechowania odczytanych danych, używamy struktur dynamicznych.

W języku jedną z możliwości jest wykorzystanie klasy LIST, dzięki której możemy stworzyć strukturę podobną do wykorzystanej wyżej listy list w języku.

Odczytane wiersze przy użyciu metody split() dzielimy na ciągi znaków (separatorem jest znak spacji) zwrócone w tablicy, którą przekształcamy na strumień za pomocą metody stream() klasy Arrays. Następnie korzystamy z metody map(), aby każdy element strumienia przekształcić na liczbę całkowitą. Z uzyskanej tablicy liczb całkowitych za pomocą metody collect() tworzymy listę, którą dodajemy przy użyciu metody add() do listy dane.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        // Lista list
        List<List<Integer>> dane = new ArrayList<>();
        BufferedReader plik = new BufferedReader(new FileReader("dane.txt"));
        String wiersz;
    
        while ((wiersz = plik.readLine()) != null) {
            dane.add(Arrays.stream(wiersz.split(" ")).map(Integer::parseInt).collect(Collectors.toList()));
        }
        plik.close();
    
        // wypisanie odczytanych danych
        for (List<Integer> liczby : dane) {
            for (Integer liczba: liczby)
                System.out.print(liczba + " ");
            System.out.println(" ");
        }
    }

}

Przekierowanie standardowego wejścia i wyjścia

Oprócz przedstawionych rozwiązań możliwe jest również przekierowanie standardowego wejścia i wyjścia na wskazane pliki podczas uruchamianiu kodu z poziomu linii poleceń. Operatorem przekierowania standardowego wejścia jest operator <, natomiast operatorem przekierowania standardowego wyjścia jest operator >.

Program wykorzystujący struktury dynamiczne wymaga minimalnych zmian, aby dane czytane były z przekierowanego wejścia. Wystarczy, że zmienną plik typu BufferReader utworzymy jako obiekt klasy InputStreamReader, której konstruktorowi przekazujemy standardowy strumień wejścia System.in:

BufferedReader plik = new BufferedReader(new InputStreamReader(System.in))

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        // Lista list
        List<List<Integer>> dane = new ArrayList<>();
        BufferedReader plik = new BufferedReader(new InputStreamReader(System.in));
        String wiersz;
    
        while ((wiersz = plik.readLine()) != null) {
            dane.add(Arrays.stream(wiersz.split(" ")).map(Integer::parseInt).collect(Collectors.toList()));
        }
        plik.close();
    
        // wypisanie odczytanych liczb
        for (List<Integer> liczby : dane) {
            for (Integer liczba: liczby)
                System.out.print(liczba + " ");
            System.out.println(" ");
        }
    }

}

Polecenia niezbędne do przetestowania powyższej wersji wydajemy w terminalu:

javac plikZKodem.java
java plikZKodem < dane.txt > wyniki.txt

Pierwsze polecenie kompiluje kod, drugie uruchamia program przekierowując standardowe wejście na plik dane.txt, a wyjście na plik wyniki.txt. Do tego ostatniego pliku trafią wszystkie komunikaty z instrukcji System.out.print() lub System.out.println().

Słownik