当前位置:网站首页>Fibonacci sequence

Fibonacci sequence

2020-12-22 20:36:30 osc_ seventy-six million seven hundred and fifty-six thousand s

One 、 Background of Fibonacci sequence problem

Fibonacci (Leonardo Pisano Fibonacci) Born about in 1170 year , About 1250 In what is now Italy Pisa died , He has traveled all over Europe and North Africa . He is the author of many mathematics textbooks , In addition, the Arabic numeral representation was introduced The European . Although his books are Manuscripts , But they are still very popular . One of Fibonacci's most famous books is LiberAbaci, Published in 1202 year . The following questions are raised :

One on one rabbit Put it in a place surrounded by walls , If you assume that each pair of rabbits gives birth to a pair of rabbits every month , And the newborn rabbits can give birth from the second month , So a year later, how many pairs of rabbits will be produced by the original pair of Rabbits

The solution to this problem is a set called Fibonacci sequence :1、1、2、3、5、8、13....

The general formula is

[ The formula ]

Be careful , This statement is a little bit of a conversion to a statement —— If it's not assumed that the newborn rabbit will take a month to mature , And then we can have children , Then there will be no sequence named after Fibonacci . Because in that case , The number of rabbits doubles every month ,n Months later , There will be a total of  [ The formula ]  To the rabbit , Although the rules are easy , But it's not unique in Mathematics .

 

Two 、 The standard recursive solution - Program realization

MATLAB edition - With caching mechanism

function f = fibonacci(n)
% this is my first function
f = zeros(n, 1); %  Specify the size of the vector in advance , Speed up processing 
f(1) = 1;
f(2) = 2;
for k = 3:n
    f(k) = f(k-1) + f(k-2);
end

Output results

>> fibonacci(10)

ans =

     1
     1
     2
     3
     5
     8
    13
    21
    34
    55

Python edition - Pure recursion mechanism

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

Python Decorator version - With caching mechanism

from functools import wraps


def memoization(func):
    """ Cache decorator """
    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、 ... and 、 Diagonal solutions from the perspective of linear algebra

3.1 Discussion of principle

Through the above discussion , We have The recurrence of Fibonacci sequence is

[ The formula ]

General idea : We can use matrix diagonalization to solve , Turn the above formula into  [ The formula ]  In the form of , And then it turns into [ The formula ] , For easy calculation  [ The formula ] , We use diagonalization

[ The formula ]

1、 Make up the equations :

[ The formula ]

2、 According to the above equation, the matrix expression is formed :

[ The formula ]

3、 Find the coefficient matrix A The eigenvalues and eigenvectors of have been compared with each other A Diagonalize ,

[ The formula ]

4、 Eigenvector matrix S by :

[ The formula ]

5、 take  [ The formula ]  Express by eigenvector , [ The formula ]  The first two terms of the Fibonacci sequence

[ The formula ]

6、 The final result is

[ The formula ]

So give k value , You can calculate the Fibonacci sequence value you need directly , You don't have to recurse to get .

3.2 Code implementation

Use matlab Write the above steps :

%  I want Fibonacci number n term , assignment k=(n-1)
%  assignment k, I want to ask for 10 term .1、1、2、3、5、8....
k = 9;
%  Find the number of Fibonacci series k term , The initial value is u_0 = [0 1]
A = [1,1; 1 0];
% S Is the eigenvector matrix ,D For diagonal matrix 
[S,D] = eig(A);
u_0 = [1;0];
%  Express by eigenvector matrix u_0
% u_0 = S * C -> C = inv(S) * u_0
C = S \ u_0;
u_k = S * D^k * C;

u_k

The result is :

>> diagonal

u_k =

   55.0000  %  The first 10 term 
   34.0000  %  The first 9 term 
  • It's fun learning linear algebra ~

More :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)
form  
   
   

Reference source

  1. 《MATLAB Numerical calculation 》 Books
  2. 《 Linear algebra and its applications 》 Books
  3. 《MIT linear algebra 》 Course , This course is really wonderful !

 

 

版权声明
本文为[osc_ seventy-six million seven hundred and fifty-six thousand s]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201222203624023E.html

随机推荐