#include <stdio.h>
#include <stdlib.h>

// Suite de Fibonacci: a_n = a_{n-1} + a_{n-2}, a_0 = 0, a_1 = 1
int fib(int n);
int fib2(int n);
int fib_imp(int n);

int main() {
    int n;
    printf("n=");
    scanf("%d", &n);
    printf("%d\n", fib(n));
    printf("%d\n", fib2(n));
    printf("%d\n", fib_imp(n));
}

// Suite de Fibonacci: a_n = a_{n-1} + a_{n-2}, a_0 = 0, a_1 = 1
int fib(int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return fib(n - 1) + fib(n - 2);
    }
}

int fib2(int n) {
    if (n > 1) {
        return fib2(n - 1) + fib(n - 2);
    }
    return n;
}

int fib_imp(int n) {
    int fib0 = 1;
    int fib1 = 1;
    int fib  = n == 0 ? 0 : fib1;
    for (int i = 2; i < n; ++i) {
        fib  = fib0 + fib1;
        fib0 = fib1;
        fib1 = fib;
    }
    return fib;
}