[Algorithm/C] Project Euler. Even Fibonacci Numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 1, the first 10 terms will be:

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

#include <stdio.h>

int Fibonacci(int n);

int main(int argc, char * argv[])

{

int sum = 0;

int i=0;

for(i=0; Fibonacci(i)<=4000000;i++)

{

if(Fibonacci(i)%2 == 0)

sum += Fibonacci(i);

}

printf("4,000,000 보다 작은 피보나치 수열의 짝수의 합은 : %d\n",sum);

}

int Fibonacci(int n)

{

if(n==0)

return 1;

else if(n==1)

return 1;

else

return Fibonacci(n-1) + Fibonacci(n-2);

}

접근 방법

1. 누구나 생각할 수 있는 재귀함수와 조건,반복문을 이용한 코드

*Project Euler에서 제시한 수학적 분석에 의한 코드

실제로 돌려보면 실행시간 차이가 엄청납니다.

원리는 모임때 발표

#include <stdio.h>

int Fibonacci(int n);

int main(int argc, char * argv[])

{

int sum = 0;

int i=0;

for(i=0; Fibonacci(i)<=4000000;i++)

{

if(Fibonacci(i)%2 == 0)

sum += Fibonacci(i);

}

printf("4,000,000 보다 작은 피보나치 수열의 짝수의 합은 : %d\n",sum);

}

int Fibonacci(int n)

{

if(n==0)

return 2;

else if(n==1)

return 8;

else

return 4*Fibonacci(n-1) + Fibonacci(n-2);

}

문제 출처 - https://projecteuler.net/problem=2