파이썬 - 피보나치 함수 / 프로젝트 오일러 2번 문제

피보나치 수열은 첫번째 항의 값이 0이고 두번째 항의 값이 1이며,

이후에 이어지는 항은 이전의 두 항을 더한 값으로 이루어지는 수열입니다.

0, 1, 1, 2, 3, 5, 8, 13, ...

 

아래 연습문제를 통해 피보나치 수열에 대해 자세히 배워보았습니다. 

 

---

 

< 연습문제 1 >

filter 함수를 이용하여 아래 피보나치 수열에서 2의 배수를 출력해보시오.

Fibo_seq = [0, 1, 1, 2, 3, 5, 8, 13, 23]

Fibo_seq = [0, 1, 1, 2, 3, 5, 8, 13, 23]
list(filter(lambda x: x % 2 == 0, Fibo_seq))

결과값: [2, 8]

 

 

< 연습문제 2 >

정수 하나를 넘겨주면 그 정수번째의 피보나치 수열을 리턴해 주는 함수를 작성하시오.

def fibonacci(num):
    if num == 1 or num == 2:
        return 1
    return fibonacci(num-1) + fibonacci(num-2)

 

 

결과값:

fibonacci(8)을 입력했을 때 결과값은 21이 나오는 것을 확인할 수 있습니다.

 

풀이해석:

def fibonacci(num):
    if num == 1 or num == 2: 
        return 1   #1번째와 2번째의 피보나치 값은 각각 1 
    return fibonacci(num-1) + fibonacci(num-2) #피보나치 값은 이전의 두 항을 더한 값
																						   #fibonacci 함수 반복
print(fibonacci(8))

 

 

 

< 연습문제 3 (프로젝트 오일러 2번) >

피보나치(fibonacci) 수열의 각 항은 바로 앞의 항 두개를 더한 것입니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다. 4백만 이하의 짝수 값을 갖는 모든 피보나치 항을 더하면 얼마가 되는가?

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

i = 2
j = 1
sum = 0

while i< 4000000:
    if i % 2 == 0:
        sum += i

    temp = i 
    i += j
    j = temp

print(sum)

결과값: 4613732

 

풀이해석:

i = 2
j = 1
sum = 0

while i< 4000000:
    if i % 2 == 0:
        sum += i

    temp = i #temp라는 임시 함수에 i 저장
    i += j #i에 i와 j의 합 저장
    j = temp #j에 temp 값 저장(= 이전 i 값)

print(sum)