Zadanie 2.2, matura maj 2017, informatyka rozszerzona

2 pktzamknięteśrednie 63%Maj 2017

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 punkty

Dana 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.

Wypróbuj za darmo

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

2 pkt

za prawidłową odpowiedź 2k−1.

1 pkt

za odpowiedź 2k.

0 pkt

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ń.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.