p1720 月落乌啼算钱（斐波那契数列）

这道题是要求计算斐波那契数列中第n项的值，其中斐波那契数列的定义是：第一项为，第二项为1，从第三项开始，每一项都是前两项的和。因此，斐波那契数列的前几项为、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、6765、10946、17711、28657、46368、75025、121393、196418、317811、514229、832040等。

对于这道题，我们可以使用递归或循环的方式来计算斐波那契数列中第n项的值。具体实现方法可以参考以下代码：

递归实现：

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

循环实现：

int fib(int n) {
    if (n == ) return ;
    if (n == 1) return 1;
    int a = , b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

以上代码中，递归实现的时间复杂度为O(2^n)，循环实现的时间复杂度为O(n)，因此循环实现更加高效。

相关问题

P1720 月落乌啼算钱（斐波那契数列）

题目描述：

在某个寂静的午夜，月亮高挂在天空中，窗外传来凄凉的乌鸦叫声。此时，机房小王正在打游戏，他想知道当前玩了多长时间，于是他打开了电脑的时钟，惊奇地发现时针和分针的指向正好重合在12点刻度上。此刻，小王看到的秒针指向了正下方，即6点刻度上。假设此时小王已经玩了X分钟，请编程计算出此刻时针和分针的夹角。结果精确到小数点后2位。

输入格式
输入文件只有一行，包含一个整数X（0<=X<=10^8）

输出格式
输出文件只有一行，包含一个实数，即时针和分针的夹角。结果精确到小数点后2位。

输入输出样例
输入 #1
1344
输出 #1
168.00

提示
数据说明：请将你的程序提交到OJ系统中，以P1720为题号进行提交。"""
算法1

思路：

斐波那契数列的通项公式：f(n) = ((1+√5)/2)^n/√5 - ((1-√5)/2)^n/√5。

时间复杂度：$O(1)$

空间复杂度：$O(1)$

参考代码：

洛谷P1720 月落乌啼算钱（斐波那契数列）答案

洛谷P1720题目要求计算斐波那契数列的第n项的值。斐波那契数列是一个经典的数学问题，定义如下：
- 第1项和第2项都为1；
- 从第3项开始，每一项都等于前两项之和。

以下是洛谷P1720题目的解答代码：

#include <iostream>
using namespace std;

long long fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    long long a = 1, b = 1, c;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

int main() {
    int n;
    cin >> n;
    cout << fibonacci(n) << endl;
    return 0;
}

你可以将上述代码复制到洛谷的编译器中运行，输入n的值，即可得到斐波那契数列的第n项的值。