Zadanie 2.3, matura czerwiec 2018, informatyka rozszerzona
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 punktyAby 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.
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
za poprawną odpowiedź, w tym:
za prawidłowe zdefiniowanie warunków
za prawidłowe wywołania rekurencyjne
za podanie odpowiedzi błędnej albo brak odpowiedzi.
Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.