프로젝트 오일러 #2 피보나치 수열의 짝수항 합

 

C/C++ 언어를 배우다보면, 꼭 한번은 프로그램해보는 것이 있다면, 피보나치 수열일거라 생각합니다.  피보나치 수열은 재귀함수를 사용한 곳에서도 많이 나오지만, 동적 프로그램이 필요한 예로도 자주 사용됩니다.

 

피보나치 수열은 한쌍의 토끼의 개체수 증가라는 퀴즈 형태에서 출발한 것인데요.  꼭 토끼가 아니라도 대장균의 증식같은 데에서도 응용할 수 있습니다.  기하함수로 증가하는 곡선을 보이게 됩니다.

 

피보나치는 아주 간단한 점화식을 이용합니다.

 

\[ F_{n} = F_{n-1} + F_{n-2} \]

 

점화식을 보면 아주 간단한 형태입니다.  전항과 전전항을 더한 값이 현재항의 값이 됩니다.

 

그래서  첫번째 항과 두번째 항이 초기값으로 주어져야 합니다.  첫번째 항은 1, 두번째 항은 1입니다.  자연수 범위안에서 피보나치 수열은 진행합니다.  확장해서 음수항을 만들기도 하지만, 여기서는 양수항만을 다루도록 할께요.

 

간단한 점화식을 사용하지만, 일반항을 구하는 방법은 좀 까다롭습니다.  수학적 방법론이 어떻게 나왔는가는 여기서 중요하지 않으니, 그것은 생략하고요.  일반항을 구하는 방법을 제 식으로 표현하면 다음과 같습니다.

 

\[ F_{n} = F_{n-1} + F_{n-2} \]

\[ z^2 = z + 1 \]

\[ (z-\alpha)(z-\beta)=0 \]

 

위와 같이 만들면, 우리는 서로 다른 두개의 해를 구할 수 있습니다.  해는 2차방정식의 근의 공식을 이용하면 손쉽게 구할 수 있습니다.  그 해는 우리가 흔히 말하는 황금비율값입니다.  그래서 더 피보나치 수열이 유명해졌는지도 모르겠네요.  (그 외에 피보나치 소수도 있고요.)

 

\[ z = \frac{1 \pm \sqrt{1^2 + 4}}{2} = \frac{1 \pm \sqrt{5}}{2} = \phi , 1 - \phi \]

 

이 값이 결정되면, 우리는 피보나치의 일반항을 구할 수 있습니다.

피보나치 일반항을 홤금비를 이용해서 표현하면 다음과 같습니다.

 

\[ F_n = \frac{1}{\sqrt{5}} ( \phi^n - (1-\phi)^n ) \]

 

만약 프로그램에서 큰 수에 대한 피보나치 항을 구하라는 것이 있다면, 위의 일반항 공식을 이용해서 풀어주는 것이 필요합니다.

 

피보나치 일반항을 구하는 프로그램은 INT64 범위 안에서는 다음과 같이 표현할 수 있습니다만, double을 쓴 관계로 실제 큰 수에 대해서는 오차가 발생할 수 있습니다.

 

long long fib(int n)
{
    double v = (pow(1+sqrt(5), n) - pow(1-sqrt(5), n))/pow(2.0, n)/sqrt(5);
    return (long long)(v+0.5);
}

 

 

오일러 프로젝트 2번은 사실 일반적인 방법의 피보나치 방법을 이용하는 것이 편합니다.  조금 빠르게 하고 싶다면, 다음과 같은 것을 이용하시면 됩니다.  피보나치의 짝수값을 갖는 항은 매 3번째 항마다 발생합니다.  (홀수 + 홀수 = 짝수 이므로)

 

그러므로 원래의 피보나치 점화식을 이용해서 우리는 다음과 같은 새로운 피보나치 점화식을 유도할 수 있습니다.

 

\[ F_{3m} = 4 F_{3m-3} + F_{3m-6} \]

 

이것을 이용해서 프로그램을 짜면 다음과 같이 됩니다.

 

 

  int f1 = 2, f2 = 8;
  sum = 2;
  while( f2 <= 4000000 )
  {
     sum += f2;
     int t = f1+4*f2;
     f1 = f2;
     f2 = t;
  }
  printf("sum is %d\n", sum);

 

 

오일러 프로젝트에 있는 문제에서는 그다지 효율적으로 나아지지는 않겠지만요.