fibonacci numbers

1# Easy fibonacci exercise
2# Method #1
3def fibonacci(n):
4    # 1th: 0
5    # 2th: 1
6    # 3th: 1 ...
7    if n == 1:
8        return 0
9    elif n == 2:
10        return 1
11    else:
12        return fibonacci(n - 1) + fibonacci(n - 2)
13
14# Method #2
15def fibonacci2(n):
16    if n == 0: return 0
17    n1 = 1
18    n2 = 1
19    # (1, n - 2) because start by 1, 2, 3... not 0, 1, 1, 2, 3....
20    for i in range(1, n - 2):
21        n1 += n2
22        n2 = n1 - n2
23    return n1
24
25
26print(fibonacci(13))
27# return the nth element in the fibonacci sequence

10, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

1def fibonacci(n):
2    if n <= 0:
3        return 0
4    elif n == 1:
5        return 1
6    else:
7        return fibonacci(n-1) + fibonacci(n-2)

1
2
3def fib(n):
4  lisp = []
5  
6  for i in range(n):
7    if len(lisp) < 3:
8      if len(lisp) == 0:
9        lisp.append(0)
10      else:
11        lisp.append(1)
12    
13    else:
14      lisp.append(lisp[len(lisp)-1]+lisp[len(lisp)-2])
15  
16  return lisp

1f(n) = f(n-1) + f(n-2) 
2                                  f(6)
3                                   ^
4  			                       /\
5                f(5)               +                       f(4)
6                ^
7               /\                                           /\
8                
9        f(4)    +           f(3)                     f(3)    +    f(2)
10       ^                       ^                     ^              ^
11      /\                       /\                    /\            /\
12   
13 f(3)   +       f(2)            f(2) +f(1)       f(2) + f(1)   f(1) +  f(0)             
14   ^              ^                ^                ^
15   /\             /\                /\              /\
16    
17f(2) + f(1)      f(1) +  f(0)     f(1)+ f(0)       f(1) + f(0)         
18  ^
19  /\
20f(1) +  f(0) 
21  
22//f(6) = 8   ==>  f(1)*8    f(1) appears 8 times 
23 double feb  = (1/Math.pow(5,0.5)) * (Math.pow((1+Math.pow(5,0.5))/2,n)) - (1/Math.pow(5,0.5))* (Math.pow((1-Math.pow(5,0.5))/2,n));  
24  
25f(1) == 1;   
26  
27  
28  
29  
30  
31  
32  

1//using dp, top -down approach memoization
2#include <iostream>
3
4using namespace std;
5int arr[1000];
6int fib(int n)
7{
8    if(arr[n]==0)
9    {
10        if(n<=1)
11        {
12            arr[n]=n;
13        }
14        else
15        {
16            arr[n]=fib(n-1)+fib(n-2);
17        }
18    }
19    return arr[n];
20}
21
22int main()
23{
24    int n;
25    cout<<"enter the value of which fibonacci value you want to calculate:"<<endl;
26    cin>>n;
27    int f=fib(n);
28    cout<<"fib value is: "<<f<<endl;
29    return 0;
30}
31