피보나치 예제

작성한 질문수 23

0

제가 풀이한 내용이 도움이 될지는 모르겠지만 공유드립니다.

if(n<=1){

return n;을 통해 입력값 i(0 ~ 9)까지 순서대로 입력되는데, 0과 1은 return n을 통해 0과 1이 출력됩니다.

이후 입력값 2부터는 n<=1이 거짓이되기 때문에

return fibo(n-1) + fibo(n-2)를 수행하게 되는데, 입력값 2를 입력하게 되면

fibo(2-1) + fibo(2-2), 즉 fibo(1) + fibo(0)을 수행하게 되서 1이 리턴되게 됩니다.

i = 2, 출력값 1

i = 3, fibo(3-1) + fibo(3-2), fibo(2) + fibo(1) // fibo(2) = 1, fibo(1) = 1, 출력값 = 2

i = 4, fibo(4-1) + fibo(4-2), fibo(3) + fibo(2) // fibo(3) = 2, fibo(2) = 1, 출력값 = 3

i = 5, fibo(5-1) + fibo(5-2), fibo(4) + fibo(3) // fibo(4) = 3, fibo(3) = 2, 출력값 = 5

i = 6, fibo(6-1) + fibo(6-2), fibo(5) + fibo(4) // fibo(5) = 5, fibo(4) = 3, 출력값 = 8

i = 7, fibo(7-1) + fibo(7-2), fibo(6) + fibo(5) // fibo(6) = 8, fibo(5) = 5, 출력값 = 13

i = 8, fibo(8-1) + fibo(8-2), fibo(7) + fibo(6) // fibo(7) = 13, fibo(6) = 8, 출력값 = 21

i = 9, fibo(9-1) + fibo(9-2), fibo(8) + fibo(7) // fibo(8) = 21, fibo(7) = 13, 출력값 = 34

도움이 되셨으면 좋겠네요.

0

안녕하세요,

우선, 풀이를 설명하기 전에 앞에 5까지 맞았으면, 뒤가 틀릴 수가 없습니다.

왜냐하면 식 자체가 자기보다 하나 1이 작은 수, 2가 작은 수를 더해서 호출하기 때문입니다.

계산식이 잘못되었다면 애초부터 잘못된 값이 산출되었어야 합니다.

해설:

편의상 함수를 f()라고 정의하고 사용하겠습니다.

f(6)에 대해서 질문 주신 것으로 알고 설명드립니다.

f(6)은 f(5) + f(4)로 쪼개집니다.

f(4)는 나중에 처리하는 것으로 하고, f(5) 먼저 같이 해보시죠. ----- 책갈피

f(5)는 다시 f(4) + f(3)으로 쪼개집니다.

f(4) = f(3) + f(2)

f(3) = f(2) + f(1) 이 됩니다.

이를 다시 나누면

f(4) = f(2) + f(1) + f(2) = f(1) + f(0) + f(1) + f(1) + f(0) = 3

f(3) = f(1) + f(0) + f(1) = 2가 됩니다.

이것 두개를 합치는 것이 f(5)가 되었으니 5가 되는 것이고,

f(4)는 위에서 확인한 것처럼 3이었습니다.

이 둘을 더해야했기 때문에 (윗 부분 책갈피) 총 8이 산출됩니다.

질문 감사합니다.