Фібоначчі#4730
Увійти

Фібоначчі (Розбір)

Обчислимо всі числа Фібоначчі і розмістимо їх в масиві , встановивши fib[i] = f(i). Потім виведемо необхідне число Фібоначчі.

Приклад

Масив буде заповнений наступним чином:

Реалізація алгоритму

Будемо обчислювати числа Фібоначчі і зберігати їх в масиві fib: fib[i] = f(i).

#define MAX 46
int fib[MAX];

Заповнюємо масив відповідно до рекурентної формули.

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

Читаємо вхідне значення . Виводимо відповідь.

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

Реалізація алгоритму — рекурсія

Для зберігання чисел Фібоначчі оголосимо масив fib: fib[i] = f(i).

#define MAX 46
int fib[MAX];

Рекурсивна функція f обчислює -те число Фібоначчі. Використовуємо техніку мемоізації.

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

Основна частина програми. Читаємо число .

scanf("%d",&n);

Присвоїмо всім елементам масиву значення .

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

Обчислюємо та виводимо значення .

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

Реалізація алгоритму — ітерація

Читаємо вхідне число .

scanf("%d", &n);

Обробляємо базовий випадок.

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

Занесемо:

Спочатку змінні і містять два послідовних числа Фібоначчі.

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

Змінні і містять два послідовних числа Фібоначчі:

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

Обчислюємо наступне число Фібоначчі:

c = a + b = f(i - 2) + f(i - 1) = f(i) 
  c = a + b;

Виконуємо зрушення, в результаті якого a = f(i - 1) і b = f(i).

  a = b;
  b = c;
}

Виводимо відповідь. Змінна містить значення .

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

Java реалізація

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 реалізація — константна пам'ять

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 реалізація — рекурсія з запам'ятовуванням

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 реалізація — список

Для зберігання чисел Фібоначчі оголосимо список fib: fib[i] = f(i).

fib = [1,1]

Заповнюємо список відповідно до рекурентної формули.

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

Основна частина програми. Читаємо число .

n = int(input())

Обчислюємо та виводимо значення .

print(fib[n])

Python реалізація — константна пам'ять

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

Python реалізація — запам'ятовування

Для зберігання чисел Фібоначчі оголосимо список fib: fib[i] = f(i).

fib = [-1] * 46

Рекурсивна функція f обчислює -те число Фібоначчі. Використовуємо техніку мемоізації.

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]

Основна частина програми. Читаємо число .

n = int(input())

Обчислюємо та виводимо значення .

print(f(n))