求斐波那契数列的5种实现--JavaEE23,xuef

斐波那契数列 1,1,2,3,5,8,13,21....
通项公式 fib(n) = fib(n-1) + fib(n-2)

  1. 普通迭代

...

  1. 普通递归

[Java] 纯文本查看 复制代码

?

private static long fib(int n){

    return n<=2?1:(fib(n-1)+fib(n-2));

}

  1. 带缓存的递归

        

[Java] 纯文本查看 复制代码

?

static Map<Integer,Long> cache2 = new HashMap<>();

        private static long fib2(int n){

        if(n <= 2) return 1L;

        if(cache2.containsKey(n))

            return cache2.get(n);

        Long fibn = fib2(n-1)+fib2(n-2);

        cache2.put(n, fibn);

        return fibn;

    }

  1. 使用 BigInteger 防止溢出

[Java] 纯文本查看 复制代码

?

static Map<Integer, BigInteger> cache = new HashMap<>();

    public static void main(String[] args) {

        int n = 100;

        BigInteger bi = fib(n);

        System.out.println(bi);

    }

 

    private static BigInteger fib(int n) {

        if(n <= 2) return BigInteger.ONE;

        if(cache.containsKey(n))

            return cache.get(n);

         

        BigInteger t = new BigInteger(fib(n-1).toByteArray()).

                add(new BigInteger(fib(n-2).toByteArray()));

        cache.put(n, t);

        return t;

    }

  1. 斐波那契数列迭代器

[Java] 纯文本查看 复制代码

?

/**

 * 定义一个遍历器,用于遍历斐波那契数字。

 *

 * @author moveb

 *

 */

public class T24_13_FibonacciIterator implements Iterator<Integer> {

    private int upBound = 23302;

    private int pre = 1;

    private int cur = 1;

     

    public T24_13_FibonacciIterator(){}

     

    public T24_13_FibonacciIterator(int ub){

        upBound = ub;

    }

     

    @Override

    public boolean hasNext() {

        return (cur < upBound);

    }

 

    @Override

    public Integer next() {

        int fib = cur;

        cur = cur + pre;

        pre = fib;

        return fib;

    }

 

    @Override

    public void remove() {

         

    }

}

评论

暂无评论