Basecamp
    Home
    Problems
    Contests
    Courses
    Ranking
    Posts
4730
Fibonacci
Sign in
StatementDiscussionEditorial

Algorithm Analysis

We will compute all Fibonacci numbers in the array fib, setting fib[i] = F(i). Then we will output the required Fibonacci number.

Example

The array fib will be filled as follows:

Fibonacci

Algorithm Implementation

We will compute Fibonacci numbers in the array fib: fib[i] = F(i).

#define MAX 46
int fib[MAX];

// Fill the array according to the recurrence 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 n. Output the answer.
scanf("%d",&n);
printf("%d\n",fib[n]);
C
11 lines
258 bytes

Implementation with Memoization

Declare the array fib for memorizing Fibonacci numbers: fib[i] = f(i).

The recursive function f(n) finds the n-th Fibonacci number.

#define MAX 46
int fib[MAX];

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);
}

// Main part of the program. Read the number n.
scanf("%d",&n);
// Assign the value -1 to all elements of the array fib.
memset(fib,-1,sizeof(fib));
// Find and output the value f(n)
printf("%d\n",f(n));
C
16 lines
354 bytes
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
18 lines
413 bytes
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
19 lines
381 bytes
Java Implementation – Recursion, TLE
import java.util.*;

public class Main
{
    static int f(int n)
    {
        if (n <= 1) return 1;
        return f(n-1) + f(n - 2);
    }

    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        int n = con.nextInt();
        System.out.println(f(n));
        con.close();
    }
}
Java
18 lines
331 bytes
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
22 lines
448 bytes
Python Implementation with List
fib = [1,1]
for i in range(2,46):
    fib.append(fib[i-1] + fib[i-2])
n = int(input())
print(fib[n])
Python Implementation with Constant Memory
n = int(input())
a, b = 1, 1
for i in range(n):
    a, b = b, a + b
print(a)
Python Implementation with Memoization
fib = {0:1,1:1}
n = int(input())
for i in range(2,n+1):
    fib[i] = fib[i-1] + fib[i-2]
print(fib[n])
Python Implementation – Function with Memoization
fib = {0:1,1:1}
def fibon(n):
    if not n in fib:
        fib[n] = fibon(n-1) + fibon(n-2)
    return fib[n]

n = int(input())
print(fibon(n))
Python
8 lines
144 bytes
Loading...
Loading...