10870번, 피보나치 수 5

https://www.acmicpc.net/problem/10870

이 문제는 n을 주면, n번째 피보나치 수를 구하는 문제이다.

우선 이전에 풀었던 문제인 팩토리얼 2를 응용해서 풀거기 때문에, unsigned long int는 그대로 사용하겠다.

---

우선 기본 라이브러리를 불러온다.

#include <stdio.h>

---

재귀 함수를 이용해서 풀거기 때문에, fibonaci함수를 생성한다. (a와 b는 이전에 있던 숫자들이다.)(만약 C++이라면, 첫 a와 b를 기본 값으로 설정할 수 있다. a = 0, b = 0)

unsigned long int fibonaci(int n, int a, int b);

---

함수 내에서는 n이 0이면 0을 리턴하고, n이 3보다 작으면 a+b를 리턴하고, 전부 아니면 fibonaci(n-1, b, a+b)를 리턴한다.

if (n == 0){
    return 0;
}else if (n < 3){
    return a+b;
}else {
    return fibonaci(n-1, b, a+b);
}

만약 n이 4라면, (a와 b는 추후 계산을 위해서 필요한 것이기 때문에, 각각 0과 1로 고정하겠다.)

n은 0이 아니고, 3보다 작지 않기 때문에, fibonaci(n-1, b, a+b)를 리턴한다. 리턴하기 전, fibonaci(n-1, b, a+b)를 계산한다.

fibonaci(n-1, a, b)(n=3, a=1, b = 1)에서 n은 0이 아니고, 3보다 작지 않기 때문에 fibonaci(n-1, b, a+b)를 리턴한다. 리턴하기 전, fibonaci(n-1, b, a+b)를 계산한다.

fibonaci(n-1, a, b)(n=2, a=1, b = 2)에서 n은 0이 아니지만, 3보다 작기 때문에 a+b = 3을 리턴한다.

fibonaci(n-1, a, b)(n=3, a=1, b=1)에서 fibonaci(2, 1, 2) = 3의 값을 그대로 리턴한다.

fibonaci(n-1, a, b)(n=4, a=0, b=1)에서 fibonaci(3, 1, 1) = 3의 값을 그대로 리턴한다.

따라서 n이 4일때 피보나치의 값은 3이다.

---

main함수에서 scanf로 n을 입력 받고, printf로 피보나치 함수의 결과를 출력한다.

int main(){
    int n;
    scanf("%d", &n);
    printf("%lu", fibonaci(n, 0, 1));
}

---

최종 코드

#include <stdio.h>

unsigned long int fibonaci(int n, int a, int b){
    if (n == 0){
        return 0;
    }else if (n < 3){
        return a+b;
    }else {
        return fibonaci(n-1, b, a+b);
    }
}

int main(){
    int n;
    scanf("%d", &n);
    printf("%lu", fibonaci(n, 0, 1));
}