Ciąg Fibonacciego - zadanie

[nika88]

Witam,
mam prośbę, czy ktoś mógłby mi pomóc w rozwiązaniu zadania z algorytmów?
Oto treść zadania:
a. Wykaż, że F2n = Fn(Fn + 2 Fn–1)
b. Podaj podobną zależność dla F2n+1.
c. Korzystając z wyprowadzonych zależności, zaproponuj algorytm wyznaczania wartości Fn. Wyznacz
liczbę wykonanych mnożeń i dodawań w zależności od n.

[xiikzodz]

\(\displaystyle{ F_{2n+1}=F_{n+1}^2+F_n^2}\)
\(\displaystyle{ F_{2n}=F_nF_{n+1}+F_nF_{n-1}}\)

Oba wzory jednoczesnie dowodzimy przez indukcje:

Zakladamy, ze oba dzialaja dla pewnego \(\displaystyle{ n}\), pokazemy, ze rowniez dla \(\displaystyle{ n+1}\).

Krok indukcyjny dla \(\displaystyle{ 2n}\):

\(\displaystyle{ F_{2n+2}=F_{2n+1}+F_{2n}\stackrel{zal.ind.}{=}F_{n+1}^2+F_n^2+F_nF_{n+1}+F_nF_{n-1}}\)

\(\displaystyle{ =(F_{n+1}^2+F_nF_{n+1})+(F_n^2+F_nF_{n-1})=(F_{n+1}^2+F_nF_{n+1})+F_nF_{n+1}=}\)

\(\displaystyle{ =F_{n+1}F_{n+2}+F_{n+1}F_n}\)

czyli OK.

Teraz krok indukcyjny dla \(\displaystyle{ 2n+1}\) (wykorzystamy zalozenie ind. i wlasnie pokazany wzor dla \(\displaystyle{ F_{2n+2}}\)):

\(\displaystyle{ F_{2n+3}=F_{2n+1}+F_{2n+2}\stackrel{zal.ind.}{=}(F_{n+1}^2+F_n^2)+(F_{n+1}F_{n+2}+F_{n+1}F_n)=}\)

\(\displaystyle{ F_{n+1}^2 + F_{n+1}F_{n+2}+(F_n^2+F_{n+1}F_n)=F_{n+1}^2 + F_{n+1}F_{n+2}+F_nF_{n+2}=F_{n+1}^2+F_{n+2}^2}\)

co konczy dowod indukcyjny.

A teraz algorytm w stylu C (rekursja):

Kod: Zaznacz cały

int F(int n)
{
	if(!(n>1))
		return 1;	// F_0=F_1=1
	else if (!(n%2))	// n - parzyste
		return F(n/2)*(F(n/2-1)+F(n/2+1));
	else			// n - nieparzyste
		return F((n-1)/2)^2+F((n+1)/2)^2;
}

Zeby wyznaczyc \(\displaystyle{ F_n}\) wykonamy funkcje F

\(\displaystyle{ \mathcal{O}(\log n)}\)

razy. Dokladniej, wykonamy ja \(\displaystyle{ \log n + i}\)razy (czyli \(\displaystyle{ \log n + \mathcal{O}(1)}\)), gdzie \(\displaystyle{ i}\) jest niewielka liczba naturalna.

Kazde wykonanie kosztuje 1 mnozenie + 1 dodawanie, lub 2 mnozenia + 1 dodawanie. Stad oszacowanie na liczbe mnozen i dodawan tez wynosi

\(\displaystyle{ \mathcal{O}(\log n)}\),

a dokladniej niewiecej niz \(\displaystyle{ 2\log n + 2i}\) mnozen i niewiecej niz \(\displaystyle{ \log n + i}\) dodawan dla pewnej niewielkiej liczby naturalnej \(\displaystyle{ i}\).

[Fibik]

Fajna metoda obliczania liczb Fibonacciego, ale i tak szybciej będzie wyliczyć od razu:
\(\displaystyle{ F(n) = round(\frac{\sqrt{5}}{5}\cdot \phi^n)}\)
jedno potęgowanie, jedno mnożenie, oraz jedno zaokrąglenie do całości.