Fibonacci#4730

Fibonacci (Editorial)

Compute all Fibonacci numbers and store them in the $f ib$ array by assigning $f ib [i] = f (i)$ fib[i] = f(i). Then print the desired Fibonacci number.

Example

The $f ib$ array will be filled as follows:

Algorithm implementation

Compute the Fibonacci numbers and store them in the $f ib$ array: $f ib [i] = f (i)$ fib[i] = f(i).

#define MAX 46
int fib[MAX];

Fill the $f ib$ array according to the recursive formula.

fib[0] = 1; fib[1] = 1;
for (int i = 2; i < MAX; i++)
  fib[i] = fib[i-1] + fib[i-2];

Read the input value of $n$ . Print the answer.

scanf("%d",&n);
printf("%d\n",fib[n]);

Algorithm implementation — recursion

Declare the $f ib$ array to store Fibonacci numbers: $f ib [i] = f (i)$ fib[i] = f(i).

#define MAX 46
int fib[MAX];

The recursive function f computes the $n$ -th Fibonacci number. The memoization technique is used.

int f(int n)
{
  if (n <= 1) return 1;
  if (fib[n] != -1) return fib[n];
  return fib[n] = f(n-1) + f(n - 2);
}

The main part of the program. Read the value of $n$ .

scanf("%d",&n);

Assign the value of $- 1$ to all elements of $f ib$ array.

memset(fib,-1,sizeof(fib));

Compute and print the value $f (n)$ .

printf("%d\n",f(n));

Algorithm implementation — iteration

Read the input number $n$ .

scanf("%d", &n);

Handle the base case.

if (n == 0 || n == 1) 
{
  printf("1\n");
  return 0;
}

Let us assign:

the $0$ -th Fibonacci number to the variable $a$ ;
the $1$ -st Fibonacci number to the variable $b$ ;

Initially, the variables $a$ and $b$ contain two consecutive Fibonacci numbers.

a = b = 1;
for (i = 2; i <= n; i++) 
{

The variables $a$ and $b$ contain two consecutive Fibonacci numbers.

a = f (i - 2), b = f (i - 1)

a = f(i - 2), \\ b = f(i - 1)

Compute the next Fibonacci number:

c = a + b = f (i - 2) + f (i - 1) = f (i)

c = a + b = f(i - 2) + f(i - 1) = f(i)

  c = a + b;

Perform a shift, as a result of which $a = f (i - 1)$ a = f(i - 1) and $b = f (i)$ b = f(i).

  a = b;
  b = c;
}

Print the answer. The variable $b$ contains the value of $f (n)$ .

printf("%lld\n", b);

Java implementation

import java.util.*;

public class Main
{
  public static int MAX = 46;    
  static int fib[] = new int[MAX];    
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    fib[0] = 1; fib[1] = 1;
    for(int i = 2; i < MAX; i++)
      fib[i] = fib[i-1] + fib[i-2];
    System.out.println(fib[n]);
    con.close();
  }
}

Java

Java implementation — constant memory

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int a = 1, b = 1, temp;
    for(int i = 0; i < n; i++)
    {
      temp = a;    	
      a = b;
      b = temp + b;
    }
    System.out.println(a);     
    con.close();
  }
}

Java

Java implementation — recursion with memoization

import java.util.*;

public class Main
{
  static int fib[] = new int[46];    
  
  static int f(int n)
  {
    if (n <= 1) return 1;
    if (fib[n] != -1) return fib[n];
    return fib[n] = f(n-1) + f(n - 2);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    Arrays.fill(fib, -1);
    System.out.println(f(n));     
    con.close();
  }
}

Java

Python implementation — list

To store Fibonacci numbers, declare a list $f ib$ : $f ib [i] = f (i)$ fib[i] = f(i).

fib = [1,1]

Fill the $f ib$ array according to the recursive formula.

for i in range(2,46):
  fib.append(fib[i-1] + fib[i-2])

The main part of the program. Read the value of $n$ .

n = int(input())

Compute and print the value $f (n)$ .

print(fib[n])

Python implementation — constant memory

n = int(input())
a, b = 1, 1
for i in range(n):
  a, b = b, a + b
print(a)

Python implementation — memoization

To store Fibonacci numbers, declare a list $f ib$ : $f ib [i] = f (i)$ fib[i] = f(i).

fib = [-1] * 46

The recursive function f computes the $n$ -th Fibonacci number. The memoization technique is used.

def f(n):
  if n <= 1: return 1
  if fib[n] != -1: return fib[n]
  fib[n] = f(n - 1) + f(n - 2)
  return fib[n]

The main part of the program. Read the value of $n$ .

n = int(input())

Compute and print the value $f (n)$ .

print(f(n))