fibonacci

1# WARNING: this program assumes the
2# fibonacci sequence starts at 1
3def fib(num):
4	"""return the number at index `num` in the fibonacci sequence"""
5    if num <= 2:
6        return 1
7    return fib(num - 1) + fib(num - 2)
8
9# method 2: use `for` loop
10def fib2(num):
11	a, b = 1, 1
12	for _ in range(num - 1):
13		a, b = b, a + b
14	return a
15
16
17print(fib(6))  # 8
18print(fib2(6))  # same result, but much faster

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

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  

1import java.util.Scanner;
2public class Fibonacci 
3{
4    public static void main(String[] args) 
5    {
6        int n, a = 0, b = 0, c = 1;
7        Scanner s = new Scanner(System.in);
8        System.out.print("Enter value of n:");
9        n = s.nextInt();
10        System.out.print("Fibonacci Series:");
11        for(int i = 1; i <= n; i++)
12        {
13            a = b;
14            b = c;
15            c = a + b;
16            System.out.print(a+" ");
17        }
18    }
19}

1// program to generate fibonacci series up to n terms
2
3// take input from the user
4const number = parseInt(prompt('Enter the number of terms: '));
5let n1 = 0, n2 = 1, nextTerm;
6
7console.log('Fibonacci Series:');
8
9for (let i = 1; i <= number; i++) {
10    console.log(n1);
11    nextTerm = n1 + n2;
12    n1 = n2;
13    n2 = nextTerm;
14}Copied

1Each test case will contains a single integer n where n >=1.
2

1                         fib(5)   
2                     /                  
3               fib(4)                fib(3)   
4             /                      /     
5         fib(3)      fib(2)         fib(2)    fib(1)
6        /             /           /      
7  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
8  /    
9fib(1) fib(0)
10