Фібоначчі (#4730)

Аналіз алгоритму

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

Приклад

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

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

Числа Фібоначчі обчислимо в масиві 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];

// Читаємо вхідне значення n. Виводимо відповідь.
scanf("%d",&n);
printf("%d\n",fib[n]);

Реалізація з запам'ятовуванням

Оголосимо масив fib для запам'ятовування чисел Фібоначчі: fib[i] = f(i).

Рекурсивна функція f(n) знаходить $n$ -те число Фібоначчі.

#define MAX 46
int fib[MAX];

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

// Основна частина програми. Читаємо число n.
scanf("%d",&n);
// Присвоїмо значення -1 всім елементам масиву fib.
memset(fib,-1,sizeof(fib));
// Знайдемо та виведемо значення f(n)
printf("%d\n",f(n));