Zadanie 2.2, matura maj 2017, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 2. Rekurencja
Funkcja licz(x) przyjmuje jako argument dodatnią liczbę całkowitą x, natomiast jako wynik daje pewną liczbę całkowitą.
```
licz(x)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2)
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1
```
Uwaga: div – dzielenie całkowite, mod – reszta z dzielenia całkowitego.
Polecenie
2 punktyDana jest dodatnia liczba całkowita k. Jaka jest najmniejsza dodatnia liczba całkowita x, dla której obliczanie wartości licz(x) wymaga dokładnie k wywołań funkcji licz, licząc także pierwsze wywołanie licz(x)? Podkreśl prawidłową odpowiedź.
Przykład: obliczenie licz(13) wymaga dokładnie 4 wywołań funkcji licz.
- Ax = k2
- Bx = 2k−1
- Cx = k + 1
- Dx = 2k
Korepetytor
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
B. x = 2k−1
Schemat punktowania
za prawidłową odpowiedź 2k−1.
za odpowiedź 2k.
za podanie odpowiedzi błędnej albo brak odpowiedzi.
Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.
Komentarz. Liczba wywołań funkcji zależy od liczby bitów w binarnej reprezentacji x. Dla x = 2^{k-1} potrzeba dokładnie k wywołań.