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 $F_n$ dla dowolnego $n ≥ 1$, można zapisać następująco:

funkcja F(n)
	jeśli n = 1 lub n = 2
		wynikiem jest 1
	w przeciwnym razie
		wynikiem jest F(n - 1) + F(n - 2)

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 $F_n$ dla dowolnego $n ≥ 1$. Algorytm nie może używać tablic.

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ę $n$ – 2 razy (dwa pierwsze wyrazy są już znane), możemy obliczyć wartość wyrazu ciągu Fibonacciego o indeksie $n$.

n ← wprowadź liczbę naturalną
f1 ← 1
f2 ← 1
dla i = 3, 4, ..., n wykonuj:
	pom ← f1
	f1 ← f2
	f2 ← f2 + pom
zwróć f2

Schemat przyznawania punktów:

$2\ \text{pkt}$ – za poprawny algorytm (w tym za prawidłowe zapisanie warunków początkowych i iteracji 1 pkt).

$1\ \text{pkt}$ – za zapamiętanie tylko dwóch poprzednich wyrazów ciągu.

$0\ \text{pkt}$ – 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.

d(x):
	n ← n + 1
	T[n] ← x
	s ← n
	dopóki ((s div 2) ≥ 1) oraz (T[s] > T[s div 2]) wykonuj
		pom ← T[s]
		T[s] ← T[s div 2]
		T[s div 2] ← pom
		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:

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 $1$ 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 $2$.

Dla drugiego wiersza s wynosi $5$, zatem pierwsza iteracja sprawdzi elementy o indeksach $5$ oraz $2$. 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 $-5$.

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

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

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

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

Schemat przyznawania punktów:

$2\ \text{pkt}$ – za poprawną odpowiedź w obu wierszach.

$1\ \text{pkt}$ – za poprawną odpowiedź w jednym wierszu.

$0\ \text{pkt}$ – za podanie odpowiedzi niepoprawnej albo za brak odpowiedzi.

Słownik