Fibonaççi ardıcıllığı (#3258)

Alqoritm Analizi

Tapşırıq $n$ -ci Fibonacci rəqəmini tapmaqdır. $n \leq 40$ üçün, rekursiv həyata keçirilmə müddət baxımından keçəcək. Fibonacci ardıcıllığı aşağıdakı kimidir:

int tipinə sığan ən böyük Fibonacci rəqəmi $f_{46} = 1836311903$ -dür. $n \leq 40$ üçün, int tipindən istifadə etmək kifayətdir.

fib(n) funksiyası $n$ -ci Fibonacci rəqəmini hesablasın. Onda aşağıdakı təkrarlanan əlaqəyə sahibik:

$f ib (n) = ⎩ ⎨ ⎧ 01 f ib (n - 1) + f ib (n - 2) əgər n = 0 əgər n = 1 əks halda$

Alqoritm Həyata Keçirilməsi

fib funksiyası $n$ -ci Fibonacci rəqəmini hesablayır.

int fib(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

Proqramın əsas hissəsi. $n$ dəyərini oxuyuruq və fib(n)-i çıxarırıq.

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

Java Həyata Keçirilməsi

import java.util.*;

public class Main
{
    static int f(int n)
    {
        if (n == 0) return 0;
        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();
    }
}

Python Həyata Keçirilməsi – Memoizasiya

fib funksiyası $n$ -ci Fibonacci rəqəmini hesablayır.

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

n = int(input())
dp = (n + 1) * [-1]
dp[0] = 0
dp[1] = 1
print(fib(n))

Python Həyata Keçirilməsi – Memoizasiya 2

arr = {}

def fib(n):
    if (n == 0): return 0
    if (n == 1): return 1
    if n not in arr:
        arr[n] = fib(n - 1) + fib(n - 2)
    return arr[n]

n = int(input())
print(fib(n))

Python Həyata Keçirilməsi – Memoizasiya 3

arr = {0: 0, 1: 1}

def fib(n):
    if arr.get(n) is None:
        arr[n] = fib(n - 1) + fib(n - 2)
    return arr[n]

n = int(input())
print(fib(n))

Python Həyata Keçirilməsi – TLE

fib funksiyası $n$ -ci Fibonacci rəqəmini hesablayır.

def fib(n):
    if (n == 0): return 0
    if (n == 1): return 1
    return fib(n - 1) + fib(n - 2)

n = int(input())
print(fib(n))