Problem 2 : 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합

프로그래밍 공부를 위해 Projetct Euler의 문제 풀이를 연습하는 내용입니다.
문제(problem), 제 답변(answer), 추천하는 타인 답변(solution)으로 구성되어 있습니다.
기본적으로 풀이는 R을 사용하였지만, 일부 연습을 위해 Python으로도 구현해 보았습니다.

Problem

• 번호 : 2
• 제목 :
  피보나치 수열에서 4백만 이하이면서 짝수인 항의 합
• 설명 :
  피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.
  1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
  짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까?

Answer & Solution - R

• 피보나치 수열을 구하는 함수를 구현 : 특정 값까지 바로 앞의 항 두 개 합산

• 1과 2는 대상에 포함되지 않으므로 계산에 포함되지 않음

• 3부터는 앞에 두 개 항 합산 : sum[i-1]+sum[i-2]

• input 으로 받은 값까지 반복하다가 input 값보다 커지게 되면 짝수(sum %% 2 == 0)만 합산하여 출력

• code : R 코드

# Answer

problem2 <- function(a) {
  sum = vector()

  for (i in 1:a) {

    if (i < 3) {
      sum = c(sum, i)
    } else {
      sum_tmp = sum[i - 1] + sum[i - 2]

      if (sum_tmp < a) {
        sum = c(sum, sum_tmp)
        # cat(i, "|", sum, "\n")
      } else {
        sum_even = sum(sum[sum %% 2 == 0])

        return(sum_even)
      }  
    }
  }
}

problem2(4000000)
## 4613732

# Solution

fib <- function(n){
  if(n == 1) return(1)
  if(n == 2) return(2)

  return(fib(n-2)+fib(n-1))
}

x = 1
sum = 0

while (fib(x) < 4000000){
  if (fib(x) %% 2 == 0){
    sum = sum + fib(x)
    x = x + 1
  }
}

print(sum)    
## 4613732

Answer & Solution - Python

• code : Python

# Answer

import numpy as np

def problem2(a):
    sum = []
    for i in range(0, a):
        if i < 2:
            sum.append(i+1)

        else:
            sum_tmp = sum[i-1] + sum[i-2]
            if sum_tmp < a:
                sum.append(sum_tmp)
            else:
                # print(i, sum)
                sum_even = np.sum(num for num in sum if num % 2 == 0)

                return sum_even

print(problem2(4000000))

## 4613732

# Solution

def fib(n):
    if n == 1: return 1
    if n == 2: return 2
    return fib(n-2) + fib(n-1)

x = 1
sum = 0

while fib(x) < 4000000:
    if fib(x) % 2 == 0:
        sum += fib(x)
    x += 1

print(sum)

# 4613732

System Info.

PyCharm 2019.1 EAP (Community Edition)
Build #PC-191.6014.12, built on March 6, 2019
JRE: 11.0.2+159 amd64
JVM: OpenJDK 64-Bit Server VM by JetBrains s.r.o
Windows 7 6.1
R version 3.5.2 (2018-12-20)
Python 3.6.6
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows 7 x64 (build 7601) Service Pack 1
RStudio version 1.1.463