0

是否有可能在很大一部分数字中找到循环长度(超过 C/C++ 中最大整数类型的最大值,比如说 2^20),而不涉及磁盘来执行它?最好的情况是按顺序分析它们,因为它们来自标准输入,但我很确定这是不可能的,我需要将它们存储在内存中。但我希望我是错的。数字值是整数,它们来自标准输入。

示例:输入:( 1 2 3 ... (2^20 三元组 1 2 3) ... 1 2 3) 期望结果:3

编辑

让我们将周期视为一个周期(f(x) = f(x+t) 对于某些 t) - 寻找 t 的值

假设操作内存太少,无法存储所有数字(数字可以超过 2^20)并且可能是 gmp 类型。

4

2 回答 2

2

这是一个经过充分研究的问题,有很多算法取决于您的资源和约束到底是什么:

http://en.wikipedia.org/wiki/Cycle_detection

您不需要将所有内容都存储在内存中(基本算法中只需两个指针/索引),但您需要能够多次访问该序列。

也可以看看:

弗洛伊德的循环寻找算法

于 2012-10-08T21:11:12.723 回答
1

查找句点长度的标准方法是想象您的序列是整数字母表上的字符串 S,然后找到可以在字符串 SS 中找到 S 的最左侧位置(大于 0)(字符串 S 的串联与自身)。也就是说,如果S = 'abcabc',您必须找到i大于零的第一个位置,以便i在字符串中的位置找到SS = 'abcabcabcabc'S。在这种情况下,这是 3,这就是周期的长度。

这可以通过任何具有线性性能的字符串搜索算法来完成,并且对于现代计算机上的 2^20 个数字应该可以正常工作。我怀疑您是否可以避免将数字保存在内存中。

于 2012-10-08T21:04:34.597 回答