首页 文章

大型FIbonacci Java时间超过

提问于
浏览 次
0

我被困在一个测试用例上 . 该问题需要在给定的时间段内计算大的斐波纳契数 . 我已经通过10个中的8个案例并且坚持9个案例 .

这是我的代码：

import java.util.*;
import java.math.BigInteger;
public class LastNumberofFibo {




public static void main(String[] args) {
    Scanner sc  = new Scanner(System.in);
    BigInteger bi = sc.nextBigInteger();


    System.out.println(fib(bi));
}



public static BigInteger fib(BigInteger n) {
    BigInteger val=new BigInteger("10");
    int k = n.intValue();
    BigInteger ans = null;

    if(k == 0) {
        ans = new BigInteger("0");
    } else if(Math.abs(k) <= 2) {
        ans = new BigInteger("1");
    } else {
        BigInteger km1 = new BigInteger("1");
        BigInteger km2 = new BigInteger("1");

        for(int i = 3; i <= Math.abs(k); ++i) {
            ans = km1.add(km2);
            km2 = km1;
            km1 = ans;
        }
    }

    if(k<0 && k%2==0) { ans = ans.negate(); }
    return ans.mod(val);
}

}

提交后，我得到以下超时结果 .

我需要帮助才能提高代码效率 .

反馈 ：

失败案例＃9/10：超出时间限制输入：613455您的输出：stderr :(使用时间：3.26 / 1.50，使用的内存：379953152/536870912 . ）

请指导我 .

您诚挚的，Vidit Shah

java algorithm fibonacci

1 回答

  • 0

    我从评论中获取了最容易实现的建议并将其放入代码中 .

    import java.util.*;
import java.math.BigInteger;
public class LastNumberofFibo {


    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        BigInteger bi = sc.nextBigInteger();


        System.out.println(fib(bi));
    }


    public static BigInteger fib(BigInteger n) {
        int m = 10;
        BigInteger sixty = new BigInteger("60");
        int k = (n.mod(sixty)).intValue();
        int ans = 0;

        if(k == 0) {
            ans = 0;
        } else if(Math.abs(k) <= 2) {
            ans = 1;
        } else {
            int km1 = 1;
            int km2 = 1;

            for(int i = 3; i <= Math.abs(k); ++i) {
                ans = (km1 + km2)%m;
                km2 = km1;
                km1 = ans;
            }
        }

        if(k<0 && k%2==0) { ans = -ans; }
        return new BigInteger("" + ans);
    }

}
    回复于

相关问题