线性递归数列算法题

桃扇骨 2023-08-17 15:16 67阅读 0赞

# 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))

![1180694-20190918225439624-363649170.jpg][]  
图1 代码运行展示

转载于:https://www.cnblogs.com/Kalafinaian/p/11546178.html

[1180694-20190918225439624-363649170.jpg]: /images/20230810/e7745e4d53e944f487d9cd6ebeb9598d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，67人围观）

还没有评论，来说两句吧...

相关阅读

相关线性递归数列算法题

1 线性递归数列若数列(序列)\\(a\_n\\) 满足\\(a\_n\\)可由\\(a\_n\\)前k项线性生成，则称\\(a\_n\\)是线性递归数列

桃扇骨/ 2023年08月17日 15:16/ 0 赞/ 68 阅读

相关算法：栈模拟递归斐波那契数列

题目来源 [LEETCODE][] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_

快来打我*/ 2023年02月16日 00:42/ 0 赞/ 99 阅读

相关斐波那契数列实现方法递归解决、递归优化算法

首先基础的递归算法 include <stdio.h> include <string.h> include <windows.h> incl

以你之姓@/ 2022年12月27日 01:13/ 0 赞/ 101 阅读

相关递归算法——阶乘、斐波那契数列

文章目录前言一、什么是递归算法？二、递归算法特点三、递归算法的使用要求四、应用示例——阶乘 1.阶乘概述

蔚落/ 2022年10月28日 14:28/ 0 赞/ 180 阅读

相关线性递归和尾递归

在[数据结构][Link 1]与[算法][Link 1]中，包括在做《剑指OFFER》的过程中，很多时候都会用到递归，之前对尾递归概念模模糊糊的，看了很多前辈写的博客，这里对其

我会带着你远行/ 2022年10月19日 04:25/ 0 赞/ 177 阅读

相关斐波那契数列（递归与非递归算法）

斐波那契数列，又称[黄金分割][Link 1]数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F

一时失言乱红尘/ 2022年09月19日 15:29/ 0 赞/ 217 阅读

相关 LeetCode 外观数列【递归】

1 外观数列给定一个正整数 n ，输出外观数列的第 n 项。「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。你可以将其视作是由递

今天药忘吃喽~/ 2022年09月10日 13:11/ 0 赞/ 119 阅读

相关递归——线性递归与二分递归

递归线性递归例子1：数组求和 int sum( int A[], int n) { //数组求和算法：线性递归版 if

向右看齐/ 2022年05月21日 04:41/ 0 赞/ 296 阅读

相关递归算法--斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39 很容易我们想到使用递归求解： public

刺骨的言语ヽ痛彻心扉/ 2022年05月18日 01:06/ 0 赞/ 171 阅读

相关递归算法实现斐波那契数列

假定兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？这就是著名的斐波那契数列，也称作兔子数列。 >

Dear 丶/ 2022年05月14日 05:42/ 0 赞/ 186 阅读