C++代码O(1)实现：有一个数字n（n<=1e9），设f（n）为当n<=20时，f（n）=n，否则f（n）=f（n-10）+f（n-20），请你求出最后f（n）的值，输入样例 23 输出样例 16 输入样例 114514191 输出样例 380435595

下面是一份时间复杂度为 O(1) 的 C++ 代码：

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

int main() {
    int n;
    cin >> n;
    if (n <= 20) {
        cout << n << endl;
    } else {
        double sqrt5 = sqrt(5);
        double a = (1 + sqrt5) / 2;
        double b = (1 - sqrt5) / 2;
        double c = (pow(a, n + 1) - pow(b, n + 1)) / sqrt5;
        int ans = (int)c;
        cout << ans << endl;
    }
    return 0;
}

该代码利用了斐波那契数列的通项公式来求解，时间复杂度为 O(1)。其中，sqrt5 表示根号5，a 和 b 分别表示通项公式中的两个系数，c 表示最终的结果，ans 为 c 的整数部分，即最终的答案。

相关问题

C++代码O（1）实现：有一个数字n（n<=1e9），设f（n）为当n<=20时，f（n）=n，否则f（n）=f（n-10）+f（n-20），请你求出最后f（n）的值，输入样例 23 输出样例 16

下面是一份时间复杂度为 O(1) 的 C++ 代码：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n <= 20) {
        cout << n << endl;
    } else {
        int f1 = 10, f2 = 20, f3;
        for (int i = 30; i <= n; i += 10) {
            f3 = f2 + f1;
            f1 = f2;
            f2 = f3;
        }
        cout << f3 << endl;
    }
    return 0;
}

该代码利用了循环来逐步计算出 f(n) 的值，时间复杂度为 O(1)。其中，f1、f2、f3 分别表示 f(n-10)、f(n-20) 和 f(n)，循环从 n=30 开始，每次增加 10，直到计算出 f(n) 的值。

C++代码实现：有一个数字n（n<=1e9），设f（n）为当n<=20时，f（n）=n，否则f（n）=f（n-10）+f（n-20），请你求出最后f（n）的值，输入样例 23 输出样例 16

下面是一份时间复杂度为 O(n) 的 C++ 代码：

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

const int MAXN = 1e9 + 5;
const int MOD = 1e9 + 7;

int f[MAXN];

int main() {
    int n;
    cin >> n;

    f[1] = 1;
    f[2] = 2;
    f[3] = 3;
    f[4] = 4;
    f[5] = 5;
    f[6] = 6;
    f[7] = 7;
    f[8] = 8;
    f[9] = 9;
    f[10] = 10;
    f[11] = 11;
    f[12] = 12;
    f[13] = 13;
    f[14] = 14;
    f[15] = 15;
    f[16] = 16;
    f[17] = 17;
    f[18] = 18;
    f[19] = 19;
    f[20] = 20;

    for (int i = 21; i <= n; i++) {
        f[i] = f[i - 10] + f[i - 20];
        f[i] %= MOD;
    }

    cout << f[n] << endl;

    return 0;
}

该代码利用了动态规划的思想，使用一个数组 f 来记录 f(n) 的值，时间复杂度为 O(n)。其中，f[1] 到 f[20] 的值事先已经确定，然后从 f[21] 开始逐步计算 f(n) 的值。