Zadanie 1. Rekurencja
7 pktWprowadzenie
Dana jest zdefiniowana rekurencyjnie funkcja A(m, n), gdzie m i n są dodatnimi liczbami całkowitymi.
1.1. Wywołania funkcji A
3 pktObliczenie wartości funkcji A(3, 9) wprost z definicji wymaga trzech wywołań rekurencyjnych: A(3, 4), A(6, 2), A(12, 1), ponieważ:
A(3, 9) = 2 · A(3, 4) + 3 = 2 · A(6, 2) + 3 = 2 · A(12, 1) + 3 = 2 · 12 + 3 = 27
Uzupełnij poniższą tabelę. Podaj liczbę wywołań rekurencyjnych funkcji A oraz wypisz wywołania rekurencyjne wraz z ich argumentami (w ostatnim wierszu podaj tylko liczbę wywołań rekurencyjnych).
| m | n | liczba wywołań rekurencyjnych funkcji A | wywołania rekurencyjne funkcji A |
|---|---|---|---|
| 3 | 9 | 3 | A(3, 4), A(6, 2), A(12, 1) |
| 25 | 25 | ||
| 10 | 15 | ||
| 1 | 2100 + 1 | — |
Pokaż odpowiedź i ocenianie CKE
Odpowiedź CKE
Poprawna odpowiedź
| liczba wywołań rekurencyjnych funkcji A | wywołania rekurencyjne funkcji A |
|---|---|
| 3 | A(3, 4), A(6, 2), A(12, 1) |
| 5 | A(26, 24), A(27, 23), A(28, 22), A(29, 21), A(210, 20) |
| 3 | A(10, 7), A(10, 3), A(10, 1) |
| 100 |
Zasady oceniania CKE
3 pkt – odpowiedź poprawna w 5 polach tabeli.
2 pkt – odpowiedź poprawna w 4 polach tabeli.
1 pkt – odpowiedź poprawna dla co najmniej dwóch pól tabeli.
0 pkt – odpowiedź niepoprawna lub niepełna 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 21.2. Wartości funkcji A
1 pktUzupełnij poniższą tabelę. Podaj wartości funkcji A(m, n) dla zadanych argumentów m i n:
| m | n | A(m, n) |
|---|---|---|
| 1 | 777 | |
| 2 · 106 | 256 · 106 |
Uwaga: W swoich odpowiedziach możesz zapisać wynik podobnie jak wartości w pierwszych dwóch kolumnach (z wykorzystaniem operatorów mnożenia i potęgowania).
Pokaż odpowiedź i ocenianie CKE
Odpowiedź CKE
Poprawna odpowiedź
| 777 |
| 512·1012 = 512 000 000 000 000 |
Zasady oceniania CKE
1 pkt – odpowiedź poprawna w 2 wierszach tabeli.
0 pkt – odpowiedź niepoprawna lub niepełna 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 31.3. Rekurencja dla potęg dwójki
3 pktUzupeł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 funkcji | liczba wywołań rekurencyjnych | wartość drugiego argumentu A w i-tym wywołaniu rekurencyjnym |
|---|---|---|
| 8 | 3 | (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ń rekurencyjnych | wartość drugiego argumentu A w i-tym wywołaniu rekurencyjnym |
|---|---|
| 3 | (lub 23 − i) |
| k | 2k − i |
| k − 1 | 2k − i − 1 (lub ) |
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.
