Zadanie 2.3, matura czerwiec 2018, informatyka rozszerzona

2 pktotwartetrudne (szac.)Czerwiec 2018

Darmowe konto pozwoli wrócić do niego później.

Zadanie

Zadanie 2. Liczby Fibonacciego

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

F1 = 1, F2 = 1,

Fn = Fn−1 + Fn−2 dla n = 3, 4, …

Rekurencyjny algorytm, który służy do obliczania wartości Fn 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)

```

Polecenie

2 punkty

Aby przyśpieszyć rekurencyjne obliczanie wartości n-tego wyrazu ciągu Fibonacciego, można skorzystać z następujących wzorów, prawdziwych dla dowolnego całkowitego k ≥ 2:

F2k = (Fk+1)2 − (Fk−1)2

F2k−1 = (Fk)2 + (Fk−1)2

Zapisz w wybranej przez siebie notacji (w postaci listy kroków, w języku programowania lub w pseudokodzie) algorytm rekurencyjny, który służy do obliczania wartości liczby Fn dla dowolnego n ≥ 1 i korzysta z tych wzorów.

Algorytm:

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

Przykładowe rozwiązanie:

```cpp

long int kw(long int n)

{

return n*n;

}

long int f(long int n)

{

int i,k;

if(n==1||n==2) return 1;

else if (n%2==0) {

i=n/2+1;

k=n/2-1;

return kw(f(i))-kw(f(k));

}

else {

i=(n+1)/2;

k=(n+1)/2-1;

return kw(f(i))+kw(f(k));

}

}

int main() {

int n;

cin>>n;

cout << f(n)<< endl;

return 0;

}

```

Uwaga: Dopuszczamy zastosowanie przez zdającego funkcji potęgowania wbudowanej w język programowania.

Schemat punktowania

2 pkt

za poprawną odpowiedź, w tym:

1 pkt

za prawidłowe zdefiniowanie warunków

1 pkt

za prawidłowe wywołania rekurencyjne

0 pkt

za podanie odpowiedzi błędnej albo brak odpowiedzi.

Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.

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.