我发现了一个问题,你得到了这种类型的序列:
你有
the first K terms : a1, a2, ... , ak;
K coefficients : b1, b2, ... , bk
和重复:
S(i) = b1*S(i-K) + b2*S(i-K+1) + ... + bk*S(i-1).
我必须找出第 N 项。
我相信这个问题可以通过快速矩阵求幂来解决,但我很难找到我必须使用的矩阵。我正在尝试用 C++ 编写问题。谁能给我一些关于我应该如何处理这类问题的提示?
最佳答案
作为无耻的 self 推销,我编码了a program to solve linear recurrences using matrix multiplication .文件顶部的注释描述了您要形成的矩阵是什么,以及如何使用重复平方算法有效地计算递归的第 n 项。
希望这对您有所帮助!
关于c++ - 在 C++ 中查找序列中的第 N 项,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16021545/