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 pikselipikselpikseli 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 C++ najprostszym sposobem na odczytanie liczb z kolejnych wierszy podanego pliku jest użycie operatora przekierowania wejścia >>. W zagnieżdżonej pętli for odczytujemy z każdego wiersza 320 liczb.

#include <fstream>
#include <iostream>
#include <string>

using namespace std;

int main() {
    // dwuwymiarowa tablica
    int dane[200][320];
    fstream plik("dane.txt", ios::in);

    if (plik.good()) {
        for (int i = 0; i < 200; i++) {
            // odczytywanie liczb z wiersza
            for (int j = 0; j < 320; j++)
                plik >> dane[i][j];
        }
    }
    plik.close();

    // wypisanie wczytanych liczb
    for (int i = 0; i < 200; i++) {
        for (int j = 0; j < 320; j++)
            cout << dane[i][j] << " ";
        cout << endl;
    }

    return 0;
}

W językach Java i Python 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(" ");
        }

    }
}

W języku Python nie używa się tablic o określonym z góry rozmiarze, struktury służące do przechowywania wielu elementów, np. listy, są dynamiczne. W podanym niżej rozwiązaniu ciągi znaków zwrócone przez metodę split() przekształcamy na liczby całkowite w wyrażeniu listowym, a uzyskaną listę zapisujemy w liście dane.

dane = []  # lista do zapisania list z odczytanymi liczbami
with open("dane.txt", "r", encoding="utf-8") as plik:
    for wiersz in plik:
        dane.append([int(liczba) for liczba in wiersz.split(" ")])

# wypisanie wczytanych liczb
for liczby in dane:
    print(*liczby)

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]

Schemat punktowania

• 2 pkt – za prawidłową odpowiedź, w tym:

  • 1 pkt – za podanie wartości najjaśniejszego piksela

  • 1 pkt – za podanie wartości najciemniejszego piksela

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

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

Podane w zadaniu 1.1 rozwiązanie dla języka Python można wykorzystać również w omawianym przypadku.

W języku C++ możemy skorzystać z tablic typu vector. W podanym niżej kodzie zawartość pliku odczytujemy wiersz po wierszu. Każdy odczytany wiersz przekształcamy na strumień wejściowy za pomocą konstruktora istringstream. Z otrzymanego strumienia, podobnie jak z pliku, za pomocą operatora przekierowania wejścia >> odczytujemy wszystkie liczby.

#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

int main() {
    // 2-wymiarowa tablica dynamiczna
    vector<vector<int>> dane;
    fstream plik("dane.txt", ios::in);
    string wiersz;
    int liczba;

    if (plik.good()) {
        while (getline(plik, wiersz)) {
            // przekształcenie wiersza na strumień wejścia
            istringstream sstr(wiersz);
            vector<int> liczby;
            while (sstr >> liczba)
                liczby.push_back(liczba);
            dane.push_back(liczby);
        }
    }

    // wypisanie wczytanych liczb
    for(int i = 0; i < (int)dane.size(); i++) {
        for (int j = 0; j < (int)dane[i].size(); j++)
            cout << dane[i][j] << " ";
        cout << endl << endl;
    }

    return 0;
}

W języku Java 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 Python.

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

Język C++

Podany niżej kod jest prawie identyczny z omówionym wyżej rozwiązaniem wykorzystującym dynamiczne tablice. Zmiany polegają na usunięciu kodu obsługującego strumień pliku i użyciu standardowego strumienia wejścia w instrukcji: getline(cin, wiersz).

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

int main() {
    // 2-wymiarowa tablica dynamiczna
    vector<vector<int>> dane;
    string wiersz;
    int liczba;

    while (getline(cin, wiersz)) {
        // przekształcenie wiersza na strumień wejścia
        istringstream sstr(wiersz);
        vector<int> liczby;
        while (sstr >> liczba)
            liczby.push_back(liczba);
        dane.push_back(liczby);
    }

    // wypisanie wczytanych liczb
    for(int i = 0; i < (int)dane.size(); i++) {
        for (int j = 0; j < (int)dane[i].size(); j++)
            cout << dane[i][j] << " ";
        cout << endl;
    }

    return 0;
}

Sprawdzenie działania powyższej wersji kodu możliwe jest po wykonaniu w terminalu następujących poleceń:

g++ plik_z_kodem.cpp -o plik_wykonywalny.exe
./plik_wykonywalny.exe < dane.txt > wyniki.txt

Pierwsze polecenie kompiluje kod i buduje plik wykonywalny (w systemach Linux rozszerzenie .exe jest opcjonalne). Drugie polecenie jako strumień wejścia wskazuje plik dane.txt, a jako strumień wyjścia, do którego wypisywane będą komunikaty np. funkcji cout(), plik wyniki.txt.

Język Java

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().

Język Python

W języku Python można dane czytać ze standardowego strumienia wejścia sys.stdin, jednak kiedy dane znajdują się w pliku, lepiej użyć modułu fileinput i metody input():

import fileinput

dane = []  # lista do przechowywania list z odczytanymi liczbami
for wiersz in fileinput.input():
    dane.append([int(liczba) for liczba in wiersz.split(" ")])

# wypisanie wczytanych liczb
for liczby in dane:
    print(*liczby)

Polecenie uruchomienia skryptu z wejściem przekierowanym na plik dane.txt, a wyjściem na plik wyniki.txt wydajemy w terminalu:

python3 ./plik_z_kodem.py < dane.txt > wyniki.txt

Do pliku wyniki.txt zapisane zostaną wszystkie komunikaty z instrukcji print().

Słownik