欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

菲波那切数列最大公约数

程序员文章站 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