0

我有一系列数字 A。有一个索引 - k，它将作为参数传递给程序。该系列是等差数列 (d=1)，直到第k个元素。例如：

A 0 = 0，A 1 = 1 [...] A k -1 = k -1。

从那时起，每个元素都是最后k个元素的总和。例如：

A k +3 = A 2 + A 3 + [...] + A k +2。

用户输入一个数字n（和k，如前所述）。程序需要计算并返回所描述的系列 A 的第n个元素。

示例： k = 5，n = 8

A 0 = 0 , A 1 = 1 , A 2 = 2 , A 3 = 3 , A 4 = 4 , A 5 = 10 , A 7 = 20 , A 7 = 39 , A 8 = 76

A = [0,1,2,3,4,10,20,39, 76 ]

一个n = 76

有什么想法吗？在过去的几天里，这一直困扰着我，但数学从来都不是我的事，所以我想这是找到一个聪明的方法的大问题（当然，除了有一个循环 - 这听起来并不聪明）。另外，对不起，如果我犯了任何错误，英语不是我的主要语言。

4

5 回答 5

5

稍微扩展 Oli Charlesworth 的答案，考虑向量

A n = [ A n , A n-1 ... A n-k+1 ]

你知道的

A n = A n-1 + ... + A n-k

所以你可以用A n-1将A n表示为

A n = B A n-1

其中B是k x k矩阵，其顶行为 1，主对角线下方为 1，其他所有位置均为零。例如，对于k = 4，您有

    1   1   1   1
B = 1   0   0   0
    0   1   0   0
    0   0   1   0

复发的解决办法是现在

A n = B n-k+1 A k-1

和

A k-1 = [k-1, k-2, k-3 ... 2, 1, 0]

使用快速矩阵求幂算法，您需要进行 log( n - k + 1) 矩阵乘法来得出答案，对于n >> k，它近似为 log( n ) 。矩阵乘法的成本是k 3所以总复杂度是k 3 log( n )

于 2013-06-06T11:18:13.923 回答
3

我不知道你是否可以在没有循环的情况下做到这一点，但你肯定可以做得比 O(n) 时间复杂度更好。如果将此递归表示为矩阵运算（类似于Fibaonacci 序列），则找到n第 - 项相当于取n矩阵的 - 次方，这可以通过O(log n) 中的快速取幂来完成时间。

于 2013-06-06T10:35:22.570 回答
0

O(1)如果您找到序列元素的封闭形式，您可以解决它。对于线性循环序列来说，这是一个非常直接的过程，它涉及到生成函数的使用。请参阅斐波那契数列的示例。

于 2013-06-07T02:36:34.380 回答
0

@ChrisTaylor 和 @OliCharlesworth 的快速矩阵求幂是要走的路。找到@AdrianPanasiuk 提到的封闭形式涉及找到要取幂的矩阵的对角化。一个足够强大的库也许可以为你做这件事。

如果不是，生成函数和线性递归归结为您需要找到多项式 x k -x k-1 -...-1=0 的所有 k 个根（包括复数根）。如果您标记根 r 1 ,r 2 ,...,r k，那么您的解决方案将采用 A n = Σ i=1 n c i r i n的形式。为了找到 c i的值，您将在 0≤n≤k-1 时插入已知的 A n以获得具有 k 个未知数的 k 个线性方程。

这可能值得所有麻烦的唯一方法是，如果您知道 k≤4，以便您可以提前完成所有可能的 k 值的所有数学运算（您将无法解决较大 k 的多项式方程）。如果你期望 n 有巨大的价值。如果您期望有很多用户查询。

于 2013-06-07T20:07:05.380 回答
-1

如果您只写出该系列的前几个术语，我想您会看到如何在恒定时间内计算它：

 0, 1, 1, 2, 4, 8, 16, 32, ...

所以我认为是 2^(n-2) （第一个任期除外）。还是我误会了？

哦，我刚刚重新阅读并看到 k 可以变化——我给出了 k=2 的答案？所以 k=3 将是：

 0, 1, 2, 3, 6, 12, 24, ... ?

肯定有一个封闭形式的解决方案；我想也许

 k * 2^(n-k);  n > k
于 2013-06-06T10:42:46.000 回答