Fibonacci,wonderful series.

Computer Science Level 3

S=1+1+2+3+5+8+............up to 70th term

Find the sum of last two digites of S

18 13 8 9 6 10 11

Golam Mohammad Kibria by Golam Mohammad Kibria , 26, Bangladesh

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Relevant wiki: Subroutines 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include<bits/stdc++.h>
using namespace std;

long long R[9999999];

long long fibo(long long n){    
    if(R[n]==-1)
        R[n]=fibo(n-1)+fibo(n-2);
    return R[n];
}
int main(){

long long m,sum=0;  

    cin>>m;
    memset(R,-1,sizeof R);
        R[1]=1;R[2]=1;
    for(int i=1;i<=m;i++) sum=sum+fibo(i);

    cout<<sum<<endl;

}

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Bill Bell
Sep 26, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
def Fib():
    f0=1
    yield 1,f0
    f1=1
    yield 2,f1
    n=2
    while True:
        n+=1
        f0,f1=f1,f0+f1
        yield n,f1

total=0
for n,f in Fib():
    total+=f
    if n==70:
        print str(total)[-2:]
        break

1 Helpful 0 Interesting 0 Brilliant 0 Confused

@Bill Bell I had written the following code :

def fib(n): 

if n<2: return n

else: return fib(n-1)+fib(n-2)

sum =0

n = 1

while n<=33: 

sum = sum+fib(n)

n = n+1

print sum

But it is taken enormous amounts of time.How can i reduce the time?

Anik Mandal - 5 years, 3 months ago

Log in to reply

There are a few ways, one of which is used in the code I presented above. Another way would be to use memoisation. But I still prefer the essential idea in that code above because it avoids recursion.

Notice in your code how when n>=2 you call fib recursively. This means that fib will call itself over and over again until n is reduced to a value less than two. And it means that as n rises the code recalculates some terms in the sequence many, many times. Expensive! And you do it twice.

But to calculate one term in the Fibonacci sequence you need to know only the preceding two terms. Here's a simple way to express that idea. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
def Fib(f0,f1):
    fib=f0+f1
    return (f1,fib)

f0=0
f1=1
sum=1
print (1,f1)
for n in range(69):
    f0,f1=Fib(f0,f1)
    sum+=f1
    print (n+2,f1)

print (sum)

Each time I call Fib I pass it the preceding two terms of the sequence and it gives me back the immediately preceding term and the new term. Just what I need to calculate the next term. Since this approach is not recursive I'm calculating terms just once.

Bill Bell - 5 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...