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  listy list (Python).

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

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

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