Fibonaççi#4730

Fibonaççi (Həll təhlili)

Bütün Fibonacci ədədlərini hesablayıb onları $f ib$ massivinə yerləşdiririk, burada $f ib [i] = f (i)$ fib[i] = f(i). Sonra tələb olunan Fibonacci ədədini çıxarırıq.

Nümunə

$f ib$ massivi aşağıdakı kimi doldurulacaq:

Alqoritmin Tətbiqi

Fibonacci ədədlərini hesablayıb onları $f ib : f ib [i] = f (i)$ fib: fib[i] = f(i) massivində saxlayacağıq.

#define MAX 46
int fib[MAX];

Rekursiv düsturdan istifadə edərək $f ib$ massivini dolduraq.

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

Giriş dəyəri $n$ -i oxuyuruq. Cavabı çıxarırıq.

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

Alqoritmin Tətbiqi — Rekursiya

Fibonacci ədədlərini saxlamaq üçün $f ib : f ib [i] = f (i)$ fib: fib[i] = f(i) massivini elan edəcəyik.

#define MAX 46
int fib[MAX];

Rekursiv f funksiyası $n$ -ci Fibonacci ədədini hesablayır. Məzmun yaddaşına almanın texnologiyasından istifadə olunur.

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

Proqramın əsas hissəsi. $n$ sayını oxuyuruq.

scanf("%d",&n);

$f ib$ massivinin bütün elementlərinə $- 1$ dəyəri veririk.

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

$f (n)$ dəyərini hesablayıb çıxarırıq.

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

Alqoritmin Tətbiqi — Iterasiya

Giriş sayını $n$ oxuyuruq.

scanf("%d", &n);

Əsas halı işləyirik.

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

Qeyd edək:

$a$ dəyişənində sıfırıncı Fibonacci ədədini;
$b$ dəyişənində birinci Fibonacci ədədini;

Əvvəldən $a$ və $b$ dəyişənləri iki ardıcıl Fibonacci ədədidir.

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

$a$ və $b$ dəyişənləri iki ardıcıl Fibonacci ədədini saxlayır:

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

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

Növbəti Fibonacci ədədini hesablayırıq:

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;

Siçra edirik ki, nəticədə $a = f (i - 1)$ a = f(i - 1) və $b = f (i)$ b = f(i) olur.

  a = b;
  b = c;
}

Cavabı çıxardırıq. $b$ dəyişəni $f (n)$ dəyərini saxlayır.

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

Java İcraatı

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 İcraatı — Sabit yaddaş

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 İcraatı — Rekursiya ilə yadda asılması

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 İcraatı — Siyahı

Fibonacci ədədlərini saxlamaq üçün $f ib : f ib [i] = f (i)$ fib: fib[i] = f(i) siyahısını elan edəcəyik.

fib = [1,1]

Rekursiv düsturdan istifadə edərək $f ib$ siyahısını dolduraq.

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

Proqramın əsas hissəsi. $n$ sayını oxuyuruq.

n = int(input())

$f (n)$ dəyərini hesablayıb çıxarırıq.

print(fib[n])

Python İcraatı — Sabit yaddaş

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

Python İcraatı — Yadda müəllimlik

Fibonacci ədədlərini saxlamaq üçün $f ib : f ib [i] = f (i)$ fib: fib[i] = f(i) siyahısını elan edəcəyik.

fib = [-1] * 46

Rekursiv f funksiyası $n$ -ci Fibonacci ədədini hesablayır. Yadda müəllimlik texnikasından istifadə olunur.

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]

Proqramın əsas hissəsi. $n$ sayını oxuyuruq.

n = int(input())

$f (n)$ dəyərini hesablayıb çıxarırıq.

print(f(n))