斐波那契数列编码实现

JAVA版

    /**
     * 平推方法实现
     */
    public static long fibLoop(int num) {
        if(num < 1 || num > 92)
            return 0;
        long a = 1;
        long b = 1;
        long temp;
        for(int i = 2; i < num; i++) {
            temp = a;
            a = b;
            b += temp;
        }
        return b;
    }

    /**
     * 递归方法实现
     * f(n) = f(n - 1) + f(n - 2)
     * 最高支持 n = 92 ，否则超出 Long.MAX_VALUE
     * @param num n
     * @return f(n)
     */
    public static long fibRec(int num) {
        if(num < 1)
            return 0;
        if(num < 3)
            return 1;
        return fibRec(num - 1) + fibRec(num - 2);
    }

    static long[] l = new long[93];
    static {
        l[1] = 1;
    }
    /**
     * 带有缓存的方法，比fibRec方法性能好很多
     */
    public static long fibBuffRec(int num) {
        if(num < 1 || num > 92)
            return 0;
        if(l[num] == 0)
            l[num] = fibBuffRec(num - 1) + fibBuffRec(num - 2);
        return l[num];
    }

    static List<BigDecimal> list = new ArrayList<BigDecimal>(93);
    static {
        list.add(BigDecimal.ZERO);
        list.add(BigDecimal.ONE);
    }
    /**
     * 1，2，3，4，5，6， 7 ，8
     * 1，1，2，3，5，8，13，21
     * 支持num超过92的超大型数字，使用了ArrayList进行缓存以提高性能
     */
    public static BigDecimal fibBig(int num) {
        if(num < 0)
            return list.get(0);
        if (list.size() <= num)
            list.add(fibBig(num - 1).add(fibBig(num - 2)));
        return list.get(num);
    }

    public static void main(String[] args) {

       long num1 = fibLoop(90);
       System.out.println(num1);
       long num2 = fibRec(10);
       System.out.println(num2);
       long num3 = fibBuffRec(10);
       System.out.println(num3);
       System.out.println(JSONUtil.parse(l));
       BigDecimal num4 = fibBig(100);
       System.out.println(num4);
       System.out.println(JSONUtil.parse(list));

    }

Python 版

# 一、从最大值考虑
numMax = int(input('please input  a maxnumber : '))    
c = []    
a, b = 0, 1    
while a < numMax: 
    a, b = b, a + b        
    c.append(a)    
c.remove(c[-1])    
print(c)   
# 从位数考虑
num = int(input('please input  a number : '))    
list1 = []    

for i in range(num):        
        if i <=1:
            list1.append(1)
        else:    
            list1.append(list1[-2] + list1[-1])
print(list1) #输出num位数列

# 根据f（n）= f(n-1)+f(n-2)实现
Fbs = [1,1]#斐波那契数列前两位
n = 3
s = input("Maxmun ")#输入最大次数
while n != (int(s)+1) :#因为差一原则所以要再加一
    a = Fbs[-1]
    b = Fbs[-2]
    fb = a+b
   # print(str(n)+" "+str(fb))
    n = n +1
    Fbs.append(fb)

print(Fbs)

完
参看资料
https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145