当前位置:网站首页>斐波那契数列

斐波那契数列

2020-12-22 20:36:30 osc_76756685

一、斐波那契数列问题背景

斐波那契(Leonardo Pisano Fibonacci)约出生于1170年,大约于1250年在现在意大利 的比萨逝世,他履行的足迹遍布欧洲和北非。他著有多本数学课本,此外还把阿拉伯数字表示法引入欧洲。虽然他的书都是手抄本,但它们还是广为流传。斐波那契最著名的一本书是LiberAbaci,出版于1202年。其中提出了下述问题:

某人将一对兔子 放在一个四周都是围墙的地方,如果假设每对兔子每个月生出一对兔子,且新生的兔子从第二个月开始就能生育,那么一年之后由最初的那对兔子一共产生多少对兔子

这个问题的解就是被称为斐波那契数列的集合:1、1、2、3、5、8、13....

通项公式为

[公式]

注意,这个表述稍微转换一种说法——如果没有假设新生出的兔子需要一个月才能够成熟,进而能够生育,那么将不会有这个以斐波那契的名字命名的序列。因为这样的话,兔子的对数每过一个月就会翻倍,n个月过后,会有总共 [公式] 对兔子,虽然规律共容易,但在数学上没啥独特性。

 

二、标准的递归解-程序实现

MATLAB版-带有缓存机制

function f = fibonacci(n)
% this is my first function
f = zeros(n, 1); % 提前规定向量的大小,加快处理速度
f(1) = 1;
f(2) = 2;
for k = 3:n
    f(k) = f(k-1) + f(k-2);
end

输出结果

>> fibonacci(10)

ans =

     1
     1
     2
     3
     5
     8
    13
    21
    34
    55

Python版-纯递归机制

def fibonacci(n):
    if n <= 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Python装饰器版-带有缓存机制

from functools import wraps


def memoization(func):
    """缓存装饰器"""
    cache = {}
    miss = object()

    @wraps(func)
    def wrapper(args):
        result = cache.get(args, miss)
        if result is miss:
            result = func(args)
            cache[args] = result
        return result

    return wrapper


@memoization
def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


print(fib(9))

三、线性代数视角下的对角化解

3.1 原理探讨

通过上面的讨论,我们有 斐波那契数列的递推式为

[公式]

总体思路:我们可以使用矩阵对角化来解决,将上面的式子化成 [公式] 的形式,继而化成[公式] ,为了容易计算 [公式] ,我们采用对角化的方式

[公式]

1、组成方程组:

[公式]

2、根据上述方程组成矩阵表达式:

[公式]

3、求系数矩阵A的特征值和特征向量已对A进行对角化,

[公式]

4、特征向量矩阵S为:

[公式]

5、将 [公式] 用特征向量表示, [公式] 表示斐波那契数列的前两项

[公式]

6、最终结果为

[公式]

所以给出k值,可以直接算出需要的斐波那契数列值,不必递归才能得到。

3.2代码实现

使用matlab编写上述步骤:

% 欲求斐波那契数列第n项,赋值k=(n-1)
% 赋值k,想要求第10项。1、1、2、3、5、8....
k = 9;
% 求斐波那契数列的第k项,初始值为u_0 = [0 1]
A = [1,1; 1 0];
% S为特征向量矩阵,D为对角阵
[S,D] = eig(A);
u_0 = [1;0];
% 用特征向量矩阵表示u_0
% u_0 = S * C -> C = inv(S) * u_0
C = S \ u_0;
u_k = S * D^k * C;

u_k

结果为:

>> diagonal

u_k =

   55.0000  % 第10项
   34.0000  % 第9项
  • 学习线性代数真是有趣~

更多内容:https://zhuanlan.zhihu.com/p/119395137

https://zhuanlan.zhihu.com/p/119395137

def consumer():
    r = ''
    while True:
        n = yield r
        if not n:
            return
        print('[CONSUMER] Consuming %s...' % n)
        r = '200 OK'

def produce(c):
    c.send(None)
    n = 0
    while n < 5:
        n = n + 1
        print('[PRODUCER] Producing %s...' % n)
        r = c.send(n)
        print('[PRODUCER] Consumer return: %s' % r)
    c.close()

c = consumer()
produce(c)
表格  
   
   

参考来源

  1. 《MATLAB数值计算》书籍
  2. 《线性代数及其应用》书籍
  3. 《MIT线性代数》课程,这门课真是精彩!

 

 

版权声明
本文为[osc_76756685]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4711987/blog/4830429

随机推荐