Zadanie 1
Matura z informatyki, maj 2024, poziom rozszerzony
Wymaganie: I.2) do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych. P.I.4) […] analizuje algorytmy na podstawie ich gotowych implementacji. P.I.5) sprawdza poprawność działania algorytmów dla przykładowych danych. P.II.1) projektuje i programuje rozwiązania problemów z różnych dziedzin […]. (1.2–1.3).
Treść zadania
Zadanie 1. Plansza
Dana jest prostokątna plansza złożona z n wierszy i m kolumn zawierająca n * m pól. Wiersze są ponumerowane od góry kolejnymi liczbami 1, 2, …, n, natomiast kolumny od lewej do prawej kolejnymi liczbami 1, 2, …, m. Każde pole jest albo białe, albo czarne.
Planszę możemy opisać jako tablicę dwuwymiarową A[1..n][1..m], w której A[i][j] = 0, jeśli pole w i-tym wierszu i j-tej kolumnie jest czarne, natomiast A[i][j] = 1, jeśli to pole jest białe. Pola w lewym górnym rogu oraz prawym dolnym rogu zawsze są białe (czyli A[1][1] = 1 oraz A[n][m] = 1).
Rozważmy następujący algorytm, w którym jest wykorzystywana pomocnicza tablica P[1..n][1..m], przyjmująca wartości logiczne (PRAWDA albo FAŁSZ).
Specyfikacja: Dane: n, m — liczby całkowite dodatnie, wymiary planszy; A[1..n][1..m] — opis planszy. Wynik: PRAWDA albo FAŁSZ.
P[1][1] ← PRAWDA dla i = 1, 2, …, n wykonuj dla j = 1, 2, …, m wykonuj jeżeli A[i][j] = 0 P[i][j] ← FAŁSZ w przeciwnym przypadku jeżeli i = 1 oraz j ≠ 1: P[i][j] ← P[i][j − 1] jeżeli i ≠ 1 oraz j = 1: P[i][j] ← P[i − 1][j] jeżeli i ≠ 1 oraz j ≠ 1: P[i][j] ← P[i][j − 1] lub P[i − 1][j] podaj wynik P[n][m]
Zadanie 1.1. (0–2) Podaj wynik działania algorytmu dla planszy z podanych rysunków: a) n = 3, m = 3; b) n = 5, m = 3; c) n = 5, m = 5.
Zadanie 1.2. (0–2) Przy założeniu, że lewy górny i prawy dolny róg planszy są białe, podaj przykład planszy (zamaluj odpowiednie pola lub wpisz w nie zera): a) o 5 wierszach i 5 kolumnach, na której co najwyżej 2 pola są czarne, a wynikiem działania algorytmu jest FAŁSZ; b) o 4 wierszach i 4 kolumnach, na której co najmniej 9 pól jest czarnych, a wynikiem działania algorytmu jest PRAWDA.
Zadanie 1.3. (0–1) Dana jest kwadratowa plansza o n wierszach i n kolumnach. Podaj, jaka jest największa możliwa liczba czarnych pól na tej planszy, dla których wynikiem działania algorytmu jest PRAWDA.
Źródło: arkusz CKE MINP-R0-100-2405. Otwórz oryginalny PDF
Rozwiązanie
Algorytm sprawdza, czy istnieje droga od pola (1,1) do (n,m) poruszająca się tylko w prawo lub w dół wyłącznie po białych polach. Tablica P[i][j] = PRAWDA wtedy i tylko wtedy, gdy istnieje taka droga od (1,1) do (i,j).
1.1. Odpowiedź z zasad oceniania CKE: a) PRAWDA, b) FAŁSZ, c) PRAWDA. (Plansze do tego zadania są w arkuszu na rysunkach; dla każdej sprawdzamy, czy istnieje droga z (1,1) do (n,m) po białych polach, idąca tylko w prawo lub w dół.)
1.2.
a) Plansza 5×5, co najwyżej 2 czarne pola, wynik = FAŁSZ. Wystarczy „odciąć” wszystkie możliwe ścieżki dwoma polami. Przykład: pola czarne (1,2) i (2,1) — od (1,1) nie można pójść ani w prawo, ani w dół po polach białych, więc algorytm zwraca FAŁSZ.
b) Plansza 4×4, co najmniej 9 czarnych pól, wynik = PRAWDA. Musi pozostać monotoniczna ścieżka biała o długości 7 pól. Przykład — pozostawiamy ścieżkę typu „L":
1 1 1 1
0 0 0 1
0 0 0 1
0 0 0 1
Liczba czarnych: 9, ścieżka biała (1,1)→(1,2)→(1,3)→(1,4)→(2,4)→(3,4)→(4,4) istnieje, więc wynik = PRAWDA.
1.3. Liczba pól ogółem = n². Każda monotoniczna ścieżka prawo/dół z (1,1) do (n,n) składa się z dokładnie 2n − 1 pól białych. Maksymalna liczba czarnych pól, dla których wynik = PRAWDA wynosi więc:
n² − (2n − 1) = n² − 2n + 1 = (n − 1)².
Uwaga: algorytm dopuszcza ruch TYLKO w prawo lub w dół (wartość P[i][j] bierze się z pola z lewej, P[i][j−1], albo z góry, P[i−1][j]), nie w lewo i nie w górę. Zasady oceniania 1.2 podkreślają, że musi istnieć ścieżka po białych polach od lewego górnego do prawego dolnego rogu, idąca tylko w prawo lub w dół. W 1.3 pamiętaj, że każda taka ścieżka na planszy n × n ma 2n − 1 pól (nie 2n).
Strona arkusza CKE z treścią zadania
Rozwiązanie
Algorytm to klasyczny przykład programowania dynamicznego dla problemu ścieżki monotonicznej w siatce. Tablica P[i][j] mówi: „czy z pola (1,1) da się dojść do pola (i,j) idąc tylko w prawo lub w dół po polach białych”.
Krok po kroku — interpretacja reguł:
- Pole czarne → automatycznie FAŁSZ (nie można na nim stać).
- Pierwszy wiersz (i = 1): możemy dojść tylko z lewej → kopiujemy P[1][j−1].
- Pierwsza kolumna (j = 1): możemy dojść tylko z góry → kopiujemy P[i−1][1].
- Pozostałe pola: możemy dojść z lewej LUB z góry → suma logiczna.
1.3 — uzasadnienie maksimum: Aby wynik = PRAWDA musi istnieć co najmniej jedna monotoniczna ścieżka biała od (1,1) do (n,n). Najkrótsza ma długość 2n − 1 pól. Reszta planszy ((n − 1)² pól) może być dowolnie zaczerniona, byleby ścieżka pozostała.
Rozumiesz, jak to rozwiązać?
Przećwicz podobne typy zadań w aplikacji
matury-online.pl ma tysiące zadań pogrupowanych po dziedzinach. Sprawdź, czy temat „algorytm na tablicy dwuwymiarowej, plansza prostokątna, analiza algorytmu” zrobisz samodzielnie.
Otwórz matury-online.pl