책 이야기

작아지지 않는 정수의 수열인 a_n은 다음 과정을 통해 양의 실수 θ에서 만들어 낼 수 있다.

    b₁=θ

    b_n=└b_n-1┘(b_n-1-└_bn-1┘+1) , n>=2일 때

    a_n=└b_n┘

└ ┘은 버림을 나타낸다.

예를 들어, θ=2.956938891377988...는 피보나치 수열(2, 3, 5, 8, 13, 21, 34, 55, 89, ...)를 생성한다.

양의 정수의 수열인 a_n을 연결하면, τ로 표기하는 a₁에서 시작해서 소숫점 아래의 연속된 요소를 결합한 a₁.a₂a₃a₄...모양의 실수가 된다.

예를 들어, θ=2.956938891377988...에서 나오는 피보나치 순열을 연결하면 τ=2.3581321345589...가 되며, θ 값에 대해 θ와 τ는 다르다.

a₁=2에서 시작해서 수열을 결합했을 때 τ=θ가 되는 유일한 값 θ를 찾으시오. 답안은 반올림하여 소숫점 24자리까지 구하시오.

--------------------------------------------------------------------------

처음에는 고민을 많이 하고 접근했는데, 생각보다 어렵지 않게 해결 가능했다.

처음에는 θ=2로 시작해서, 공식을 소숫점 25자리까지 반복 적용해서 나온 숫자(τ)를 다시 θ로 설정하는 작업을 τ=θ가 나올때까지 반복하면 되는데 몇 번 반복하지 않고 답을 구할 수 있었다.

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

    F₁ = 1

    F₂ = 1

    F₃ = 2

    F₄ = 3

    F₅ = 5

    F₆ = 8

    F₇ = 13

    F₈ = 21

    F₉ = 34

    F₁₀ = 55

    F₁₁ = 89

    F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

피보나치 배열은 회귀하는 관계로 정의된다:

F_n = F_n−1 + F_n−2,  F₁ = 1이고 F₂ = 1.

따라서, 처음 12개 요소는 F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, F₆ = 8, F₇ = 13, F₈ = 21, F₉ = 34, F₁₀ = 55, F₁₁ = 89, F₁₂ = 144가 된다.

12번째인 F₁₂는 처음으로 3자리 숫자가 되는 요소이다.

처음으로 1000자리 숫자가 되는 요소는 몇번째인가인가?

--------------------------------------------------------------------------

재귀함수를 배울 때 가장 많이 사용되는 예시가 피보나치 수열이다. 이 문제는 특정 피보나치 수를 구하는 것이 아니라 일정 조건을 만족하는 피보나치 수를 찾는 문제이기 때문에 재귀함수 보다는 반복문이 더 적절한 것으로 판단되었다.

계속 얘기하지만 파이썬이 큰 숫자도 간단히 다룰 수 있게 구현되어 있기 때문에, 까다롭지 않게 해결 가능했다.

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.

피보나치 순열에서 새 항은 이전 두 항을 합해서 구해진다. 1과 2로 시작하면 첫 10개 항은 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...가 된다.

피보나치 순열에서 4백만이 넘지 않는 항 중 짝수인 항의 합계를 구하시오.

--------------------------------------------------------------------------

피보나치 순열 새 항의 값이 4백만 이하인 동안, 짝수인 항을 더해서 답을 구하면 된다. 변수 4개로 답을 구하는 것이 더 간단하지만, 리스트를 활용해서 답을 구했다.