프로젝트 오일러(Project Euler) 2번문제

Problem 2

피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까?

풀이

  피보나치 수열을 프로그래밍 언어로 구현할 때 크게 두가지가 있는데, while문이나 for문을 사용하는 방법이 있고 재귀함수를 사용하여 구현하는 방법이 있다. 반복문을 사용해서 바로바로 더해가는 것이 재귀함수를 사용하는 것보다 빠르지만, 갑자기 재귀함수가 써보고 싶어서 재귀함수로 구현하였다. 아직까진 머리를 쓰는 것보다는 손 스트레칭하는 듯한 난이도...

int fibo(int i)
{
    int num = i + 1;
 
    if (num <= 1) return num;
 
    else return fibo(num - 2) + fibo(num - 3);
}
 
void main()
{
    int sum = 0, num = 0, i = 2;
 
    while (1)
    {
        num = fibo(i);
        if (num > 4000000) break;
 
        sum += num;
 
        i += 3;
    }
    printf("%d\n", sum);
}

결과

  재귀함수로 만들어서 그런가 확실히 속도가 많이 느리긴 했다. 한 1초? 가까이 걸린것 같다.