1.3. Rekurencja dla potęg dwójki

ORYGINALNE POLECENIE CKE

Wprowadzenie

Dana jest zdefiniowana rekurencyjnie funkcja A(m, n), gdzie m i n są dodatnimi liczbami całkowitymi.

A(m,n)={mgdy n = 1A(2·m,n2)gdy n > 1 oraz n jest podzielne przez 22·A(m,n−12)+mgdy n > 1 oraz n nie jest podzielne przez 2

Polecenie

Uzupełnij tabelę. W drugiej kolumnie podaj liczbę wywołań rekurencyjnych funkcji A dla każdej wartości n podanej w tabeli (drugiego argumentu wywołania funkcji, pierwszy jest nieistotny w tym zadaniu). W trzeciej kolumnie podaj wyrażenie, którego wartość jest równa drugiemu argumentowi funkcji w i-tym wywołaniu rekurencyjnym dla wszystkich wartości i większych bądź równych 1 i mniejszych bądź równych całkowitej liczbie wywołań.

n – drugi argument wywołania funkcjiliczba wywołań rekurencyjnychwartość drugiego argumentu A w i-tym wywołaniu rekurencyjnym
8382i (lub 23 − i)
2k
2k − 1

gdzie k jest pewną liczbą całkowitą dodatnią większą od 2.

Pokaż odpowiedź i ocenianie CKE

Odpowiedź CKE

Poprawna odpowiedź

liczba wywołań rekurencyjnychwartość drugiego argumentu A w i-tym wywołaniu rekurencyjnym
382i (lub 23 − i)
k2k − i
k − 12k − i − 1 (lub ⌊2k−12i⌋)

Zasady oceniania CKE

3 pkt – odpowiedź poprawna w 4 polach tabeli.

2 pkt – odpowiedź poprawna w 3 polach tabeli.

1 pkt – odpowiedź poprawna w 2 polach tabeli.

0 pkt – odpowiedź niepoprawna albo brak rozwiązania.

Uwagi ogólne CKE

Ten dokument zawiera zasady oceniania oraz odpowiedzi i przykłady poprawnych rozwiązań zadań.

W zadaniach otwartych akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.

W zadaniach praktycznych wszystkie wyniki muszą być odzwierciedleniem komputerowej realizacji obliczeń. Realizacje komputerowe muszą być zapisane zgodnie z instrukcjami w arkuszu.

Źródło

Oryginalne zasady oceniania CKE — PDF, strona 4

Potrzebujesz pomocy w przygotowaniu do matury?

Zobacz korepetycje

TWÓJ NASTĘPNY KROK

Przygotuj się do matury z informatyki ze mną.

Igor Józefowicz — korepetycje z informatyki do matury

Na indywidualnych zajęciach online uporządkujemy trudne zagadnienia i przećwiczymy zadania maturalne. Wspólnie ustalimy plan przygotowań dopasowany do Twojego poziomu i celu.

TWÓJ PIERWSZY KROK

30 minut · online · bezpłatnie

Umów bezpłatną rozmowę