python兔子繁殖问题中如何输出相应月份的数列_斐波那契数列介绍及Python中五种方法斐波那契数列...

Q：斐波那契数列为何那么重要，全部关于数学的书几乎都会提到？

A：由于斐波那契数列在数学和生活以及天然界中都很是有用。html

1.　斐波那契数列 概念引入

斐波那契数列(Fibonacci sequence)，又称黄金分割数列，因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入，故又称为“兔子数列”。python

数学上，斐波那契数列以递归的形式进行定义：

F

0

=

0

F

1

=

1

F

n

=

F

n

−

1

+

F

n

−

2

F_{0} = 0\\ F_{1} = 1\\ F_{n} = F_{n-1} + F_{n-2}F0​=0F1​=1Fn​=Fn−1​+Fn−2​web

场景

先来开看看“兔子数列”以及其余数学应用场景！！app

1. 1　兔子数列

通常而言，兔子在出生两个月后，就有繁殖能力，一对兔子每月能生出一对小兔子来。若是全部兔子都不死，那么一年之后能够繁殖多少对兔子？svg

1.2　排列组合

有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不一样的走法?函数

更多数学方面知识，请戳：

斐波那契数列ui

…设计

2.　数列数学方法解答

2.1　兔子繁殖问题

斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。code

通常而言，兔子在出生两个月后，就有繁殖能力，一对兔子每月能生出一对小兔子来。若是全部兔子都不死，那么一年之后能够繁殖多少对兔子？

咱们不妨拿新出生的一对小兔子分析一下：

第一个月小兔子没有繁殖能力，因此仍是一对

两个月后，生下一对小兔对数共有两对

三个月之后，老兔子又生下一对，由于小兔子尚未繁殖能力，因此一共是三对

－－－－－－

依次类推能够列出下表：

通过月数

1

2

3

4

5

6

7

8

9

10

11

12

…

幼仔对数

1

0

1

1

2

3

5

8

13

21

34

55

…

成兔对数

0

1

1

2

3

5

8

13

21

34

55

89

整体对数

1

1

2

3

5

8

13

21

34

55

89

144

幼仔对数=前月成兔对数

成兔对数=前月成兔对数+前月幼仔对数

整体对数=本月成兔对数+本月幼仔对数

能够看出幼仔对数、成兔对数、整体对数都构成了一个数列。这个数列有关十分明显的特色，那是：

前面相邻两项之和，构成了后一项。

2.2　排列组合

2.2.1　跨楼梯组合

有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第10级台阶有几种不一样的走法?

这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……

1，2，3，5，8，13……因此，登上十级，有89种走法。

2.2.2　掷硬币不连续情形

一枚均匀的硬币掷10次，问不连续出现正面的可能情形有多少种？

答案是:

(

1

/

√

5

)

∗

[

(

1

+

√

5

)

/

2

]

(

10

+

2

)

−

[

(

1

−

√

5

)

/

2

]

(

10

+

2

)

=

144

(1/√5)*{[(1+√5)/2]^(10+2) - [(1-√5)/2]^(10+2)}=144(1/√5)∗[(1+√5)/2](10+2)−[(1−√5)/2](10+2)=144

…

3.　Python代码实现斐波那契数列

时间复杂度

空间复杂度

经过时间复杂度和空间复杂度评判代码的执行效率。

例如：从规模上来讲，若是须要计算F(4)的值，须要进行9次元素操做

设T(n)为计算n的时间复杂度，那么

T

(

n

)

=

T

(

n

−

1

)

+

T

(

n

−

2

)

+

O

(

1

)

T(n) = T(n-1) + T(n-2)+O(1)T(n)=T(n−1)+T(n−2)+O(1)

通常状况，能够得出：T

(

n

)

<

2

∗

T

(

n

−

1

)

+

O

(

1

)

T(n)< 2* T(n-1) + O(1)T(n)<2∗T(n−1)+O(1)

粗略估算，T

(

n

)

<

O

(

2

n

)

T(n) < O(2^n)T(n)

3.1　python特有写法

打印正整数n以内的斐波那契数列

# Python特有， 常规写法

def fib(self, n):

a = 0

b = 1

while a <= n:

print(a, end=" ", flush=True)

a, b = b, a + b # python不借助变量交换两数的值

fib(100) # 求n以内的斐波那契数列

时

间

复

杂

度

：

O

(

n

)

，

空

间

复

杂

度

：

O

(

1

)

时间复杂度：O(n)， 空间复杂度：O(1)时间复杂度：O(n)，空间复杂度：O(1)

3.2　递归

打印斐波那契数列前10位数字

# 递归

def fibonacci(i):

num_list = [0, 1]

if i < 2:

return num_list[i]

elif i >= 2:

return (fibonacci(i - 2) + fibonacci(i - 1))

print(fibonacci(10))

时

间

复

杂

度

：

O

(

n

)

，

空

间

复

杂

度

：

O

(

n

)

时间复杂度：O(n)， 空间复杂度：O(n)时间复杂度：O(n)，空间复杂度：O(n)

3.3　类对象

# 迭代的方式

class FibIterator(object):

"""斐波那契数列迭代器"""

def __init__(self, n):

"""

:param n: int, 指明生成数列的前n个数

"""

self.n = n

# current用来保存当前生成到数列中的第几个数了

self.current = 0

# num1用来保存前前一个数，初始值为数列中的第一个数0

self.num1 = 0

# num2用来保存前一个数，初始值为数列中的第二个数1

self.num2 = 1

def __next__(self):

"""被next()函数调用来获取下一个数"""

if self.current < self.n:

num = self.num1

self.num1, self.num2 = self.num2, self.num1+self.num2

self.current += 1

return num

else:

raise StopIteration

def __iter__(self):

"""迭代器的__iter__返回自身便可"""

return self

if __name__ == '__main__':

fib = FibIterator(10)

for num in fib:

print(num, end=" ")

3.4 矩阵解决问题

从定义开始：

F

0

=

0

F

1

=

1

F

n

=

F

n

−

1

+

F

n

−

2

F_{0} = 0\\ F_{1} = 1\\ F_{n} = F_{n-1} + F_{n-2}F0​=0F1​=1Fn​=Fn−1​+Fn−2​

转化为矩阵形式

(

F

n

+

1

F

n

)

=

(

1

1

1

0

)

∗

(

F

n

F

n

−

1

)

$$\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}$$ = $$\begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}$$ * $$\begin{pmatrix} F_{n}\\ F_{n-1} \end{pmatrix}$$ (Fn+1​Fn​​)=(11​10​)∗(Fn​Fn−1​​)

能够得出：(

F

n

+

1

F

n

)

(

1

1

1

0

)

(

F

1

F

0

)

$$\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}$$ $$\begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}$$ $$\begin{pmatrix} F_{1}\\ F_{0} \end{pmatrix}$$ (Fn+1​Fn​​)(11​10​)(F1​F0​​)

咱们设定

A

=

(

1

1

1

0

)

A=

$$\begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}$$ A=(11​10​)

很显然能够变为以下：

A

=

(

F

2

F

1

F

1

F

0

)

A=

$$\begin{pmatrix} F_{2}&F_{1}\\ F_{1}&F_{0} \end{pmatrix}$$ A=(F2​F1​​F1​F0​​)

经过数学概括法能够推出如下公式：

A

n

=

(

F

n

+

1

F

n

F

n

F

n

−

1

)

=

(

1

1

1

0

)

n

A^{n}=

$$\begin{pmatrix} F_{n+1}&F_{n}\\ F_{n}&F_{n-1} \end{pmatrix}$$ = $$\begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}$$ ^{n}An=(Fn+1​Fn​​Fn​Fn−1​​)=(11​10​)n

很显然计算F(n)的值，只须要进行矩阵的n次幂运算，取出结果矩阵第二行第一个元素值便可

时

间

复

杂

度

：

O

(

n

)

，

空

间

复

杂

度

：

O

(

1

)

时间复杂度：O(n)， 空间复杂度：O(1)时间复杂度：O(n)，空间复杂度：O(1)

这里能够利用快速幂运算求解，假设计算A的N次幂,二阶矩阵的乘法知足结合律

设A,B,C都是任意的二阶矩阵，则

A

(

B

C

)

=

(

A

B

)

C

A(BC)=(AB)CA(BC)=(AB)C

咱们设定：m

=

[

n

2

]

m=[\frac{n}{2}]m=[2n​]

当n为偶数: A

N

=

A

m

∗

A

m

A^{N}=A^{m}∗A^{m}AN=Am∗Am

当n为奇数: A

N

=

A

m

∗

A

m

∗

A

A^{N}=A^{m}∗A^{m}∗AAN=Am∗Am∗A

至关于A

6

=

A

3

∗

A

3

，

A

7

=

A

3

∗

A

3

∗

A

A^{6}=A^3∗A^3，A^7=A^3∗A^3∗AA6=A3∗A3，A7=A3∗A3∗A

这样能够减小计算次数，由于A

6

=

A

∗

A

∗

A

∗

A

∗

A

∗

A

A6=A∗A∗A∗A∗A∗AA6=A∗A∗A∗A∗A∗A这里有5个乘,A

6

=

(

A

∗

A

∗

A

)

∗

(

A

∗

A

∗

A

)

A6=(A∗A∗A)∗(A∗A∗A)A6=(A∗A∗A)∗(A∗A∗A) 计算完A

∗

A

∗

A

A*A*AA∗A∗A 获得结果A

3

A^3A3，再乘以A

3

A^3A3 这里用了3个乘

如下是普通数据的快速幂运算，运算改成矩阵乘法,ret改成单位矩阵便可

def qpow(base, exp):

if exp == 0:

return 1

ret = 1

while exp:

if exp & 1:

ret = ret * base

base = base * base

exp >>= 1

return ret

3.5 矩阵再推导

咱们能够设定： n

=

2

m

n=2mn=2m

那么

A

2

m

=

(

F

2

m

+

1

F

2

m

F

2

m

F

2

m

−

1

)

=

A

m

∗

A

m

A^{2m}=

$$\begin{pmatrix} F_{2m+1}&F_{2m}\\ F_{2m}&F_{2m-1} \end{pmatrix}$$ =A^{m}*A^{m}A2m=(F2m+1​F2m​​F2m​F2m−1​​)=Am∗Am

已知

A

m

=

(

F

m

+

1

F

m

F

m

F

m

−

1

)

A^{m}=

$$\begin{pmatrix} F_{m+1}&F_{m}\\ F_{m}&F_{m-1} \end{pmatrix}$$ Am=(Fm+1​Fm​​Fm​Fm−1​​)

因此：

(

F

m

+

1

F

m

F

m

F

m

−

1

)

∗

(

F

m

+

1

F

m

F

m

F

m

−

1

)

=

(

F

2

m

+

1

F

2

m

F

2

m

F

2

m

−

1

)

$$\begin{pmatrix} F_{m+1}&F_{m}\\ F_{m}&F_{m-1} \end{pmatrix}$$ * $$\begin{pmatrix} F_{m+1}&F_{m}\\ F_{m}&F_{m-1} \end{pmatrix}$$ = $$\begin{pmatrix} F_{2m+1}&F_{2m}\\ F_{2m}&F_{2m-1} \end{pmatrix}$$ (Fm+1​Fm​​Fm​Fm−1​​)∗(Fm+1​Fm​​Fm​Fm−1​​)=(F2m+1​F2m​​F2m​F2m−1​​)

计算后能够得出：

(

F

2

m

+

1

F

2

m

)

=

(

F

m

+

1

2

+

F

m

2

F

m

∗

(

F

m

+

1

+

F

m

−

1

)

)

$$\begin{pmatrix} F_{2m+1}\\ F_{2m} \end{pmatrix}$$ = $$\begin{pmatrix} F_{m+1}^{2}+F_{m}^{2}\\ F_{m}*(F_{m+1}+F_{m-1}) \end{pmatrix}$$ (F2m+1​F2m​​)=(Fm+12​+Fm2​Fm​∗(Fm+1​+Fm−1​)​)

这里须要注意一点 n 须要进行奇偶性断定：

当n为奇数时：m

=

[

n

2

]

，

n

=

2

∗

m

+

1

m=[\frac{n}{2}]，n=2*m+1m=[2n​]，n=2∗m+1 此时，(

F

n

+

1

F

n

)

(

F

2

m

+

2

F

2

m

+

1

)

(

F

m

+

1

∗

(

F

m

+

2

+

F

m

)

F

m

+

1

2

+

F

m

2

)

$$\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}$$ $$\begin{pmatrix} F_{2m+2}\\ F_{2m+1} \end{pmatrix}$$ $$\begin{pmatrix} F_{m+1}*(F_{m+2}+F_{m})\\ F_{m+1}^{2}+F_{m}^{2} \end{pmatrix}$$ (Fn+1​Fn​​)(F2m+2​F2m+1​​)(Fm+1​∗(Fm+2​+Fm​)Fm+12​+Fm2​​)

因为 F

m

+

2

=

F

m

+

1

+

F

m

F_{m+2}=F_{m+1}+F_{m}Fm+2​=Fm+1​+Fm​ ，所以，能够推导出

(

F

n

+

1

F

n

)

=

(

F

m

+

1

∗

(

F

m

+

1

+

2

∗

F

m

)

F

m

+

1

2

+

F

m

2

)

$$\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}$$ = $$\begin{pmatrix} F_{m+1}*(F_{m+1}+2*F_{m})\\ F_{m+1}^{2}+F_{m}^{2} \end{pmatrix}$$ (Fn+1​Fn​​)=(Fm+1​∗(Fm+1​+2∗Fm​)Fm+12​+Fm2​​)

当n为偶数时：m

=

n

2

，

n

=

2

∗

m

m=\frac{n}{2}，n=2*mm=2n​，n=2∗m，此时

(

F

n

+

1

F

n

)

=

(

F

2

m

+

1

F

2

m

)

=

(

F

m

+

1

2

+

F

m

2

F

m

∗

(

F

m

+

1

+

F

m

−

1

)

)

$$\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}$$ = $$\begin{pmatrix} F_{2m+1}\\ F_{2m} \end{pmatrix}$$ = $$\begin{pmatrix} F_{m+1}^{2}+F_{m}^{2}\\ F_{m}*(F_{m+1}+F_{m-1}) \end{pmatrix}$$ (Fn+1​Fn​​)=(F2m+1​F2m​​)=(Fm+12​+Fm2​Fm​∗(Fm+1​+Fm−1​)​)

因为 F

m

+

2

=

F

m

+

1

+

F

m

F_{m+2}=F_{m+1}+F_{m}Fm+2​=Fm+1​+Fm​，所以，能够推导出：

(

F

n

+

1

F

n

)

=

(

F

m

+

1

2

+

F

m

2

F

m

∗

(

2

∗

F

m

+

1

−

F

m

)

)

$$\begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix}$$ = $$\begin{pmatrix} F_{m+1}^{2}+F_{m}^{2}\\ F_{m}*(2*F_{m+1}-F_{m}) \end{pmatrix}$$ (Fn+1​Fn​​)=(Fm+12​+Fm2​Fm​∗(2∗Fm+1​−Fm​)​)

因此计算F(N)的值，只须要知道F(n/2+1)和F(n/2)便可

def fib(n):

if n < 1:

return (1, 0)

f_m_1, f_m = fib(n >> 1)

if n & 1:

return f_m_1 * (f_m_1 + 2 * f_m), f_m ** 2 + f_m_1 ** 2

else:

return f_m_1 ** 2 + f_m ** 2, f_m * (2 * f_m_1 - f_m)

时

间

复

杂

度

：

O

(

log

⁡

2

n

)

，

空

间

复

杂

度

：

O

(

1

)

时间复杂度：O(\log_2 n)， 空间复杂度：O(1)时间复杂度：O(log2​n)，空间复杂度：O(1)