什么是 rho 形序列？

Question

我在 Saurabh Kr Vats 提出的解决方案中遇到了这个 http://www.careercup.com/question?id=14990323

他说：

# Finally, the sequence could be "rho-shaped." In this 
# case, the sequence looks something like this: 
# 
# x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j} 
# ^ | 
# | | 
# +-----------------------+ 
# 
# That is, the sequence begins with a chain of elements that enters a cycle, 
# then cycles around indefinitely. We'll denote the first element of the cycle 
# that is reached in the sequence the "entry" of the cycle.

我上网搜索到了cycle detection。当我们到达一个循环的 start/end 并尝试去一个不相邻的元素时，我可以看到 rho 形状正在形成。然而，我不理解序列的表示或其用法。

如果有人能举例说明就太好了。

Answer 1

如果您有一个变成循环的序列，那么在初始序列与循环相交的点上，您可以通过两种方式获得一个值，即从初始序列或从循环中。

我不知道这是否是一个有代表性的例子，但假设数组包含 {1,2,3,1,0} 并且你从 0 开始。然后你以 0->1- >2->3->1->2->3->1... 你会发现 f(0)=f(3)=1

Answer 2

字面意思是希腊字母rho的形状，即“ρ”。这个想法是，如果您将值映射为图形，则视觉表示形式会形成此形状。您也可以将其视为 "d" 形或 "p" 形。但仔细观察字体并注意线条或词干略微延伸超过循环，但它不在 rho 上。 Rho 是对形状的更好描述，因为循环永远不会退出；即，不应有任何线路引出循环。那和数学家喜欢希腊字母。

您有一些不重复的值；这些形成一行或 "letter" 的 "stem"。这些值然后进入循环或循环，形成一个圆圈或 "letter".

的 "loop"

例如，考虑 repeating decimals 7/12 (0.5833333...) 和 3227/55 (5.81441441444...)。如果您将数字中的数字作为序列，那么您可以将它们绘制成一个 rho 形状。再来看3227/55

x0 = 5
x1 = 8
x2 = 1
x3 = 4
x4 = 4
x5 = 1 = x2
x6 = 4 = x3
x7 = 4 = x4
...

你可以这样画：

5 -> 8 -> 1 
         ^  \
        /    v
        4 <- 4

你可以看到这形成了一个“ρ”形状。

Answer 3

代码段中的注释看起来不完整。在上下文中，我认为

# x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}

应该是

# x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j} = x_k

这将使 j 循环的长度和 x_0 -> x_1 -> ... -> x_{k-1} 序列的 "tail" 在你到达尾巴所附的圆之前。

3n+1 问题提供了一个很好的例子。这是您从正整数种子数开始的地方，如果它是偶数则除以 2，如果它是奇数则乘以 3 并加 1。对于种子 5，这给出了序列

5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> ...

可以这样写

5 -> 16 -> 8 -> 4
               /  \
              1 <- 2

哪个看起来像倒下的 rho。

Collatz Conjecture 是所有种子产生 rho-shaped 序列，这些序列最终在长度为 3 的相同循环中结束。

什么是 rho 形序列？

What is a rho shaped sequence?

algorithm

function

cycle-detection