[fibonacci] 피보나치 [C 언어]

피보나치 지긋지긋하다.

#include 
#include 
// 피보나치 수열

long long fibo(int n)
{
  if (n == 1 || n == 2) {
    return 1;
  }
  
  return fibo(n-1) + fibo(n-2);
}

// cache
#define MAXSIZE 100
long long fibo2(int n) {
  static long long cache[MAXSIZE];
  
  if (cache[n])
    return cache[n];
    
  if (n == 1 || n == 2)
    // cache[n] = 1;
    return cache[n] = 1;
    
  // cache[n] = fibo2(n-1) + fibo2(n-2);
  return cache[n] = fibo2(n-1) + fibo2(n-2);
}

// 재귀 없이 풀기
long long fibo3(int n) {
  int i;
  long long f_res, f_a, f_b;
  
  if (n == 1 || n == 2)
    return 1;

  // f(3) = f(2) + f(1);
  // f(n) = f(n-1) + f(n-2)
  f_a = 1;
  f_b = 1;
  for (i = 3; i <= n; ++i) {
    f_res = f_a + f_b;
    f_a = f_b;
    f_b = f_res;
  }
  
  return f_res;
}


int main(void) {
  printf("Hello World\n");
  // printf("%lld\n", fibo(100)); 
  printf("%lld\n", fibo2(100));
  printf("%lld\n", fibo3(100)); 
  return 0;
}