精确斐波那契数列 的代码

精确斐波那契数列的代码实现取决于你选择的语言，这里提供一种常见的Python版本的动态规划解法：

def fibonacci(n):
    if n <= 0:
        return "错误：输入必须是非负整数"
    elif n == 1 or n == 2:
        return 1
    else:
        # 创建一个列表存储已经计算过的斐波那契数
        fib_sequence = [0, 1] +  * (n - 1)
        
        # 使用动态规划填充列表
        for i in range(2, n+1):
            fib_sequence[i] = fib_sequence[i-1] + fib_sequence[i-2]
            
        return fib_sequence[n]

# 测试代码
n = int(input("请输入一个非负整数："))
result = fibonacci(n)
print(f"斐波那契数列的第 {n} 项是：{result}")

在这个代码中，我们首先检查输入是否合法，然后通过创建一个列表 `fib_sequence` 来存储斐波那契数列的前几项以及后续的预计算值。接着，利用循环逐步计算并更新列表，最后返回所需的第 n 项的值。

如果你需要其他语言的实现，如Java或C++，代码会有所不同，但基本思想是相同的：利用数组或列表存储中间结果，避免重复计算。

相关问题

Java Fibonacci数列。（用数组不用数组都可以） Fibonacci数列有如下特点：已知n1=1,n2=1,n3=n1+n2,n4=n2+n3,...要求输出前20个数字，并判断2178309是不是Fibonacci数列中的数，如果是则输出是第几个数值。

斐波那契数列是一个经典的数学序列，其中每个数都是前两个数之和。在Java中，我们可以使用循环或递归的方式来生成这个序列。这里我将展示如何用数组存储前20个数字，并检查给定的数2178309是否属于该序列。

首先，我们先生成前20个数字并存储在一个数组里：

public class Fibonacci {
    public static void main(String[] args) {
        int[] fibArray = new int[20];
        fibArray[0] = 1;
        fibArray[1] = 1;

        for (int i = 2; i < 20; i++) {
            fibArray[i] = fibArray[i - 2];
        }

        // 输出前20个数字
        for (int num : fibArray) {
            System.out.print(num + " ");
        }
    }
}

运行上述代码，你将得到前20个斐波那契数。

接下来，我们要检查2178309是否为斐波那契数。由于数组已经生成了前20个数字，我们可以从后向前查找是否存在某个数等于2178309：

// 检查给定数是否为Fibonacci数
for (int i = fibArray.length - 1; i >= 0; i--) {
    if (fibArray[i] == 2178309) {
        System.out.println("2178309是第" + (i + 1) + "个Fibonacci数");
        break;
    }
}

if (fibArray[fibArray.length - 1] != 2178309) {
    System.out.println("2178309不是Fibonacci数");
}

这段代码会在找到2178309的位置后立即停止搜索，并告知它是在序列中的哪个位置。

注意，这个过程假设输入的数小于或等于上一个斐波那契数，因为斐波那契序列中的数通常非常大，直接计算到很大数可能会遇到精度问题。如果你需要精确地计算较大的斐波那契数，可能需要使用其他算法（例如矩阵快速幂法）。

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)$

参考代码：