我遇到了这个问题,对此我感到很困惑,但我不知道(而且似乎没有令人满意的答案)。我敢复制到这里:
假设我们有一个流,每个元素取决于它的前一个元素,就像对于siimple伪随机序列,例如:

def neum(a:Int): Stream[Int] = Stream.iterate(a)(a => (a*a/100)%10000)

这是一个von Neumann的随机数发生器
从给定的值开始,我们想知道序列何时进入循环。我们可以使用一组存储值的命令形式轻松地执行此操作:
// like in java
Set<Integer> values = new HashSet<>();
while (true) {
    int x = nextValueInSequence(x)
    if (values.contains(x)) {
        break;
    }
    values.add(x);
}

不过,对于scala来说,提出“功能性”解决方案是很有趣的。但是这个问题的作者似乎不知道如何保持“cccc>时间复杂性”。我也是。这里唯一的评论似乎是建议直接的O(N)解决方案。

最佳答案

我相信,有一个算法,具有O(n log n)时间复杂度(可能会提高到O(n))和O(1)总内存消耗。也就是说,我们不必记住之前的大多数数字不过,常数因子相当高。
这种内存消耗不是用Stream计算的,而是用一个由起始元素和递归公式定义的常规数字序列计算的。例如Iterator.iterate(start)(a => a * a / 100 % 10000)
Stream将记住以前的结果,并有效地使其成为o(n)内存。
假设序列在循环开始之前有p≥0个元素,在循环中有l≥1个元素。例如,序列[2, 10, 13, 9, 11, 17, 11, 17, ...]具有p=4和l=2。我们需要找到P+L。
在算法中,我们必须遍历序列。我将当前位置称为“指针”。在数字序列中,指针只表示一个数字。最初,指针等于序列的起始元素,要将指针向前移动一步,我们必须对其应用递归公式。
现在来看看算法:
从两个指向序列开头的指针开始:“slow”和“fast”慢速指针一次移动1步,快速指针一次移动2步(即递归公式的两个应用)。
最初指针是相等的开始向前移动,直到它们再次相等,并跟踪慢速指针的步数。让我们命名指针的步数,使其再次相等k0。可以证明,p≤k0在这一步中,我们还应该特别注意当p=0时的情况:当指针变得相等时,如果它们也等于起始元素,我们应该设置k0=0,以便以后能够区分这种情况。
这个步骤的时间复杂度是O(n)。
现在指针肯定在序列的循环中。再次开始向前移动它们,并跟踪慢指针的步数,直到它们再次相等这个步数是序列的循环l的长度。(也可以在这个步骤中只移动慢指针,直到它回到相同的位置,但是我将重用函数来同时移动这两个函数,这不会增加时间复杂度)
这个步骤的时间复杂度是O(n)。
现在我们必须计算p。我们可以注意到,如果在算法的第2)步中,我们不是从一开始就启动“快速”指针,而是使用一些移位s:0≤s这个步骤的时间复杂度是O(n log n),因为二进制搜索中的每一步都取O(n)。
所以我们有一个算法,它在O(N logn)和O(1)内存中工作下面是代码示例:

case class Sequence[T](start: T)(f: T => T) {
  def next = Sequence(f(start))(f)
  def forward(steps: Int) =
    Sequence(Function.chain(List.fill(steps)(f))(start))(f)
}

object Sequence {
  def neum(a: Int) = Sequence(a)(a => a * a / 100 % 10000)

  def movesToEquality[T](
    slow: Sequence[T], fast: Sequence[T], count: Int = 1
  ): (Sequence[T], Int) = {
    val nextSlow = slow.next
    val nextFast = fast.forward(2)
    if (nextSlow == nextFast) (nextSlow, count)
    else movesToEquality(nextSlow, nextFast, count+1)
  }

  def findLoopStart[T](seq: Sequence[T]): Int = {
    val (inLoop, k0) = movesToEquality(seq, seq) match {
      case (c, k) if c == seq => (c, 0)
      case other => other
    }
    val (_, loopSize) = movesToEquality(inLoop, inLoop)

    def binarySearch(lo: Int, hi: Int): Int = {
      if (lo + 1 >= hi) lo
      else {
        val mid = (lo + hi) / 2
        if (movesToEquality(seq, seq.forward(mid))._2 == k0 - mid)
          binarySearch(mid, hi)
        else
          binarySearch(lo, mid)
      }
    }

    k0 - binarySearch(0, loopSize) + loopSize
  }
}

object Main extends App {
  println(Sequence.findLoopStart(Sequence.neum(1)))
  println(Sequence.findLoopStart(Sequence.neum(4100)))
  println(Sequence.findLoopStart(Sequence.neum(5761)))
}

10-02 21:13