파이썬 피보나치 함수 비재귀함수로 푸는 법
조회수 1334회
def fibo(n):
a = 1
b = 1
if n <= 2:
return 1
else:
while n > 2:
if a <= b:
a = a + b
else:
b = a + b
return a + b
n = int(input())
x = fibo(n)
print(x)
n을 입력받아 n번째 피보나치 수를 리턴해서 출력하려하는데요. 재귀함수 안쓰고 변수와 while문 만으로 풀려는데, a와 b가 피보나치 수를 저장할 변수인데 while문에서 a와 b의 값을 증가시키는 방법은 알겠는데 n이 증가할수록 그 두개의 값을 더한 값을 구하는걸 잘 모르겠습니다.
1 답변
-
피보나치 수열의 성질을 다시 잘 읽고 함수를 짜보니 재귀 없는 피보나치 코드는 좀 tricky한 부분이 한 군데 있네요. 본인의 코드와 비교해 보면서 왜 이게 작동하는지 한번 연구해 보세요.
def fibo(n) : # 기본 상태를 정의한다. 제 0항은 0이고 제 1항은 1이다. # 여기서 b는 "마지막으로 구한 항", a는 "두 번째 마지막으로 구한 항"이다. a = 0 b = 1 # 현재 우리는 제 1항을 구한 상태이다. SequenceNo = 1 # b가 제 n항이 될 때까지: while SequenceNo < n : # b를 변화시키기 전의 값을, 별도 변수에 저장해 둔다. lastB = b # b에 a를 더한다. 이제 b는 변화된 b이다. b += a # a를, 변화되기 전의 b로 바꿔준다. # 이렇게 해야 다음 while이 실행될 때 b += a 연산이 의도한 대로 동작한다. a = lastB # 다음 항을 처리할 준비를 한다. SequenceNo += 1 # 여기까지 왔으면 이제 b는 제 n항의 값이다. 출력하고 끝. return b # 테스트 print(fibo(7)) # 13 print(fibo(12)) # 144
댓글 입력