2

我在 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.

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

如果有人可以举例说明，那就太好了。

4

3 回答 3

8

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

您有一些不重复的值；这些形成一条线或“字母”的“词干”。然后这些值进入一个循环或循环，形成一个圆圈或“字母”的“循环”。

例如，考虑重复小数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

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

于 2016-01-02T14:30:06.577 回答
2

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

# 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}序列的“尾部”在你到达尾部所连接的圆圈之前。

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

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

可以写成

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

哪种看起来像倒塌的rho。

Collat ​​z 猜想是所有种子都产生 rho 形序列，最终在长度为 3 的相同循环中结束。

于 2016-01-02T14:40:54.657 回答
0

如果您有一个变成循环的序列，那么在初始序列与循环相遇的点处，您可以通过两种方式获得一个值，无论是从初始序列还是从循环。

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

于 2016-01-02T14:18:13.080 回答