2019-zad2

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

2019-zad2.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ętli for
  • Pierwsza iteracja pętli, dla i = 0:
    • wywołujemy funkcję pisz(s + str(i), n, k), czyli pisz("0", 2, 2) (możemy już zapisać cyfrę 2 przy pozycji pisz("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ętli for
      • Pierwsza iteracja pętli, dla i = 0:
        • wywołujemy funkcję pisz(s + str(i), n, k), czyli pisz("00", 2, 2) (zapisujemy w drzewku że ta funkcja wykona się jako trzecia)
          • len(s) = n, więc wypisujemy wartość s, czyli 00
      • Druga iteracja pętli, dla i = 1:
        • wywołujemy funkcję pisz(s + str(i), n, k), czyli pisz("01", 2, 2) (zapisujemy w drzewku że ta funkcja wykona się jako czwarta)
          • len(s) = n, więc wypisujemy wartość s, czyli 01
  • 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ź

2019-zad2.1-odp

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

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

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