Java解决斐波那契数列内存溢出问题

剑指offer10-1
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

最近看到一道题，求斐波那契数列的第一百项，于是我简单写了个递归`在这里插入代码片在这里插入代码片

class Solution {
    public int fib(int n) {
        int s1=0,s2=1,s3=0;
        if(n<2){
            return n;

        }

        for(int i=2;i 
但是如果是int类型的话，会出现内存溢出的问题，到第47项就出现了内存溢出；于是我改用了long类型；
 
class Solution {
    public int fib(int n) {
        long s1=0,s2=1,s3=0;
        if(n<2){
            return n;

        }

        for(int i=2;i 
但是还是会出现内存溢出，到第93项出现内存溢出。
 于是我又选取了biginteger解决这个问题：
 
public class Soulution {
        public BigInteger fib(int n) {

            long s1=0,s2=1,s3=0;
            if(n==0){
                return new BigInteger("0");

            }
            if(n==1){
                return new BigInteger("1");

            }

            BigInteger a1=new BigInteger("0");
            BigInteger a2=new BigInteger("1");
            BigInteger a3=new BigInteger("0");
             for(int i=2;i 
因为BigInteger可以 *** 纵大整数，所以不会出现内存溢出的问题，但是也改变了题目中返回的数据类型，题干要求返回int类型的数据,我就很疑惑，内存都溢出了，怎么还能输出int型的呢？我就开始看题干，发现题干有个取模这个东西，他并不需要输出完整的答案，只需要在内存溢出时取模再输出，于是我就在上面的程序上改了改，于是结果就出来了：
 
import java.math.BigInteger;
class Solution {
    public int fib(int n) {
        switch (n) {
            case 0:
                return 0;
            
            case 1:
                return 1;
            
            case 2:
                return 1;
            


        }
        
        BigInteger a1 = new BigInteger("0");
        BigInteger a2 = new BigInteger("1");
        BigInteger a3 = new BigInteger("0");
        for (int i = 2; i < n; i++) {
            a3 = a1.add(a2);
            a1 = a2;
            a2 = a3;
            a3 = a1.add(a2);
        }
        if (a3.compareTo(new BigInteger("1000000007")) == 1) {
            a3 = a3.mod(new BigInteger("1000000007"));
        }
        int result = a3.intValue();
        return result;

    }
}
 

 题就解出来了，应该还有更好的办法，但是我现在还没想到，看看以后能不能想到更好的方案吧。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5482661.html