Что такое последовательность в форме rho?

Question

Я наткнулся на это в решении, представленном Саурабх Kr Чаны в этом 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. 

Я искал в Интернете и достигли https://en.wikipedia.org/wiki/Cycle_detection.I мог видеть Rho фасонный образуется, когда мы достигаем старт/конец цикла и попытайтесь перейти к элементу, который не смежен с ним. Однако я не понял представления последовательности или ее использования.

Было бы здорово, если бы кто-нибудь мог объяснить это на примере.

Answer 1

Это означает буквально в форме греческой буквы rho, который является «ρ». Идея состоит в том, что если вы выставляете значения в виде графика, визуальное представление формирует эту форму. Вы могли бы также подумать об этом как «d» или «p». Но внимательно посмотрите на шрифт и обратите внимание на то, что линия или стержень немного простираются мимо петли, в то время как она не на rho. Rho - лучшее описание формы, потому что цикл никогда не выходит; то есть не должно быть линий, выходящих из цикла. Это и математики любят греческие буквы.

У вас есть несколько значений, которые не повторяются; они образуют линию или «стержень» «буквы». Затем значения вводятся в цикл или цикл, образуя круг или «цикл» букв.

Например, рассмотрите repeating decimals 7/12 (0.5833333 ...) и 3227/55 (5.81441441444 ...). Если вы сделаете свою последовательность цифрами в номере, вы можете нарисовать их, чтобы сформировать форму rho. Давайте посмотрим на 3227/55.

• x0 = 5
• x1 = 8
• х2 = 1
• x3 = 4
• x4 = 4
• х5 = 1 = х2
• х6 = 4 = x3
• x7 = 4 = x4
• ...

Вы можете построить график так:

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

Вы можете увидеть это образует «р» форму.

Answer 2

Если у вас есть последовательность, которая превращается в цикл, то в точке, где начальная последовательность соответствует циклу, есть значение, которое вы можете получить двумя способами: либо из начальной последовательности, либо из цикла.

Я не знаю, является ли это представительным примером, но предположим, что массив содержит {1,2,3,1,0}, и вы начинаете с 0. Затем вы получаете 0-> 1-> 2-> 3-> 1-> 2-> 3-> 1 ... и вы обнаружите, что f (0) = f (3) = 1

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} «хвост» последовательности, прежде чем попасть в круг, что хвост прилагается.

Хороший пример предоставлен проблемой 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-образные последовательности, которые в конечном итоге в том же цикле длины 3.