ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1133. Fibonacci Sequence

I've passed 1133 using c++
Posted by BFL 29 May 2005 14:34
my idea :
typical sequence

i      1 2 3 4 5 6 7
fib(i) 1 1 2 3 5 8 13

assume that i<=j
first, we have to find f(i+1)

diff=j-i
using F(i+1)=Fj/fib(diff) - Fi*fib(diff-1)/fib(diff)

but my prog didn't compute fib(i) but only computed
1/fib(i)  and  fib(i-1)/fib(i)

using formular
1/fib(i) = 1/(1/fib(i-1)+1/fib(i-2))
double f1(int ind)// return 1/fib(ind)
{
    int i;
    double a[3]={1,1};
    for(i=2;i<ind;i++)
        a[i%3]=1/(1/a[(i+1)%3]+1/a[(i+2)%3]);
    return a[(ind -1)%3];
}

fib(i-1)/fib(i) using this relation
1+1/(1+1/(1+1/...))
double f2(int ind)// return fib(ind-1)/fib(ind)
{
    int i;
    double ret=1;
    for(i=0;i<ind-2;i++)
        ret=1/(ret+1);
    return ret;
}

using this procedure, we can store any computation with
double and avoid int overflow.

and so the F(i+1) = (Fj*f1(diff)-Fi*f2(diff)), then find f(n) with ordinary algo using int(it said that fk can store in INT) !!