Przykładowe zadania maturalne

Zadanie 1. Liczby Fibonacciego

Liczby Fibonacciego są definiowane w następujący sposób:

Rekurencyjny algorytmalgorytmalgorytm, który służy do obliczania wartości dla dowolnego , można zapisać następująco:

Linia 1. funkcja F otwórz nawias okrągły n zamknij nawias okrągły. Linia 2. jeśli n znak równości 1 lub n znak równości 2. Linia 3. wynikiem jest 1. Linia 4. w przeciwnym razie. Linia 5. wynikiem jest F otwórz nawias okrągły n minus 1 zamknij nawias okrągły plus F otwórz nawias okrągły n minus 2 zamknij nawias okrągły.

Zapisz w wybranej przez siebie notacji (w języku programowania lub w pseudokodzie) algorytm iteracyjnyiteracjaiteracyjny, który służy do obliczania wartości liczby dla dowolnego . Algorytm nie może używać tablic.

Zadanie zostało opracowane przez CKE i pojawiło się na egzaminie maturalnym z informatyki w czerwcu roku (poziom rozszerzony).

Praca domowa

Przedstaw rozwiązanie zadania w postaci programu w języku C++, Java lub Python.

Przykładowe rozwiązanie:

Specyfikacja problemu:

Dane:

  • n – liczba naturalna określająca wyraz ciągu Fibonacciego o indeksie n

Wynik:

  • fn – wartość wyrazu ciągu Fibonacciego o indeksie n

Rozwiązanie przedstawimy w postaci pseudokodu. Na początek zauważmy, że dla każdego wyrazu ciągu Fibonacciego potrzebujemy znać dwa wyrazy go poprzedzające. Dwa początkowe wyrazy są znane, zatem bez problemu możemy wyliczyć trzeci. Podobnie dla wyrazu czwartego skorzystamy z wyrazu drugiego i trzeciego.

Zauważmy, że indeksy wyrazów potrzebnych do zbudowania kolejnego przesunęły się o jeden do przodu. Wystarczy zatem skorzystać z pomocniczej zmiennej, która przechowa n poprzedni z obu wyrazów. Wyrazem poprzednim stanie się obecny wyraz następny, a wyrazem następnym stanie się suma obecnego następnego i zmiennej pomocniczej. Powtarzając procedurę  – 2 razy (dwa pierwsze wyrazy są już znane), możemy obliczyć wartość wyrazu ciągu Fibonacciego o indeksie .

Linia 1. n ← wprowadź liczbę naturalną. Linia 2. f1 ← 1. Linia 3. f2 ← 1. Linia 4. dla i znak równości 3 przecinek 4 przecinek kropka kropka kropka przecinek n wykonuj dwukropek. Linia 5. pom ← f1. Linia 6. f1 ← f2. Linia 7. f2 ← f2 plus pom. Linia 8. zwróć f2.

Schemat przyznawania punktów:

– za poprawny algorytm (w tym za prawidłowe zapisanie warunków początkowych i iteracji 1 pkt).

– za zapamiętanie tylko dwóch poprzednich wyrazów ciągu.

– za podanie odpowiedzi błędnej albo za brak odpowiedzi.

Zadanie 2. Analiza algorytmu

Niech n będzie nieujemną liczbą całkowitą, a T[1..n] – tablicą zawierającą n liczb całkowitych. Dla n = 0 tablica T jest pusta (nie zawiera żadnego elementu). Przeanalizuj przedstawioną funkcję d(x), która rozszerza tablicę T o liczbę całkowitą x, a następnie przeprowadza pewną reorganizację zawartości tej tablicy.

Linia 1. d otwórz nawias okrągły x zamknij nawias okrągły dwukropek. Linia 2. n ← n plus 1. Linia 3. T otwórz nawias kwadratowy n zamknij nawias kwadratowy ← x. Linia 4. s ← n. Linia 5. dopóki otwórz nawias okrągły otwórz nawias okrągły s div 2 zamknij nawias okrągły ≥ 1 zamknij nawias okrągły oraz otwórz nawias okrągły T otwórz nawias kwadratowy s zamknij nawias kwadratowy zamknij nawias ostrokątny T otwórz nawias kwadratowy s div 2 zamknij nawias kwadratowy zamknij nawias okrągły wykonuj. Linia 6. pom ← T otwórz nawias kwadratowy s zamknij nawias kwadratowy. Linia 7. T otwórz nawias kwadratowy s zamknij nawias kwadratowy ← T otwórz nawias kwadratowy s div 2 zamknij nawias kwadratowy. Linia 8. T otwórz nawias kwadratowy s div 2 zamknij nawias kwadratowy ← pom. Linia 9. s ← s div 2.

Uwaga: w tym zadaniu przyjmujemy, że:

  • tablica T może być powiększana;

  • jeśli wartość lewego argumentu operatora oraz jest to fałsz, to wartość prawego argumentu nie jest wyliczana;

  • div jest operatorem oznaczającym część całkowitą z dzielenia.

Uzupełnij tabelę – wpisz zawartość tablicy T po wykonaniu d(x) z podanym parametrem x:

n

T[1..n]

x

T po wykonaniu d(x)

4

26, 3, 5, 4

5

26, 5, 5, 4, 3

4

36, 15, 17, 3

5

7

27, 6, 13, 4, 3, 2, 3

30

Zadanie zostało opracowane przez CKE i pojawiło się na egzaminie maturalnym z informatyki w  roku (poziom rozszerzony). Cały arkusz można znaleźć na stronie internetowej Centralnej Komisji Egzaminacyjnej.

Praca domowa

Przedstaw rozwiązanie zadania w postaci programu w języku C++, Java lub Python.

Przykładowe rozwiązanie:

Specyfikacja problemu:

Dane:

  • n – liczba naturalna

  • T[1..n] – tablica zawierająca n liczb całkowitych

Wynik:

  • T[1..n] – tablica liczb całkowitych powstała po wykonaniu d(x)

Zgodnie z przedstawionym algorytmem wstawiamy element x na koniec tablicy T, jej nowy rozmiar zapisujemy do pomocniczej zmiennej s, a następnie, dopóki s div 2 jest większe lub równe oraz element o indeksie s jest większy od elementu o indeksie s div 2, to zamieniamy oba elementy miejscami i dzielimy s całkowitoliczbowo przez .

Dla drugiego wiersza s wynosi , zatem pierwsza iteracja sprawdzi elementy o indeksach oraz . Element T[5] jest jednak mniejszy od T[2], czyli warunek nie jest spełniony. Na koniec tablicy T zostanie jedynie wstawiony argument x o wartości .

36, 15, 17, 3, 5

Dla trzeciego wiersza s wynosi , zatem najpierw sprawdzone zostaną elementy o indeksach oraz . Element T[4] jest mniejszy, więc zostaną zamienione:

27, 6, 13, 4, 3, 2, 3, 30

27, 6, 13, 30, 3, 2, 3, 4

W drugiej iteracji sprawdzamy elementy o indeksach oraz . Ponownie zachodzi zamiana:

27, 6, 13, 30, 3, 2, 3, 4

27, 30, 13, 6, 3, 2, 3, 4

W ostatnim iteracji porównujemy dwa pierwsze elementy tablicy, dla których również spełniony jest warunek pętli:

27, 30, 13, 6, 3, 2, 3, 4

30, 27, 13, 6, 3, 2, 3, 4

Końcowa tabela przedstawia się następująco:

n

T[1..n]

x

T po wykonaniu d(x)

4

26, 3, 5, 4

5

26, 5, 5, 4, 3

4

36, 15, 17, 3

5

36, 15, 17, 3, 5

7

27, 6, 13, 4, 3, 2, 3

30

30, 27, 13, 6, 3, 2, 3, 4

Schemat przyznawania punktów:

– za poprawną odpowiedź w obu wierszach.

– za poprawną odpowiedź w jednym wierszu.

– za podanie odpowiedzi niepoprawnej albo za brak odpowiedzi.

Słownik

algorytm
algorytm

przepis postępowania prowadzący do rozwiązania ustalonego problemu, określający ciąg czynności elementarnych, które należy w tym celu wykonać

iteracja
iteracja

technika programowania polegająca na powtarzaniu tych samych operacji w pętli określoną liczbę razy lub do momentu, aż zostanie spełniony zadany warunek

schemat oceniania
schemat oceniania

dokument, który precyzyjnie określa, które elementy rozwiązania zadań są sprawdzane i w jaki sposób przyznawane są punkty