[ Project Euler With Python ] 2. Even Fibonacci numbers

원문 : Even Fibonacci numbers

---

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

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

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

피보나치 수열의 각 항은 이전의 두 항을 더함으로써 생성됩니다. 1 과 2 에서 시작해서, 처음 10 개의 항은 다음과 같습니다:

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

피보나치 수열에 있는 400 만을 초과하지 않는 값들을 고려할 때, 짝수값을 가진 항들의 합을 구하십시오.

문제 의도 해석

피보나치 수열에서 어떤 항은 앞의 두 수를 더해서 나온 것입니다.

• 3 = 1 + 2
• 5 = 2 + 3
• 8 = 5 + 3
• ...

문제에서는 짝수값만 더하라는 것이죠. 위의 예에서는 2 + 8 + 34 = 44 가 됩니다.

print_fibonacci function

일단 피보나치 수열의 값을 출력하는 함수를 만들어 보았습니다. 재귀적으로 호출하는 형식입니다. 단 100 을 넘지 않는 값을 출력하도록 했죠.

def print_fibonacci( a, b, max_term ) : if b > max_term : print( a ) return print( a ) print_fibonacci( b, a + b, max_term )

이를 실행하면 다음과 같은 결과가 나오죠.

물론 재귀 함수가 아니라 for 문을 통해서 구현하는 것도 가능합니다.

def print_fibonacci_with_while( a, b, max_term ) : a_val = a b_val = b while( b_val <= max_term ) : print( a_val ) temp = a_val a_val = b_val b_val = temp + b_val print( a_val )

sum_fibonacci function

이제 이 결과를 합쳐 보겠습니다. 결과를 더하는 건 결국 출력하는 순서와 동일하게 더해 가는 겁니다. 그런데 문제는 함수 내에서 a + b 가 발생하면, 다음 재귀 함수에서 b + next_term 를 하기 때문에( a' 로서 b, b' 로서 next_term, 그러므로 b 누적 ) 요소가 한 번씩 누적될 수 있다는 겁니다. 이에 주의해야 합니다.

def sum_fibonacci( a, b, max_term ) : if b > max_term : return a return a + sum_fibonacci( b, a + b, max_term )

sum_even_fibnoacci function

이제 문제의 의도대로 짝수값만 더하는 함수를 만듭니다. 임시 변수를 만들어서 홀수인 경우에는 0 취급을 해 주면 기존의 함수의 형태에서 크게 달라지지 않습니다.

def sum_even_fibonacci( a, b, max_term ) : a_val = 0 if ( a % 2 ) else a # a_val = ( a % 2 ) ? 0 : a if b > max_term : return a_val return a_val + sum_even_fibonacci( b, a + b, max_term )

파이썬 삼항 연산자가 좀 맘에 안 들기는 하지만, 어쨌든 비슷한 형태가 나옵니다.

4,000,000 까지의 피보나치 수열의 짝수항들을 더한 결과는 4613732 입니다.

More Efficient Method?

근데 재귀함수의 복잡도는 O( n ) 보다는 무조건 크게 나오는 것으로 보입니다; O( logn ), O( n^2 ), O( n^3 ). 그러므로 가급적이면 O( n ) 이 나오는 whlie 문을 사용하는 것이 좋을 것같습니다.

그런데 O( 1 ) 상수복잡도를 가지는 식은 없을까요? 왠지 불가능할 것 같습니다. 혹시 알고 계시다면 제보를 부탁드립니다.

우리는 짝수가 "홀수와 홀수" 혹은 "짝수와 짝수"를 더했을 때 나온다는 것을 알고 있습니다. 그래서 이를 이용해서 뭔가 간단한 규칙을 만들어 보려고 했습니다만, 어떻게 해야 할지 모르겠더군요. 그런데 이미 이걸 하신 분이 있더군요( F3 부터 세 번째 항들( F6, F9, ... )이 짝수라는 겁니다 ). 

"홀수 + 홀수 = 짝수" 이고 짝수 앞뒤에는 항상 홀수가 오니까 세 번째마다 반복되는 것으로 보입니다. 물론 이분은 "1, 1" 에서 시작하는 피보나치 수열을 가지고 계산한 것입니다.

이 분의 최종 코드는 다음과 같습니다( C# 으로 구현한 겁니다. 정확한 방식에 대해 알고자 하신다면 MathBlog 의 [ Project Euler - Problem 2 ] 를 참조하시기 바랍니다 ).

long[] fib = {2,0}; int i = 0; long summed = 0; while (fib[i] < 4000000) { summed += fib[i]; i = (i + 1) % 2; fib[i] = 4 * fib[(i + 1) % 2] + fib[i]; }

Where is Fibonacci Sequences?

피보나치 수열은 황금비를 형성한다고 합니다. [ 왜 자연은 피보나치 수열과 황금비를 택했을까 ] 를 읽어 보시면 재밌습니다. 엄청나게 세부적인 설명을 보려면 [ Fibonacci Numbers and Nature ] 라는 글을 참고하시면 좋습니다.