查找第n项在序列c ++ [英] Find the Nth term in a sequence in C++

问题描述

我已经找到了，你给出这种类型序列的问题：

I have found a problem in which you are given this type of sequence:

您

  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项。

I have to find out the Nth term.

我相信这个问题能够快速矩阵幂来解决，但我有困难时期发现我不得不使用矩阵。我想用C ++的问题。任何人都可以给我一些提示有关我应该如何处理这类问题？

I believe this problem can be solved with fast matrix exponentiation but I am having hard time discovering the matrices I have to use. I am trying to write the problem in C++. Can anyone give me some hints about how should I treat this type of problem?

推荐答案

作为一个无耻的自我推销，我codeD起来的一个程序来解决使用矩阵乘法的线性复发。在该文件的顶部的注释描述什么要形成基质是，以及如何使用重复平方算法来有效地计算复发的第n项

As a shameless self-promotion, I coded up a program to solve linear recurrences using matrix multiplication. The comments at the top of the file describe what the matrix you want to form is, as well as how to use the repeated squaring algorithm to efficiently compute the nth term of the recurrence.

希望这有助于！

这篇关于查找第n项在序列c ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！