[python] 음수 피보나치 수열 (구현)

f(0) = 1, f(1) = 1

f(n) = f(n-1)+f(n-2)

위와 같은 조건을 만족하는 피보나치 수열이 있다고 가정하자.

위 공식을 통해 음수 또한 피보나치 수열을 만들 수 있다.

예를들어, f(1) = f(0) + f(-1)  f(-1) = f(1) - f(0) = 1을 구할 수 있다. 

입력된 숫자 번호에 해당하는 피보나치 수열을 문자열로 리턴하는 음수 피보나치 수열을 구현하라.

 

# 메모이제이션 사용 
#타겟 원소 
lst = [-5,-1,-10,-3,5,10,2]
box = [0]*100
box[1] = 1
minusBox = [0]*100
minusBox[-1] = 1
def fibo(n):
    for i in range(2, n+1):
        if box[i] != 0:
            continue
        else:
            box[i] = box[i-1] + box[i-2]
def minFibo(n):
    for i in range(-2,n-1,-1):
        if minusBox[i] != 0:
            continue
        else:
            minusBox[i] = minusBox[i+2] - minusBox[i+1]
            
# 타겟 원소에 해당하는 피보나치 수열 확인 
for data in lst:
    if data == 0 or data == 1:
        print(str(box[data]))
    elif data > 1:
        fibo(data)
        print(str(box[data]))
    else:
        minFibo(data)
        print(str(minusBox[data]))

# print(minusBox[-20:])
# print(box[:20])