线性递归数列算法题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了线性递归数列算法题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含790字，纯文字阅读大概需要2分钟。

内容图文

1 线性递归数列

       若数列(序列)\(a_n\) 满足\(a_n\)可由\(a_n\)前k项线性生成，则称\(a_n\)是线性递归数列，即有:
\[ a_n = b_1a_{n-1} + b_2a_{n-2} + ... + b_ka_{n-k} \]

        其中\(b_i\)是常数

• 使用矩阵乘法 + 快速幂原理可以在O(logN)时间内得到答案
• 使用数列通项公式可以在O(1)时间内得到答案

2 Python代码

以斐波那契数列数列为例说明

import numpy as np
import datetime

A = [[1,1], [1, 0]]
a1 = [[1],[1]]

mat_a1 = np.asarray(a1)


for n in range(3, 39+1):
    # 矩阵乘法 + 快速幂
    t1_s = datetime.datetime.now()
    mat_R = np.asarray([[1,0], [0,1]])
    mat_A = np.asarray(A)

    r = n - 2
    while r > 0 :
        if r & 1 == 1:
            mat_R = mat_R.dot(mat_A)
        mat_A = mat_A.dot(mat_A)
        r >>= 1

    F_n = mat_R.dot(mat_a1)[0][0]
    t1_e = datetime.datetime.now()
    print("F_%d = %d\t cost time(1E-6s):%d" % (n, F_n, (t1_e - t1_s).microseconds))

图1 代码运行展示

内容总结

以上是互联网集市为您收集整理的线性递归数列算法题全部内容，希望文章能够帮你解决线性递归数列算法题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---