Rosalind - Rabbits and Recurrence Relations

문제 풀이:

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

 

출처:https://earthteacher.tistory.com/44#gsc.tab=0

 

재귀식(recurrence relation) 이란 수열의 항 사이의 관계를 말한다.

다시 말해 반복해서 현재 값이 이전값을 반영하는 식을 말한다. 파보나치 수열의 경우,

1번째 항과 2번째 항을 더하면 3번째 항이 되고, 2번째 항과 3번째 항을 더하면 4번째 항이된다.

즉, n 번째 항 더하기 n+1 번째 항은 n+2 번째 항을 의미한다.  이를 본 문제에 적용하여 공식을 만들면,

 

Fn(n번째 달의 총토끼의 수) = F(n1) + F(n2)

 

파보나치 수열 공식

Fn = F(n1)+ F(n2)*k

 

코드: 

def rabbits(n, k):
    prev1 = 1
    prev2 = 1
    for i in range(2, n):
        current = prev1 + k * prev2
        prev2 = prev1
        prev1 = current
    return current

rabbits(5, 3)
#result
19