Zadanie 1.2, matura maj 2024, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
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]
```
Polecenie
2 punktyPrzy 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
Powiększb) o 4 wierszach i 4 kolumnach, na której co najmniej 9 pól jest czarnych, a wynikiem działania algorytmu jest PRAWDA.
PowiększKorepetytor
Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.
5 rozmów · bez karty · Zaloguj się
Sprawdź się
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
Przykładowe rozwiązania (0 – pole czarne, 1 – pole białe):
Podpunkt a):
```
1 0 1 1 1
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
```
lub
```
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 0
1 1 1 0 1
```
Podpunkt b):
```
1 0 0 0
1 0 0 0
1 0 0 0
1 1 1 1
```
lub
```
1 1 0 0
0 1 0 0
0 1 0 0
0 1 1 1
```
lub
```
1 1 1 1
0 0 0 1
0 0 0 1
0 0 0 1
```
Uwaga: Musi istnieć ścieżka przejścia po białych polach od lewego górnego rogu do prawego dolnego, taka że poruszamy się tylko w prawo lub w dół.
Schemat punktowania
odpowiedź poprawna, w tym:
poprawny rysunek w podpunkcie a)
poprawny rysunek w podpunkcie b).
odpowiedź niepoprawna albo brak odpowiedzi.
Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.
Komentarz. Musi istnieć ścieżka przejścia po białych polach od lewego górnego rogu do prawego dolnego, taka że poruszamy się tylko w prawo lub w dół.