[Project Euler] Problem 2

원문: Problem 2

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, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

피보나치 수열의 각각의 새로운 항은 이전의 두 항을 더한 것에 의해 생성된다. 1 과 2로 생성되는 첫번째 10 개의 항은 다음과 같다. :

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

4백만을 초과하지 않는 수열 내에서 짝수 값을 갖는 모든 항의 합을 구하여라.

Python

>>> sum = 0
>>> a, b = 1, 2
>>> while b <= 4000000 :
    if b%2 == 0 :
        sum += b
    a, b = b, a+b
else :
    print(sum)

접기

처음에는 이렇게 했다가 게시글을 보니까 좀 더 수학적 방법을 사용해서 풀 수도 있다.

Python 2

짝수는 홀수의 합 또는 짝수의 합으로 이루어지므로, 피보나치 수열에서 짝수가 나오는 경우는 2, 5, 8, 11 ... 번째 마다 나오게 된다. 이것을 점화식으로 나타내면 a_n = 3a_n-3 + 2a_n-4, a_n-1 = 2a_n-3 + a_n-4 가 된다. 즉, 짝수 번째의 값과 그 이전 값만 알면 다음 짝수 번째의 값도 바로 알 수가 있다.

>>> a = 1
>>> b = 2
>>> sum = 0
>>> while b <= 4000000 :
    sum += b
    a, b = 2*b+a, 3*b+2*a
else :
    print(sum)

접기

ps.
게시글을 보다 보니까 J나 K 언어를 보면 참 대단하다는 생각이 든다.