Problem_002_Even Fibonacci numbers

[그림 01] Problem 002 문제

문제를 살펴보면 다음과 같습니다.

문제 이름 : 짝수 피보나치 숫자들

문제 내용 : 각 단계마다 피보나치가 생성되는데, 피보나치의 다음 단계는 두 개의 단계(번째)를 더하여 생성됩니다. 1과 2로 시작하여 10단계를 생성해보면 다음과 같이 생성됩니다.

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

이제 이를 고려하여 4,000,000(4백만, 4million)을 넘지 않는 각 단계를 계속 생성할 때, 생성된 값이 짝수들인 단계를 모두 더한 값을 구하십시오.

우리는 다음과 같은 조건을 가진다는 것을 알 수 있습니다.

1. 피보나치의 원리를 이용하여 다음 단계를 계속 생성함

2. 생성된 단계가 400만을 넘지 않아야 함

3. 생성된 값 중 짝수인 것을 모두 더해야 함

이제 소스코드를 작성해보도록 합시다.

#Project Euler Problem 002
#Python 3 version source
#even-valued terms' Sum value --> 짝수의 값으로 나오는 term을 모두 더함

def Define_Fibonacci(ex_number, number):	#피보나치 생성함수
	next_number = ex_number + number
	return number, next_number

def Even_Value_Sum(Fibo_list):		        #짝수 값을 구분하여 더함
	Even_Fibo_Sum = 0
	for i in range(len(Fibo_list)):
		if Fibo_list[i] % 2 == 0:
			Even_Fibo_Sum += Fibo_list[i]
	return Even_Fibo_Sum

if __name__ == "__main__":
	Fibonacci_Limit = 4000000       #피보나치 값이 넘지 않아야 할 한계값
	Fibonacci_Sum = 0               #피보나치 짝수 값을 더할 변수
	Fibonacci_List= [1,2]           #피보나치 배열
	i = 0
	
	while True:
		main_num, main_next_num = Define_Fibonacci(Fibonacci_List[i],Fibonacci_List[i+1])
		if main_next_num <= Fibonacci_Limit: #피보나치 값이 한계값을 넘지 않으면 피보나치 배열에 추가함
			Fibonacci_List.append(main_next_num)
		else:	                               #400만을 넘는 값이 생성되면 출력하고 종료
			print("Even Fibo Sum : ", Even_Value_Sum(Fibonacci_List))
			break
		i += 1                 #While문의 횟수를 표시
	#print(Fibonacci_List)   #피보나치 배열을 출력할 수 있음

위의 소스는 문제를 해결하는 소스입니다.

먼저 메인에서는 한계값을 지정한 변수, 더해줄 변수, 피보나치 배열을 선언합니다.

그리고 While 무한 반복으로 피보나치 단계 중 400만이 넘는 값이 나오기 전까지 반복해줍니다.

Define_Fibonacci를 통해 다음 피보나치 단계를 생성하고, Even_Value_Sum을 통해 피보나치 리스트에 있는 값 중 짝수 값을 골라 더해주고, 이를 반환해줍니다.

그리고 이외에 홀수, 그리고 피보나치 배열의 모든 값을 더하는 기능을 추가한 소스는 다음과 같습니다.

#Project Euler Problem 002
#Python 3 version source
#even-valued terms' Sum value --> 짝수의 값으로 나오는 term을 모두 더함

def Define_Fibonacci(ex_number, number):
	next_number = ex_number + number
	return number, next_number

def Even_Value_Sum(Fibo_list):
	Even_Fibo_Sum = 0
	for i in range(len(Fibo_list)):
		if Fibo_list[i] % 2 == 0:
			Even_Fibo_Sum += Fibo_list[i]
	return Even_Fibo_Sum

def Odd_Value_Sum(Fibo_list):
	Odd_Fibo_Sum = 0
	for i in range(len(Fibo_list)):
		if Fibo_list[i] % 2 == 1:
			Odd_Fibo_Sum += Fibo_list[i]
	return Odd_Fibo_Sum
	
def Whole_Value_Sum(Fibo_list):
	Whole_Fibo_Sum = 0
	for i in Fibo_list:
		Whole_Fibo_Sum += i
	return Whole_Fibo_Sum
	
if __name__ == "__main__":
	Fibonacci_Limit = 4000000
	Fibonacci_Sum = 0
	Fibonacci_List= [1,2]
	i = 0
	
	while True:
		main_num, main_next_num = Define_Fibonacci(Fibonacci_List[i],Fibonacci_List[i+1])
		if main_next_num <= Fibonacci_Limit:
			Fibonacci_List.append(main_next_num)
		else:
			print("Even Fibo Sum : ", Even_Value_Sum(Fibonacci_List))
			print("Odd Fibo Sum  : ", Odd_Value_Sum(Fibonacci_List))
			print("Whole Fibo Sum: ", Whole_Value_Sum(Fibonacci_List))
			break
		i += 1
	#print(Fibonacci_List)	

늘 느끼는 거지만, 저보다 잘하는 사람은 늘 있습니다.
출처 : http://www.s-anand.net/euler.html

cache = {}     #dict == dictionary 형태의 타입 // type(cache) == 'dict'
def fib(n):
	cache[n] = cache.get(n, 0) or (n <= 1 and 1 or fib(n-1) + fib(n-2))
	return cache[n]

n = 0
i = 0

while fib(i) <= 4000000:
    if not fib(i) % 2: n = n + fib(i)
    i = i + 1

print(n)