【题解】斐波那契数列最大公约数

【问题描述】

斐波那契数列满足 F₁ = F₂ = 1，从 F₃ 开始有 F_n = F_n-1 + F_n-2。请你计算
GCD(F₂₀₂₀, F₅₂₀)，其中 GCD(A, B) 表示 A 和 B 的最大公约数。

【答案提交】

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个
整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解题思路

• 求出两个斐波那契数

• 用求得的数做最大公约数计算。

1. 可以利用递归求出斐波那契和最大公约数，由于花费时间过长，不使用。

2. 使用BigInteger存取，用long则会溢出。求最大公约数可以使用欧几里得算法，BigInteger里已经封装此方法（gcd）。

3. 记得学习BigInteger其他方法。

【扩展】

用递归求斐波那契

/**
     * @param n : Fib的第几项
     */
static int Fibonacci(int n) {
    if (n == 2 || n == 1) {
        return 1;//递归出口
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

用递归求最大公约数

// 利用辗转相除法和递归计算最大公约数
static int GCD(int n, int m) {

    if (n % m == 0) {
        return m;//递归出口
    }

    return GCD(m, n % m);//辗转相除法
}

【代码】

import java.math.BigInteger;

public class topic05 {
    public static void main(String[] args) {

		// 求出两个斐波那契数
        BigInteger Fib2020 = Fibonacii(2020);
        BigInteger Fib520 = Fibonacii(520);

        // 使用BigInteger提供的gcd方法求得最大公约数
        System.out.println(Fib2020.gcd(Fib520));
    }


    /**
     * @param n : Fib的第几项
     */
    static BigInteger Fibonacii(int n) {
        BigInteger a = BigInteger.ONE; // 基本常量1
        BigInteger b = BigInteger.ONE;
        BigInteger temp = BigInteger.ONE;

        if (n <= 2) return a;// 前两项都是1

        for (int i = 3; i <= n; i++) {
            temp = a.add(b); // 新的项是前两项相加

            // 后移
            a = b;
            b = temp;
        }
        return temp;
    }
}

结果

6765