Aby rozwiązać to zadanie, trzeba przyjrzeć się tej funkcji. Na pierwszy rzut oka widać, że jest to funkcja rekurencyjna - wywołuje ona sama siebie.
Nie lubię pseudokodu - przepiszę sobie tę funkcję w Pythonie:
def pisz(s, n, k):
if len(s) == n:
print(s)
else:
for i in range(0, k):
pisz(s + str(i), n, k)
Zadanie 2.1
Sprawdźmy zatem, co będzie się działo po wywołaniu funkcji pisz("", 2, 2)
. Odczytuj to, patrząc na algorytm. Bez tego nic nie zrozumiesz. Wyobraź sobie, że jesteś programem :)
pisz("", 2, 2)
- jest to pierwsza funkcja, na górze diagramu, wywołujemy ją
- Stan zmiennych w funkcji:
s = "", n = 2, k = 2
len(s) ≠ n
, więc trafiamy do pętlifor
- Pierwsza iteracja pętli, dla
i = 0
:- wywołujemy funkcję
pisz(s + str(i), n, k)
, czylipisz("0", 2, 2)
(możemy już zapisać cyfrę 2 przy pozycjipisz("0", 2, 2)
w drzewku - bo ta funkcja wykona się jako druga)- Stan zmiennych:
s = "0", n = 2, k = 2
len(s) ≠ n
, więc trafiamy do pętlifor
- Pierwsza iteracja pętli, dla
i = 0
:- wywołujemy funkcję
pisz(s + str(i), n, k)
, czylipisz("00", 2, 2)
(zapisujemy w drzewku że ta funkcja wykona się jako trzecia)len(s) = n
, więc wypisujemy wartośćs
, czyli00
- wywołujemy funkcję
- Druga iteracja pętli, dla
i = 1
:- wywołujemy funkcję
pisz(s + str(i), n, k)
, czylipisz("01", 2, 2)
(zapisujemy w drzewku że ta funkcja wykona się jako czwarta)len(s) = n
, więc wypisujemy wartośćs
, czyli01
- wywołujemy funkcję
- Stan zmiennych:
- wywołujemy funkcję
- Analogicznie postępując z drugą iteracją pętli, dla
i = 1
, odkryjemy kolejność wykonywania drugiej gałęzi drzewka oraz wypisywane z niej napisy.
Odpowiedź
Schemat punktowania
2 p. – za poprawną odpowiedź, w tym:
- 1 p. – poprawne uzupełnienie drzewka wywołań funkcji pisz,
- 1 p. – prawidłową kolejność wywołań.
0 p. – za podanie odpowiedzi błędnej albo brak odpowiedzi.
Wnioski
Spróbujmy wyciągnąć jakieś wnioski z tego co mozolnie prześledziliśmy. Przydadzą nam się do kolejnego zadania.
s
to początkowy string, zakładamy, że zawsze w pierwszym wywołaniu jest on pusty - tak jest we wszystkich przykładach w tym zadaniu.
Ten s
wypisywany jest zawsze wtedy, kiedy osiągnie długość n
.
Oznacza to, że funkcja pisz
wypisze zawsze same wyrazy o długości n
!
k
z kolei reguluje liczbę iteracji pętli for
, a każda iteracja pętli for
dodaje do napisu aktualne i
. Przy czym to i
, to będą liczby z przedziału <0, k)
(czemu? linia 5 kodu w Pythonie).
Wynikiem funkcji będą zatem ciągi cyfr o długości n
, składające się z cyfr z przedziału <0, k)
.
Czy będą to wszystkie możliwe n
-znakowe kombinacje cyfr z przedziału <0, k)
?
Czy w tym przykładzie (funkcja pisz(s = "", n = 2, k = 2)
) uzyskaliśmy wszystkie możliwe 2
-znakowe kombinacje składające się z cyfr z przedziału <0, 2)
?
Otrzymaliśmy liczby 00, 01, 10, 11. Więc odpowiedź na oba te pytania to tak.
Podsumowując - n
to liczba znaków w napisie, cyfry od 0
do k-1
to cyfry, z których może składać się napis.
Zadanie 2.2
W poprzednim podpunkcie zrozumieliśmy regułę tworzenia napisów. To, jakie napisy i ile ich jest tworzonych przez funkcję pisz("", n, k)
, zależy od zmiennych n
i k
.
pisz("", 3, 2)
Teraz naszym zadaniem jest wypisanie napisów powstałych w wyniku wywołania funkcji pisz("", 3, 2)
. n = 3
, więc wiemy już, że otrzymamy same 3
-znakowe napisy. k = 2
, więc będą to napisy składające się wyłącznie z cyfr 0
lub 1
. Wypiszmy je zatem:
000
001
010
011
100
101
110
111
Są to wszystkie 3-znakowe kombinacje złożone z cyfr 0 i 1.
Ile wyniesie liczba wywołań funkcji pisz
?
Liczymy pierwsze wywołanie (+1), a potem z każdego wywołania funkcji pisz
kiedy len(s) < n
(tu n = 3
) funkcja pisz
zostanie jeszcze wywołana k
(tu 2
) razy.
Sprawdźmy więc, dla każdego len(s)
:
wywołanie początkowe (+1)
len(s) = 0
(+2) - kolejne dwa wywołania
len(s) = 1
(+4) - z każdego z dwóch wywołań dwa wywołania ;)
len(s) = 2
(+8) - analogicznie
len(s) = 3
wywołanych 8 funkcji z poprzedniego etapu kończy swój żywot, bo len(s) = n
, wypisywane są napisy i nie wywoływane są żadne funkcje pisz
Zatem funkcja zostanie wywołana 15 razy (1 + 2 + 4 + 8).
pisz("", 2, 3)
Funkcja pisz("", 2, 3)
Napisy 2
-znakowe, z cyfr od 0 do 2.
00
01
02
10
11
12
20
21
22
n = 2
, dla każdego len(s) < n
:
wywołanie początkowe (+1)
len(s) = 0
(+3) - trzy wywołania, bo k = 3
len(s) = 1
(+9) - trzy wywołania z każdego z trzech wywołań
Dla zobrazowania, pogrubię tutaj wszystkie 13 wywołań funkcji pisz (trzeba doliczyć jeszcze tylko jedno początkowe, którego "nie widać", i jednocześnie z którego wywoływane są pierwsze trzy funkcje pisz, z których powstały początkowe cyfry 0, 1 i 2):
00
01
02
10
11
12
20
21
22
Zatem funkcja zostanie wywołana 13 razy (1 + 3 + 9).
Schemat punktowania
2 p. – za poprawną odpowiedź, w tym:
- 1 p. – za każde poprawnie uzupełnione dwa pola tabeli.
Uwaga: teksty wypisane przez funkcję mogą być zapisane w jednym wierszu lub jeden pod drugim – nie zmienia to oceny.
0 p. – za podanie odpowiedzi błędnej albo brak odpowiedzi.
Zadanie 2.3
Zaobserwujmy w jaki sposób otrzymaliśmy w poprzednim podpunkcie liczbę wywołań. Powinniśmy zauważyć w niej ciąg. (1 + 2 + 4 + 8), (1 + 3 + 9). Do opisania tych ciągów musimy użyć zmiennych n
i k
, bo to od nich zależna jest liczba wywołań.
(1 + 2 + 4 + 8) n = 3, k = 2, hmm, to jest 1 + 3 kolejne potęgi 2-jki
(1 + 3 + 9) n = 2, k = 3, a to jest 1 + 2 kolejne potęgi 3-jki
A więc wystarczy zapisać następujący wzór na łączną liczbę wykonań funkcji: 1 + k + k2 + ... + kn
Koniec zadania!
Schemat punktowania
2 p. – za poprawną odpowiedź,
1 p. – w przypadku podania w odpowiedzi liczby mniejszej o 1 lub gdy ostatni element szeregu w odpowiedzi ma indeks n-1 zamiast n (np. 1+k+k2+…+kn-1 zamiast 1+k+k2+…+kn),
0 p. – za podanie odpowiedzi błędnej albo brak odpowiedzi.
Uwaga: odpowiedź może być zapisana także w postaci sumy (ze znakiem ∑ ).
Linki do arkusza w formacie .pdf ze strony CKE:
CKE Matura z informatyki 2019 - arkusz część I
CKE Matura z informatyki 2019 - zasady oceniania