❗❗❗必看:
下列题我全部都使用 Java 语言写的,并且均可以提交成功,获得Accepted 结果的. 如果代码和详解看了之后,对答案有任何疑问,都可以在评论区提出来,我都会一个一个回答.
❗❗❗感谢大家的支持,如果喜欢我的博客,关注 点赞 收藏 评论一波,非常感谢!!!
文章目录
题目:菲波那契数列
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。
给出一个正整数a,要求菲波那契数列中第a个数是多少。
Input
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1 <= a <= 20)
Output
输出有n行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第a个数的大小
测试样例
输入
4
5
2
19
1
输出
5
1
4181
1
代码
import java.util.Scanner;
//斐波那契数列
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for(int i = 0;i<n;i++) {
System.out.println(fib(scanner.nextInt()));
}
}
private static int fib(int n) {
if(n<=1) {
return 1;
}
int fib = 1;
int prefib = 1;
for(int i = 2;i<n;i++) {
int temp = fib;
fib+=prefib;
prefib = temp;
}
return fib;
}
}
详解
初步思路
利用迭代的方法生成菲波那契数列,这样可以在较低的时间复杂度内计算出第a个菲波那契数。
具体步骤
-
输入解析
- 读取测试数据的组数n,然后逐一读取每组测试数据的正整数a。
-
计算菲波那契数
- 对于每个输入的a,使用迭代方法计算第a个菲波那契数:
- 如果a小于等于1,直接返回1(因为菲波那契数列的前两个数都是1)。
- 对于其他情况,使用两个变量fib和prefib分别保存当前的菲波那契数和前一个菲波那契数,并通过循环逐步更新这两个变量直到计算出第a个菲波那契数。
- 对于每个输入的a,使用迭代方法计算第a个菲波那契数:
-
输出结果
- 对每组输入,输出对应的菲波那契数。
总结方法
通过迭代法计算菲波那契数列的优点在于其时间复杂度为O(a),比递归方法的指数级增长要高效得多。对于较小的a(如本题中的a最大值为20),这种方法在计算上是非常快速且可靠的。
此外,利用变量交换的方式减少空间复杂度,使得算法只需常量空间即可完成。迭代法不仅简单易懂,而且在处理较小范围的数列问题时表现非常优异。
标签:契数,数列,int,fib,详解,菲波,那契 From: https://blog.csdn.net/weixin_75202470/article/details/139380250