#Allmählicher Ausdruck x_{n+1} = f(x_{n})Wenn die angegebene Spalte einen Zyklus hat
#Messen Sie die Länge l, um in den Kreislauf zu gelangen, und die Länge m des Kreislaufs
def find_cycle(x0, limit = nil, &f)
#Legen Sie ein Limit für die Anzahl der Zirkulationserkennungen fest (Terminierung Null oder Float).::Unendlich mit Unendlichkeit)
seq = 1..limit
# step1:Zirkulation erkennen
# -Sowohl x als auch y beginnen am Startpunkt (x0)
# -x rückt um eins vor, y rückt um zwei vor
# -→ Wenn Sie in den Zyklus eintreten, achten Sie auf x==Werde y
# -→ Dieses x==Die Position von y ist parallel zu x0
#(Immer f für ein ausreichend großes n^{n}(x) == f^{n}(x0)Hält)
x = y = x0
k = seq.find { (x = f[x]) == (y = f[f[y]]) }
raise "failed to detect a cycle" unless k
# step2:Messen Sie die Länge, um in den Zyklus einzutreten
# -Kehren Sie x zum Startpunkt zurück und y fahren Sie am Ende von Schritt 1 fort
# -X und y nacheinander vorrücken (parallele Positionsbeziehung beibehalten)
# -→ Achten Sie beim Betreten des Zyklus auf x==Werde y
x = x0
l = (x == y) ? 0
: seq.find { (x = f[x]) == (y = f[y]) }
# step3:Messen Sie die Länge der Zirkulation
# -Sowohl x als auch y beginnen in einem Zyklus (hier am Ende von Schritt 2).
# -x rückt um eins vor, y rückt um zwei vor
# -→ x ist genau eine Runde und immer x==Werde 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}(Und x_{l-1} != x_{l+m-1}) Sollte sein
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