Zadanie 1. Plansza
5 pktWprowadzenie
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]1.1. Prześledzenie algorytmu na planszy
2 pktPodaj wynik działania algorytmu dla plansz podanych na rysunkach poniżej, gdzie n to liczba wierszy, a m to liczba kolumn danej planszy.
a) n = 3, m = 3
Wynik: …
b) n = 5, m = 3
Wynik: …
c) n = 5, m = 5
Wynik: …
Pokaż odpowiedź i ocenianie CKE
Odpowiedź CKE
a) PRAWDA
b) FAŁSZ
c) PRAWDA
Zasady oceniania CKE
Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.
W zadaniach praktycznych wszystkie wyniki muszą być odzwierciedleniem komputerowej realizacji obliczeń.
2 pkt – odpowiedź poprawna dla trzech podpunktów.
1 pkt – odpowiedź poprawna dla dwóch podpunktów.
0 pkt – odpowiedź niepoprawna lub niepełna albo brak odpowiedzi.
Źródło
Oryginalne zasady oceniania CKE — PDF, strona 21.2. Konstruowanie plansz o zadanym wyniku
2 pktPrzy 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.
Pokaż odpowiedź i ocenianie CKE
Odpowiedź CKE
Przykładowe rozwiązania
Podpunkt a):
Podpunkt b):
Zasady oceniania CKE
Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.
W zadaniach praktycznych wszystkie wyniki muszą być odzwierciedleniem komputerowej realizacji obliczeń.
2 pkt – odpowiedź poprawna, w tym:
1 pkt – poprawny rysunek w podpunkcie a)
1 pkt – poprawny rysunek w podpunkcie b).
0 pkt – odpowiedź niepoprawna albo brak odpowiedzi.
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ół.
Źródło
Oryginalne zasady oceniania CKE — PDF, strona 31.3. Maksymalna liczba czarnych pól
1 pktDana 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.
Odpowiedź: …
Pokaż odpowiedź i ocenianie CKE
Odpowiedź CKE
(n–1)2
Zasady oceniania CKE
Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.
W zadaniach praktycznych wszystkie wyniki muszą być odzwierciedleniem komputerowej realizacji obliczeń.
1 pkt – odpowiedź poprawna.
0 pkt – odpowiedź niepoprawna albo brak odpowiedzi.
