2. Even Fibonacci numbers

문제에 대한 설명은 이곳에서 확인할 수 있다. 

먼저 직관적으로 떠오르는 방식으로 구현하고 이를 ver 1.0이라고 하자.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

# ver 1.0   a_n2 = 1 a_n1 = 2 answer = a_n1 # since 2 is even   while True:           a_n = a_n1 + a_n2           if a_n > 4000000: break       if a_n % 2 == 0 : answer += a_n           a_n1, a_n2 = a_n, a_n1   print answer

문제를 풀고 사람들의 풀이를 보니 더 나은 방법이 있다는 것을 알게 되었다. 이를 소개한다. 

먼저 수열의 시작을 1, 1로 바꾸자.^[각주:1] 이렇게 바꾸면 매 3번째 수가 짝수가 되어 계산을 줄일 수 있다.

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

$n$번째 피보나치 수열을 $f(n)$이라고 한다면 피보나치 수열의 성질에 의하여 다음이 성립한다.

$f(n)=f(n-1)+f(n-2)$
     $=f(n-2)+f(n-3)+f(n-3)+f(n-4)$
     $=f(n-3)+f(n-4)+f(n-3)+f(n-3)+f(n-5)+f(n-6)$
     $=4f(n-3)+f(n-6)$

위의 식을 이용한 방법을 ver 2.0이라고 하자.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

# ver 2.0   a = 2 b = 8 answer = a + b   c = 4*b +a   while c < 4000000:       answer += c           a, b = b, c           c = 4*b +a   print answer

답은 4613732이다. 사람들의 생각이 놀랍다.

1. 이렇게 바꾸어도 문제의 답은 바뀌지 않는다. 왜냐하면 수의 크기에만 관심이 있기 때문이다. [본문으로]