菲波那切数列最大公约数
程序员文章站
2022-09-29 21:51:24
不要自卑,去提升实力互联网行业谁技术牛谁是爹如果文章可以带给你能量,那是最好的事!请相信自己加油o~ 点击此处链接蓝桥杯历届真题题目+解析+代码+答案(2013-2020)(JavaA、B、C组)问题描述:【问题描述】斐波那契数列满足 F1 = F2 = 1,从 F3 开始有 Fn = Fn 1 + Fn 2。请你计算GCD(F2020, F520),其中 GCD(A, B) 表示 A 和 B 的最大公约数。【答案提交】这是一道结果填空题,你只需要算出结果后提交即可。本题的结果.....
不要自卑,去提升实力
互联网行业谁技术牛谁是爹
如果文章可以带给你能量,那是最好的事!请相信自己
加油o~
点击此处链接
蓝桥杯历届真题题目+解析+代码+答案(2013-2020)(JavaA、B、C组)
问题描述:
【问题描述】
斐波那契数列满足 F1 = F2 = 1,从 F3 开始有 Fn = Fn 1 + Fn 2。请你计算
GCD(F2020, F520),其中 GCD(A, B) 表示 A 和 B 的最大公约数。
【答案提交】
这是一道结果填空题,你只需要算出结果后提交即可。本题的结果为一个
整数,在提交答案时只填写这个整数,填写多余的内容将无法得分
解题思路:
> 首先求出两个斐波那契数
> 可以利用递归求,但是在试验时,采用递归花费时间较长,不建议
> 两个结果用BigInteger存取,因为使用long会溢出
> 求最大公约数可以利用欧几里得算法,BigInteger已经包装好,可以直接调用
代码:
public class Main {
public static void main(String[] args){
BigInteger num1=fib(2020);
System.out.println(num1);
BigInteger num2=fib(520);
System.out.println(num2);
System.out.println(num1.gcd(num2));
}
public static BigInteger fib(int n) {
BigInteger a=BigInteger.ONE;
BigInteger b=BigInteger.ONE;
BigInteger c=BigInteger.ONE;
if(n<=2) {
return a;
}
for(int i=3;i<=n;i++) {
c=a.add(b);
a=b;
b=c;
}
return c;
}
}
答案:
6765
本文地址:https://blog.csdn.net/m0_47256162/article/details/110494575
上一篇: 网站知名度快速提升的15种技巧