31.5 심사문제 : 재귀호출로 피보나치 수 구하기

코딩도장 심사문제모음

codermun 2020. 11. 4. 16:42

728x90

표준 입력으로 정수 한 개가 입력됩니다(입력 값의 범위는 10~30). 다음 소스 코드를 완성하여 입력된 정수에 해당하는 피보나치 수가 출력되게 만드세요.

피보나치 수는 0과 1로 시작하며, 다음 번 피보나치 수는 바로 앞의 두 피보나치 수의 합입니다.

사용한 코드

1. def

2. if

3. return

0, 1로 시작하는점

호출하는 인수의 개수가 "하나"인점

수열의 일정 규칙이 있다는점을 파악하여 문제를 해결 할 수 있다.

코드를 작성하기 전 문제부터 살펴보자

입력값 n 과 결과값을 나열하여 수열이라 생각해 관계를 살펴보자.

# n

# 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21...

# 결과

# 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946...

문제에서도 제시해주지만 0, 1 시작 후 2부터는 바로 두 앞의 수의 합이 결과로 반환되는점이다.

1. 함수 정의를 할때 피보나치의 수는 0과 1로 시작한다는 점을 잊지말자.

0 과 1 의 입장에서 볼 경우

if a<0 , return이 재귀호출 종료 함수로도 볼 수 있다.

def fib (a):
    if a < 2 :
        return a

2. 위의 결과를 얻기 위해선 실제적으로 a = 2인 경우 부터 그 전의 두값을 더해가면서부터 시작된다.

이를 수식으로 정리해보면 좀 더 이해가 쉽다.

## n = 값에 따라 반환 값을 정리해보자

## 0 일때는 0 반환 / f0

## 1 일때는 1 반환 / f1

## 2 일때는 1 반환 / f0+ f1 = f2

## 3 일때는 2 반환 / f1+ f2 = f3

## 4 일때는 3 반환 / f2+ f3 = f4

## 5 일때는 5 반환 / f3+ f4 = f5

# n = a 일때의 반환 값을 f(a) 라 하면 위와 같이 나타낼수 있다.

## n = 2 라면 f2 = f(2-1) + f(2-2)

f(1) + f(0)

## n = 3 라면 f3 = f(3-1) + f(3-2)

f(2) + f(1)

## n = 4 라면 f4 = f(4-1) + f(4-2)

f(3) + f(2)

## n = 5 라면 f5 = f(5-1) + f(5-2)

f(4) + f(3)

## 결국 재귀호출 사용시 바로 앞 두 값의 합을 return해주면 문제 해결이 가능하다.

def fib (a):
    if a < 2 :
        return a
    return fib(a-2) + fib(a-1)
    
n = int(input())
pritn(fib(b))

※ 실제 코딩 도장의 해법과 다를 수 있으며, 답은 여러가지가 존재합니다.

코드 지적 정말 감사히 받겠습니다.

728x90