11123. Fibonacci [MWP4_2A]

Zadanie:
https://pl.spoj.com/problems/MWP4_2A

Skrócony opis problemu:

Mając daną liczbę $x$ należy znaleźć 2 pierwsze liczby ciągu Fibonacciego, który kończy się właśnie liczbą $x$, ale jest możliwie najdłuższy. Jeśli jest wiele ciągów o tej samej długości, to należy wybrać ten o najmniejszym pierwszym elemencie.

Rozwiązanie naiwne:

Dla każdej pary liczb mniejszych od $x$ sprawdzić czy ciąg Fibonacciego zaczynający się od nich kończy się liczbą $x$. Sprawdzamy to obliczając kolejne liczby ciągu i jeśli któraś liczba przekroczy $x$ to znaczy, że dana para początkowych liczb ciągu nie jest tą właściwą. Jeśli natomiast któraś liczba będzie równa $x$ to sprawdzamy długość tego ciągu (liczymy ją na bieżąco) i jeśli jest większa niż maksymalna, którą mieliśmy to aktualizujemy ową maksymalną i zapamiętujemy te pierwsze 2 wyrazy. Jeśli jest długości są równe, to porównujemy też wielkość pierwszych wyrazów i wybieramy parę z mniejszym pierwszym wyrazem.

Złożoność: $O(x^2 \log_{\varphi} x)$ (przy $\varphi = \frac{1+\sqrt{5}}{2}$). Wynika ona z tego, że par liczb z przedziału $\left<0;x\right>$ jest x^2, a dla każdej pary obliczamy kolejne liczby ciągu aż dojdziemy do $x$. Ich z kolei jest $n$. Największą długość ma oryginalny ciąg Fibonacciego (zaczynający się od 0 i 1), a wzór na $n$-ty wyraz ciągu to (ze wzoru Bineta):

$$F_n \approx \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n$$

Nasze $x$ to właśnie $F_n$, więc wychodzi nam $x = \frac{1}{\sqrt{5}} \varphi^n$. Po pominięciu stałych wychodzi: $x = \varphi^n$. Otrzymujemy więc: $n = \log_{\varphi} x$. Po przemnożeniu wychodzi $x^2 \cdot \log_{\varphi} x$.

Rozwiązanie sprytne:

Aby to szybciej obliczyć możemy skorzystać z wcześniej wspomnianej liczby phi ($\varphi$), czyli złotego podziału. Dzięki wzorowi Bineta możemy obliczyć $n$-tą liczbę Fibonacciego w czasie stałym (zakładając oczywiście, że potęgowanie jest wykonywane w czasie stałym). W nim potęgujemy liczbę $\varphi$. Możemy więc otrzymać następną liczbę Fibonacciego mnożąc poprzednią przez $\varphi$. Okazuje się, że działa to nie tylko dla oryginalnego ciągu Fibonacciego, ale też dla zaczynających się od dowolnej pary liczb. Adam umieścił dowód w komentarzu. My chcemy jednak otrzymać liczbę, która była przed $x$. Dzielimy więc $x$ przez $\varphi$ i patrzymy co mamy.

Np. dla $x = 10$ otrzymujemy: $\frac{10}{\varphi} \approx 6.18$. Po zaokrągleniu otrzymamy 6. Idąc od tyłu otrzymujemy: 10, 6, 4, 2, 2, 0. Jak się okazuje jest to najdłuższy taki ciąg z najmniejszym pierwszym elementem. Wynik dla tego przykładu to zatem: "0 2".

Złożoność: $O(\log_{\varphi} x)$.

Ostateczny algorytm:

int main()
{
    int x, y;
    get(x);
    y = round(x/1.618033989);
    while(y <= x)
        y = x-y,
        x -= y;
    print(x, x+y);
}