Fibonaççi ardıcıllığı (Həll təhlili)

Bu məsələdə $n$-ci Fibonacci ədədini tapmaq tələb olunur. n \le 40 olduqda rekursiv həll vaxtı ötmədən çalışacaq. Fibonacci ardıcıllığı belə görünür:

$type\text{int}$-də saxlanıla biləcək ən böyük Fibonacci ədədi

n \le 40 olduqda $type\text{int}$ verilənlər tipindən istifadə etmək kifayətdir.

Fərz edək ki, fib(n) funksiyası $n$-ci Fibonacci ədədini hesablayır. Onda belə bir rekursiv tənlik ortaya çıxır:

Alqoritmin realizasiyası

fib funksiyası $n$-ci Fibonacci ədədini 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, hesablayırıq və $fib(n)$ çıxış edir.

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

Java realizasiyası

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 realizasiyası — memoizasiya

fib funksiyası $n$-ci Fibonacci ədədini hesablayır.

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

Proqramın əsas hissəsi. Giriş dəyəri $n$ oxuyuruq.

n = int(input())

$dp$ siyahısını başlayırıq.

dp = (n + 1) * [-1]
dp[0] = 0
dp[1] = 1

Cavabı hesablayırıq və çıxış edirik.

print(fib(n))

Python realizasiyası — memoizasiya 2

arr = {}

fib funksiyası $n$-ci Fibonacci ədədini hesablayır.

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]

Proqramın əsas hissəsi. $n$ dəyərini oxuyuruq, hesablayırıq və $fib(n)$ çıxış edirik.

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

Python realizasiyası — memoizasiya 3

arr = {0:0, 1:1}

fib funksiyası $n$-ci Fibonacci ədədini hesablayır.

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

Proqramın əsas hissəsi. $n$ dəyərini oxuyuruq və $fib(n)$-ni çıxış edirik.

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

Python realizasiyası — TLE

fib funksiyası $n$-ci Fibonacci ədədini hesablayır.

def fib(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, hesablayırıq və $fib(n)$ çıxış edirik.

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