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

프로젝트 오일러 - 문제 2번

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

피보나치 수열이란? 첫 번째 원소와 두 번째 원소의 합은 세 번째 원소가 되고, 두 번째 원소와 세 번째 원소의 합은 네 번째가 된다. 이것이 계속 반복된다.

피보나치(Fibonacci) 수열의 각 항은 바로 앞의 항 두 개를 더한 것입니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 4백만 이하의 짝수 값을 갖는 모든 피보나치 항을 더하면 얼마가 됩니까?

해결 방법

def solution(a, b, limit):
    numbers = [a, b]
    result = []
    
    if a % 2 == 0:
        result.append(a)
        
    if b % 2 == 0:
        result.append(b)

    i = 0
    while True:
        res = numbers[i] + numbers[i+1]
        
        if res > limit:
            break
        
        numbers.append(res)
        
        if res % 2 == 0:
            result.append(res)
        
        i += 1
        
    return sum(result)
    
print(solution(1, 2, 4000000)) # 4613732

개선된 코드

(프로젝트 오일러 다른이의 코드를 보고) 배열을 안써도 되는구나! 평가항목도 줄어들고, 변수도 바꿔쓰니 훨씬 좋은 알고리즘인듯

def solution(a, b, limit):
    sum = 0
    
    while a < limit:
        if b % 2 == 0:
            sum += b
            
        num = a + b        
        a = b
        b = num
        
    return sum
    
print(solution(1, 2, 4000000))

프로젝트 오일러에 있는 다른이의 코드중에서

cap = 4000000
i = 2 #current fib num
j = 1 #previous fib num
sum = 0

while i < cap:
	if(i % 2 == 0): #Only sum even values of fibinnaci
		sum += i; #sum current i

	#i Calc and Var Swap
	temp = i #hold i temporarily
	i += j #calculate new fib num
	j = temp #update j to old i

print(sum)