파이썬 피보나치 함수 비재귀함수로 푸는 법

조회수 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 답변

  • 좋아요

    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
    
    • 아 감사합니다 막히던 부분이 해결되었네요 그런데 SequenceNo를 쓰지 않고 n만으로도 할 수 있나요? 그 부분이 저는 생각이 잘 안됐어서요 심윤보 2019.9.13 21:29
    • 일반항이 있기는 합니다. nowp 2019.9.15 23:30

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)