我的问题是:我有一大堆数字.我知道,在某一点之后,它变成了周期性的 - 也就是说,在序列的开头有k个数字,然后还有更多的数字在序列的其余部分重复.作为一个更清楚的例子,序列可能如下所示:[1,2,5,3,4,2,1,1,3,2,1,1,3,2,1,1,3 ,...],其中k是5,m是4,然后重复块是[2,1,1,3].从这个例子可以清楚地看出,我可以在较大的块内部重复位,因此只查找重复的第一个实例是没有用的.
但是,我不知道k或m是什么 - 我的目标是将序列[a_1,a_2,...,a_n]作为输入并输出序列[a_1,...,a_k,[a_(k) +1),...,a_(k + m)]] - 基本上通过将其中的大部分列为重复块来截断较长的序列.
有没有一种有效的方法来解决这个问题？此外,计算可能更难但更理想 - 我可以在生成相关序列时执行此操作,这样我必须生成最小量？我在这个网站上看过其他类似的问题,但它们似乎都处理序列而没有开始的非重复位,并且通常不必担心内部重复.
如果它有用/有用,我也可以了解为什么我要看这个以及我将用它做什么.
谢谢!
编辑:首先,我应该提到我不知道输入序列是否恰好在重复块的结尾处结束.
我试图研究的现实世界问题是为二次非理性(实际上是负CFE)的连续分数扩展(CFE)写一个漂亮的,封闭形式的表达式.为这些CFE生成部分商*非常简单 - 但是,在某些时候,二次无理的CFE尾部变成了重复块.我需要在这个重复块中使用部分商.
我目前的想法是这样的:也许我可以调整一些建议的算法,从右边开始使用其中一个序列.或者,也许有证据表明为什么二次非理性是周期性的,这将有助于我理解为什么它们开始重复,这将帮助我提出一些简单的标准来检查.
*如果我将[a_0,a_1,...]作为连续分数展开,我将a_i称为部分商.
有兴趣的人可以在这里找到一些背景信息:http://en.wikipedia.org/wiki/Periodic_continued_fraction