Fibonaççi Ədədi#2292
Daxil ol

Fibonaççi Ədədi (Həll təhlili)

Mündəricat n ≤ 10^4 olduğuna görə, -in hesablanması üçün ya uzun arifmetika istifadə etməli, ya da məsələn, Java və ya Python proqramlaşdırma dillərindən istifadə etməliyik.

Fibonaccinin -dən 10^4-ə qədər olan ədədlərini hesablayıb massivində saxlayırıq. Daha sonra hər bir giriş qiyməti üçün elementini çıxarırıq.

Java tətbiqi

import java.util.*;
import java.math.*;

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

Java tətbiqi – yadda saxlanıla rekursiya

import java.util.*;
import java.math.*;

public class Main
{
  static BigInteger fib[] = new BigInteger[10001];    
  static BigInteger MUNIS1 = new BigInteger("-1");

  static BigInteger f(int n)
  {
    if (n <= 2) return BigInteger.ONE;
    if (fib[n].compareTo(MUNIS1) != 0) return fib[n];
    return fib[n] = f(n-1).add(f(n - 2));
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    for(int i = 0; i < 10001; i++) fib[i] = MUNIS1;
    int tests = con.nextInt();
    for(int i = 0; i < tests; i++)
    {
      int n = con.nextInt();
      System.out.println(f(n));      
    }
    con.close();
  }
}
Java

Python tətbiqi

İlk iki Fibonacci ədədini initilize edirik: F(1) = 1. F(2) = 1.

f1, f2 = 1, 1

Fibonacci ədədlərini saxlayacağımız siyahısını yaradırıq. F(0) = 0 dəyərini xüsusilə əlavə edirik ki, indeksləmə məsələnin şərti ilə uyğunlaşsın.

fib = [0, f1, f2]

-yə qədər Fibonacci ədədlərini hesablayırıq.

for i in range(10000):
  add = f1 + f2
  fib.append(add)
  f1, f2 = f2, add

Testlərin sayını oxuyuruq.

t = int(input())
for i in range(t):

Giriş dəyərini oxuyub -ı çıxarırıq.

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