回 帖 发 新 帖 刷新版面

主题:[讨论]求解一维数组周期的最佳算法是否存在

大概有三四年没写代码,手都生啦
目前遇到一个瓶颈,涉及到周期最佳算法是否存在的问题

有一个已知函数t(X),生成一维无穷数组{X1,X2,X3.....}
已知如果其周期存在,则其周期 T<=m
并从第n位开始必然出现循环 n=1,2,3... 
m已知 且n<m
比如数组 {2,4,8,16,4,8,16......}
有 m=3 n=2
求解最小周期t
能否给出类似一维数组周期的最佳算法,因为m一般比较大
\
有两点补充
1,准确说m是最小周期t的正整数倍
或者说题目应该是求最小周期t
第2点补充:
并不知道n的确切数值,n值未必是最小的
其实如果知道n,就能求出Xn的值
Xn作为循环的起始位,可以从Xn+1开始逐一判断
直到Xi=Xn,得出t=i-n

回复列表 (共1个回复)

沙发

更新问题,大家看过一下
有朋友说,把从  n 到 m 的数看作一个模式串,相当于做一次 KMP 处理
不太明白,因为这个模式串会很长,是不是最快的算法呢?

我来回复

您尚未登录,请登录后再回复。点此登录或注册