#Expression progressive x_{n+1} = f(x_{n})Lorsque la colonne donnée dans a un cycle
#Mesurer la longueur l pour entrer dans la circulation et la longueur m de la circulation
def find_cycle(x0, limit = nil, &f)
#Définir la limite du nombre de détections de circulation (terminaison nulle ou flottante)::Infini avec INFINITY)
seq = 1..limit
# step1:Détecter la circulation
# -Les deux x et y commencent au point de départ (x0)
# -x avance de un, y avance de deux
# -→ Si vous entrez dans le cycle, assurez-vous de x==Devenez y
# -→ Ce x==La position de y est parallèle à x0
#(Toujours f pour un n suffisamment grand^{n}(x) == f^{n}(x0)Tient)
x = y = x0
k = seq.find { (x = f[x]) == (y = f[f[y]]) }
raise "failed to detect a cycle" unless k
# step2:Mesurer la longueur pour entrer dans le cycle
# -Remettre x au point de départ et y continuer à partir de la fin de l'étape 1
# -Avancez x et y un par un (maintenez une relation de position parallèle)
# -→ Assurez-vous de x lorsque vous entrez dans le cycle==Devenez y
x = x0
l = (x == y) ? 0
: seq.find { (x = f[x]) == (y = f[y]) }
# step3:Mesurer la longueur de la circulation
# -Les deux x et y commencent dans un cycle (ici à la fin de l'étape 2)
# -x avance de un, y avance de deux
# -→ x est exactement un tour et toujours x==Devenez y
m = seq.find { (x = f[x]) == (y = f[f[y]]) }
[l, m]
end
if $0 == __FILE__
#Test: x_{n+1} ≡ x_{n} * 2 (mod 360), x_{0} = 133
l, m = find_cycle(133) { |x| x * 2 % 360 }
p [l, m]
# x_{l} == x_{l+m}(Et x_{l-1} != x_{l+m-1}) Devrait être
ary = (l + m).times.inject([133]) { |a, _| a << (a.last * 2 % 360) }
ary.each_with_index { |x, i| puts "%3d %4d" % [i, x] }
end
Recommended Posts