但是,我不知道k或m是多少 - 我的目标是将序列[a_1,a_2,...,a_n]作为输入,并输出序列[a_1,...,a_k,[a_(k+1),...,a_(k+m)]] - 基本上通过将大部分序列列为重复块来截断较长的序列。
有没有高效的方法来解决这个问题?而且,更理想的是计算方面更难但更好 - 是否可能在生成所需序列时进行操作,以便我只需要生成最小量?我已经查看了这个站点上的其他类似问题,但它们似乎都处理没有起始非重复位的序列,并且通常不必担心内部重复。
如果有帮助/有用的话,我也可以说明为什么我在研究这个问题以及我将用它做什么。
谢谢!
编辑:首先,我应该提到我不知道输入序列是否恰好在重复块的末尾结束。
我试图解决的实际问题是写出二次无理数(实际上是负的)连分数展开的一个漂亮的封闭式表达式。对于这些CFE的部分商*,很容易产生任何精度的结果 - 然而,在某个点上,二次无理数的CFE的尾部会成为一个重复块。我需要处理这个重复块中的部分商。
我的当前想法是:也许我可以调整一些建议从右边开始工作的算法,使其适用于这些序列之一。或者,也许在二次无理数为周期性的证明中有一些东西可以帮助我看到为什么它们开始重复,这将帮助我想出一些简单的检查标准。 *如果我将一个连分数扩展写成[a_0,a_1,...],我将a_i称为部分商。
对于那些感兴趣的人,可以在这里找到一些背景信息:http://en.wikipedia.org/wiki/Periodic_continued_fraction
k
/m
有任何限制吗?还是你只想要一个“最佳猜测”算法来逐步操作(针对“随着生成”的部分)? - Danica