[Python] [ROSALIND] Rabbits and Recurrence Relations

문제

https://rosalind.info/problems/fib/

 

https://rosalind.info/problems/fib/

 

 

 

구글 번역기를 돌렸다 ㅋㅋ

 1202년에 피사의 레오나르도(일반적으로 피보나치로 알려짐)는 토끼 개체군의 번식에 관한 수학적 운동을 고려했습니다. 그는 인구에 대해 다음과 같은 단순화된 가정을 했습니다.

 인구는 첫 달에 한 쌍의 갓 태어난 토끼와 함께 시작됩니다. 토끼는 한 달 후에 생식 연령에 도달합니다. 주어진 달에 생식 연령의 모든 토끼는 생식 연령의 다른 토끼와 교미합니다. 두 마리의 토끼가 교미한 지 정확히 한 달 만에 수컷 한 마리와 암컷 한 마리를 낳습니다. 토끼는 죽거나 번식을 멈추지 않습니다.

 피보나치의 운동은 1년에 몇 쌍의 토끼가 남을 것인지 계산하는 것이었습니다. 두 번째 달에 첫 번째 토끼 쌍이 번식 연령에 도달하고 짝짓기를 하는 것을 볼 수 있습니다. 세 번째 달에 또 다른 한 쌍의 토끼가 태어나고 두 쌍의 토끼가 있습니다. 우리의 첫 번째 토끼 쌍이 다시 짝을 이룹니다. 네 번째 달에는 원래 쌍에서 또 다른 한 쌍의 토끼가 태어나고 두 번째 쌍은 성숙하여 짝짓기를 합니다(총 세 쌍). 토끼 개체군의 역학은 그림 1에 나와 있습니다. 1년 후 토끼 개체군은 144쌍을 자랑합니다.

 토끼의 불멸에 대한 피보나치의 가정은 다소 터무니없는 것처럼 보일 수 있지만 그의 모델은 육식 동물이 없는 환경에서 번식하기에는 비현실적이지 않았습니다. 유럽 토끼는 19세기 중반에 호주에 도입되었습니다. 50년 이내에 토끼는 이미 대륙 전역에서 많은 식물 종을 박멸하여 호주 생태계에 돌이킬 수 없는 변화를 일으키고 초원의 대부분을 현대 아웃백의 실질적으로 거주할 수 없는 침식된 부분으로 바꾸었습니다(그림 2 참조). 이 문제에서 우리는 토끼 수를 세는 간단한 아이디어를 사용하여 더 작은 솔루션에서 큰 솔루션을 구축하는 것과 관련된 새로운 계산 주제를 소개합니다.

 

problem의 맨 아랫 줄에 문제가 주어진다.

암수 한 쌍으로 시작해서, 1달에 k쌍 씩 낳을 때, n개월 후 토끼는 총 몇 쌍인지 구하는 문제이다.

주어진: 양의 정수 n≤40 및 k≤5. 반환:
n개월 후에 존재할 토끼 쌍의 총 수.
1쌍으로 시작하고 각 세대에서 번식 연령 토끼의 모든 쌍은 k 토끼 쌍(단 1쌍 대신)을 한 배씩 생산합니다.

 

k = 1 일 때 총 토끼 쌍은 피보나치 수열을 띤다.

k = 3일 때, 5번째 달에는 토끼가 몇 쌍 있을까?

일단 노가다로 확인해 봤다 ㅋㅋ

k=1일 때는 1, 1, 2, 3, 5.. 이던 수열이

k=3일 때는 1, 1, 4, 7, 19... 가 된다.

 

부모와 자식으로 나눠 보면, k=3일 때

 

첫째달 : 부모 한 쌍

둘째달 : 부모 한 쌍(생식 연령)

셋째달 : 부모 한 쌍 + 자식 세 쌍 - 총 네 쌍

넷째달 : 부모 한 쌍 + 첫 째 자식 세 쌍(생식 연령) + 둘 째 자식 세 쌍 - 총 일곱 쌍

다섯째달 : 부모 한 쌍 + 첫 째 자식 세 쌍 + 첫 째 자식이 낳은 자식 아홉 쌍 + 둘 째 자식 세 쌍 + 셋 째 자식 세 쌍 - 총 19 쌍

 

아마 태어나는 자식 수에 3만 곱하면 되는 것 같다?

 

피보나치 수열로 구현해 본다.

def fib_loop(month, k):
    old, new = 1, 1
    for i in range(1, month-1):
        print("{}째달".format(i), "토끼 쌍 : ", new)
        new, old = old, old + (new * k)
    return new

print(fib_loop(25, 3))

 

흑흑 답이 잘 나왔다!

다른 사람들은 어떻게 풀었는지 더 찾아봐야겠다.