프로젝트 오일러 002

안녕하세요 DEV



프로젝트 오일러는 내가 시작하고 싶어하는 일련의 도전적인 수학/컴퓨터 프로그래밍 문제입니다. 나는 배울 것이 많을 것이라고 확신하며 여기 DEV에서 내 솔루션을 공유하고 싶습니다.

❓ 문제 002는 다음과 같습니다.

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.



💡 이 문제를 해결하기 위해 Modulo 연산과 Addition의 조합을 사용할 수 있습니다.

❗ 프로그래밍에서 피보나치 수열 또는 기타 유사한 개념으로 작업할 때 생각할 수 있는 첫 번째 솔루션은 다음과 같습니다.
재귀적 접근. 그러나 우리는 항상 이러한 함수가 수천 번 호출될 수 있다는 것을 기억해야 합니다.
오류와 같은 것 중 하나Maximum call stack size exceeded에 직면하게 될 것입니다!

이것은 💀 이러한 알고리즘의 공간 복잡성( Have a 👀 at this article on this topic ) 때문에 발생하므로 여기서는 대신 반복적 접근 방식을 사용합니다.

피보나치 수열의 공식은 다음과 같습니다.

fib(n) = fib(n-1) + fib(n-2) → for n > 1
fib(n) = 1 → for n = 0, 1


다음과 같은 변수가 있다고 가정할 수 있습니다.

MAX = 4000000

first_number = 1
second_number = 1

sum = 0


그런 다음 2개의 다른 변수에 단순히 저장하는 이전 용어로 모든 다음 용어를 계산하여 답을 계산합니다!
그런 다음 짝수를 필터링하고 모두 합산합니다.

💻 따라서 Python에서 내 솔루션은 다음과 같습니다.

while second_number <= MAX:
    temp = second_number
    second_number += first_number
    first_number = temp

    if second_number % 2 == 0:
        sum += second_number
print(sum)


이것은 이 문제에 대한 최선의 답은 아니지만 이 문제에 대해 32개의 숫자(홀수도 포함됨)만 계산합니다.
재귀 접근 방식보다 훨씬 낫습니다. 홀수를 전혀 계산하지 않는 방법을 찾을 수 있다면 분명히! 저것
완벽한 개선이 될 것입니다. 이에 대한 아이디어가 있는지 빨리 보고 싶습니다.

✅ 이 문제의 정답은 4613732 입니다.

감사합니다 ❤️



프로그래밍의 세계를 처음 접하는 사람이나 궁금한 사람 🧐에게 제 게시물이 도움이 되었으면 합니다!
내용이 유용하다고 생각되면 의견을 댓글로 남겨주세요. 여러분 모두에게서 배우고 싶습니다.

당신의 사랑의 지시에 감사드립니다.

좋은 웹페이지 즐겨찾기