majianyu
4/28/2018 - 2:41 AM

EX1.1.19

斐波那契数列通常可以使用递归,迭代,闭包等方法实现. 其中递归方法性能较差,因为会涉及到重复计算

def F(N:int)->int:
    # 递归实现
    # python 的递归很慢,当计算第50个数字的时候可能需要数个小时甚至数天
    if N == 0:
        return 0
    if N == 1:
        return 1
    return F(N-1) + F(N-2)

def F2(N:int)->list:
    # 迭代实现
    if N == 0:
        return []
    fib = [0 for i in range(N+1)]
    fib[1] = 1
    if N ==1:
        return fib
    for i in range(2,N+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib

def F3()->int:
    #闭包实现
    a,b = 0,1
    def fib()->int:
        nonlocal a,b
        a,b = b ,a +b
        return a
    return fib
    
if __name__ == '__main__':
    fib = F3()
    for i in range(50):
        print(i+1,fib())
package main

import "fmt"

func main() {
    //fmt.Println(F(50))
    //fib := F2(50)
    //for i, v := range fib {
    //    fmt.Println(i, v)
    //}
    f := F3()
    for i:=1 ;i<=50;i++{
        fmt.Println(i,f())
    }
}
func F(N int) int64 {
    // 递归实现
    if N == 0 {
        return 0
    }
    if N == 1 {
        return 1;
    }
    return F(N-1) + F(N-2)
}

// 循环
func Fib1(n int) int {
	a, b := 0, 1
	for i := 0; i < n; i++ {
		a, b = b, a+b
	}
	return a
}

// 循环返回数组
func Fib11(n int) []int64 {
	result := make([]int64, n)
	if n == 0 {
		return result
	}
	result[0] = 1
	if n == 1 {
		return result
	}
	result[1] = 1
	for i := 2; i < n; i++ {
		result[i] = result[i-1] + result[i-2]
	}
	return result
}
func F3() func() int64 {
    // 闭包实现
    var a, b int64 = 0, 1
    f := func() int64 {
        a, b = b, a+b
        return a
    }
    return f
}
package com.test;

public class Fib {
    private static long[] F(int N) {
        long[] fib = new long[N + 1];
        if (N == 0) {
            return fib;
        }
        fib[1] = 1;
        // 因为要考虑到 参数 N 为0的情况,所以要分开写 return
        if (N == 1) {
            return fib;
        }
        for (int i = 2; i <= N; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib;
    }

    private static long F2(int N) {
        // 递归没有保存计算过的数据,会导致性能较差
        if (N == 0) {
            return 0;
        }
        if (N == 1) {
            return 1;
        }
        return F2(N - 1) + F2(N - 2);

    }

    public static void main(String[] args) {
        System.out.println(F2(10));
        long[] fib = F(10);
        for (int i = 1; i < fib.length; i++) {
            System.out.println(i + " " + fib[i]);
        }
    }
}