pta1124斐波那契数列

### PTA 1124 斐波那契数列实现与解法 PTA（Programming Teaching Assistant）平台上的题目通常涉及算法设计和编程能力的考察。对于斐波那契数列的相关实现，可以基于递归、迭代或其他优化方法完成。以下是针对该问题的具体解答。 #### 方法一：递归实现 递归是一种直观的方式用于求解斐波那契数列中的某一项值。然而需要注意的是，递归方式的时间复杂度较高 \(O(2^n)\)，因此不适合处理较大的输入数据。以下是一个标准的 C 语言递归实现： ```c #include <stdio.h> // 定义斐波那契函数 int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; return fib(n - 1) + fib(n - 2); } int main() { int n; printf("请输入要查询的项数: "); scanf("%d", &n); printf("第 %d 项的值为：%d\n", n, fib(n)); return 0; } ``` 此代码片段展示了如何通过递归调用来获取指定位置的斐波那契数值[^1]。 #### 方法二：动态规划（带记忆化） 为了避免重复计算子问题的结果，可以通过引入数组存储中间状态来降低时间复杂度至线性级别 \(O(n)\)。这种方法也被称为自顶向下的动态规划或记忆化搜索。 ```c #include <stdio.h> #define MAX_N 1000 // 假设最大不超过1000项 long long dp[MAX_N]; long long fibonacci_dp(int n) { if (n == 0) return 0; if (n == 1) return 1; if (dp[n] != -1) return dp[n]; return dp[n] = fibonacci_dp(n - 1) + fibonacci_dp(n - 2); } int main() { int n; for (int i = 0; i < MAX_N; ++i) dp[i] = -1; // 初始化DP表 printf("请输入要查询的项数: "); scanf("%d", &n); printf("第 %d 项的值为：%lld\n", n, fibonacci_dp(n)); return 0; } ``` 上述程序利用了一个全局变量 `dp` 来保存已经计算过的值，从而减少不必要的重复运算[^3]。 #### 方法三：迭代法 相比递归而言，迭代更加高效且易于理解和维护。它仅需常量空间即可完成整个序列的构建过程。 ```c #include <stdio.h> int fibonacci_iterative(int n) { if (n == 0) return 0; if (n == 1) return 1; int prev = 0, curr = 1; for (int i = 2; i <= n; ++i) { int next = prev + curr; prev = curr; curr = next; } return curr; } int main() { int n; printf("请输入要查询的项数: "); scanf("%d", &n); printf("第 %d 项的值为：%d\n", n, fibonacci_iterative(n)); return 0; } ``` 这段代码实现了非递归版本的斐波那契数列生成逻辑，并具有较好的性能表现[^5]。 --- ### 总结 以上介绍了三种不同的斐波那契数列解决方案——递归、动态规划以及迭代。每种方法都有其适用场景，在实际应用中应根据具体需求选择合适的策略。