Darmowe konto pozwoli wrócić do niego później.
Polecenie
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)² − (Fk−1)²
F2k−1 = (Fk)² + (Fk−1)²
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.
Darmowe konto pozwoli wrócić do niego później.
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.
za poprawną odpowiedź, w tym:
za prawidłowe zdefiniowanie warunków
za prawidłowe wywołania rekurencyjne
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.