Matura 2017 (nowa) - zadanie 2 (Rekurencja)

Zadanie 2.1 (2 punkty)

Mała tabelka do uzupełnienia. Po dokładnej analizie wywołań dla poszczególnych wartości uzupełniamy ją następującymi wynikami:

x licz(x)
11 2
13 2
21 1
32 -4

Można się spodziewać, że na poprawne dwa poprawne wyniki (z trzech do uzupełnienia) będzie można otrzymać jeden punkt. Za jeden poprawny wynik raczej nie można liczyć na jakiekolwiek punkty.

Zadanie 2.2 (2 punkty)

Po krótkiej analizie algorytmu można zobaczyć, że każde wywołanie funkcji licz z argumentem x większym od 1 powoduje kolejne wywołanie z argumentem x/2. Wynika z tego, że sumaryczna liczba wywołań funkcji licz jest równa długości liczby x w zapisie binarnym. Zatem najmniejszą liczbą, która daje dokładnie k wywołań funkcji licz jest liczba, która w zapisie binarnym ma na pierwszej pozycji cyfrę 1 a następnie k-1 cyfr 0, zatem liczba ta jest równa 2k-1. W związku z tym, że zadanie jest punktowane dwoma punktami, być może podobna odpowiedź 2k będzie punktowana jednym punktem. Może być też jednak tak, że ta odpowiedź miała utrudnić wybranie właściwej i jedyne punkty jakie można będzie uzyskać to dwa za poprawną odpowiedź. Jak będzie zobaczymy za kilka tygodni.

Zadanie 2.3 (2 punkty)

W tym zadaniu trzeba było podać najmniejszą liczbę całkowitą większą od 100, dla której wynikiem wywołania funkcji licz(x) będzie 0.Z opowieści znajomych nauczycieli wynika, że w niektórych szkołach każdy wychodzący z egzaminu maturzysta podawał inną znalezioną najmniejszą liczbę.

Z analizy algorytmu wynika, że każdy bit 1 w zapisie bitowym argumentu x zwiększa wynik o 1, zaś każdy bit 0 zmniejsza wynik o 1. Aby wynik był równy 0 liczba x w zapisie bitowym musi mieć parzystą liczbę bitów pomijając wiodące 0. W związku z tym, że liczba ma być większa od 100 i być możliwie najmniejsza to powinna mieć osiem bitów. Najmniejszą taką liczbą jest 10000111|2, czyli 135.

Za zadanie z jednym wynikiem ponownie można otrzymać dwa punkty, zatem należy spodziewać się, że za niektóre błędy będzie można otrzymać 1 punkt. W poleceniu były podane trzy warunki:

  • najmniejsza możliwa
  • większa od 100
  • wynik licz(x) jest równy 0

Pominięcie ostatniego z warunków (wynik 101) wydaje się dyskwalifikować rozwiązanie (nie ma żadnego związku z podaną na wstępie zadania funkcją). Pominięcie drugiego (wynik 2) powoduje szukanie totalnie banalnego rozwiązania. Jedynym pominiętym warunkiem, który nie upraszcza zanadto zadania wydaje się zatem warunek pierwszy. Po jego pominięciu (np. wyniki 139, 170) być może można liczyć na otrzymanie 1 punktu.

Mogę też sobie wyobrazić próbę podania wyniku 102 (w ośmiobitowym zapisie binarnym 01100110|2), jednak w rozumieniu tego algorytmu ta liczba jest jedynie siedmiobitowa i i raczej nie ma możliwości aby w takim przypadku otrzymać za rozwiązanie jakikolwiek punkt.