题解 | Fibonacci数列

#include <iostream>
#include <vector>
using namespace std;


int Fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) {
        return 1;
    }
    if (n >= 2) {
        return Fibonacci( n - 1) + Fibonacci( n - 2);
    }
    return 0;
}

int revGoFibonacci(int n) {
    return 0;
}

int main() {
    int N;
    cin >> N;
    //cout << "N=" << N << endl;
    //int F = Fibonacci(n);
    vector<int > FF(100, 0);
    FF[0] = 0;
    FF[1] = 1;
    int step = 0;
    bool isOK = false;
    for (int i = 2; i < 500; i++) {
        FF[i] = FF[i - 1]  + FF[i - 2];
        //cout << "i=" << i << endl;
        //cout << " FF[i] =" << FF[i] << endl;
        if (N >= FF[i - 1] && N < FF[i]) {
            int leftFF = N - FF[i - 1];
            int rightFF = FF[i] - N;
            if (leftFF <= rightFF) {
                step = leftFF;
                isOK = true;
                break;
            } else {
                step = rightFF;
                isOK = true;
                break;
            }
        }
    }

    //int reF = revGoFibonacci(N);
    if (isOK) {
        cout << step << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")