memorization / 피보나치 수열

 순환을 이용한 피보나치 수열

같은 계산을 또 하지 않기 위해 F배열에 값을 메모한다.

 

#include <stdio.h>
#include <stdlib.h>
 
int fib(int n, int* F) {
    if (n == 1 || n == 2)
        return 1;
    if (F[n - 1] == 0)
        F[n - 1] = fib(n - 1, F);
    if (F[n - 2] == 0)
        F[n - 2] = fib(n - 2, F);
    printf("%d ", F[n - 1] + F[n - 2]);
    return F[n - 1] + F[n - 2];
}
 
int main(void)
{
    int n, i;
    int *F;
  
 
    printf("몇 번째까지의 피보나치 수열:");
    scanf("%d", &n); //fn
 
                    
    F = (int*)malloc(sizeof(int)*(n + 1));
                    
    for (i = 0; i < n; i++)
        F[i] = 0;
                 
    fib(n, F);
}