# Fibonacci sequence

2020-12-22 20:36:30

## 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 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 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 General idea ： We can use matrix diagonalization to solve , Turn the above formula into In the form of , And then it turns into , For easy calculation , We use diagonalization 1、 Make up the equations ： 2、 According to the above equation, the matrix expression is formed ： 3、 Find the coefficient matrix A The eigenvalues and eigenvectors of have been compared with each other A Diagonalize , 4、 Eigenvector matrix S by ： 5、 take Express by eigenvector , The first two terms of the Fibonacci sequence 6、 The final result is 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 ！

https://chowdera.com/2020/12/20201222203624023E.html