Die Fibonacci-Folge ist eine bekannte Folge, in der jeder Eintrag die Summe der beiden vorhergehenden und die ersten beiden Einträge 1 ist. Wenn wir das Modulo jedes Terms mit einer Konstanten nehmen, wird die Folge periodisch. Wenn wir uns zum Beispiel dazu entschließen, die Sequenz Mod 7 zu berechnen, erhalten wir Folgendes:
1 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1 1 ...
Dies hat eine Periode von 16. Eine verwandte Sequenz, die Pisano-Sequenz genannt wird , ist so definiert, dass dies a(n)
die Periode der Fibonacci-Sequenz ist, wenn sie modulo n berechnet wird.
Aufgabe
Sie sollten ein Programm oder eine Funktion schreiben, die bei Angabe n
die Periode des Fibonacci-Sequenzmods berechnet und ausgibt n
. Dies ist der n-te Term in der Pisano-Sequenz.
Sie müssen nur Ganzzahlen im Bereich unterstützen 0 < n < 2^30
Dies ist ein Code-Golf- Wettbewerb, daher sollten Sie versuchen, die Größe Ihres Quellcodes nach Bytes zu minimieren.
Testfälle
1 -> 1
2 -> 3
3 -> 8
4 -> 6
5 -> 20
6 -> 24
7 -> 16
8 -> 12
9 -> 24
10 -> 60
11 -> 10
12 -> 24
f(i),f(i+1)
höchstensn^2
Werte mod annehmen könnenn
. Somit könnten
begrenzt auf2^30
einen Zeitraum von bis zu produzieren2^60
. Einschränkungn <= 2^16
würde gebenP(n) <= 2^32
.f(i+2) = f(i+1)+f(i)
, dass der 'Status' einer Maschine, die über den Zeitraum eine Schleife durchläuft, mit einem Paar Ganzzahlen mod beschrieben werden kannn
. Es gibt höchstensn^2
Staaten, also höchstens eine Perioden^2
. Oh! Wikipedia behauptet, dass die Periode höchstens ist6n
. Vergiss meine Trivialität.Antworten:
GolfScript (
28 25 2423 Zeichen)Nimmt die Eingabe in stdin auf, belässt sie auf stdout (oder auf dem Stack, wenn Sie sie weiter verarbeiten möchten ...)
Dies behandelt die Eckfälle korrekt ( Demo ).
Aus Gründen des Interesses für GolfScript-Programmierer denke ich, dass dies das erste Programm ist, das ich mit einer Entfaltung geschrieben habe, die tatsächlich kürzer ausfiel als die anderen Ansätze, die ich ausprobiert habe.
quelle
GolfScript, 24 Zeichen
Nächste Iteration einer GolfScript-Implementierung. Die zweite Version behandelt nun auch 1 korrekt. Es wurde ziemlich lang, aber vielleicht kann jemand einen Weg finden, diese Version zu verkürzen. Sie können die obige Version online testen .
quelle
1
korrekt verarbeitet?1
- und immer noch nur 24 Zeichen.Python,
1881321019587 ZeichenVerwendung
Beispielsweise:
quelle
cat
ting zuwc -c
und ich die gleiche Nummer.if k>0 and s[0:k]==s[k:]:break
kann geändert werden zuif s and s[:k]==s[k:]:break
. Sie können auch erheblich reduzieren, indem Sie den Iterator entfernen, diefor
Schleife auf ändernwhile 1:
unda,b=a,a+b
am Ende der while-Schleife ausführen .Python
908596949082Edit: Vorschläge von beary und primo umgesetzt
quelle
a.append(c) -> a+=[c]
((n>1)>>(c in a)) -> (n>1)>>(c in a)
append
hat tatsächlich eine andere Funktionalität als+=
. Vielen Dank für die Tipps.(n>1)>>(c in a)
->
(c in a)<1%n
für 3 Bytes. Und ich stimme Beary in Bezug auf den Anhang zu. Unabhängig davon, ob Sie einen Verweis anfügenc
oder uma
den Wert von erweiternc
, ist dies in beiden Fällen genauso (da Sie den Verweis aufc
sowieso sofort zerstören ).a+=c
statta+=[c]
Mathematica 73
quelle
PHP -
6157 BytesDieses Skript wird fälschlicherweise berichten
2
fürn=1
, aber alle anderen Werte korrekt sind.Sample I / O, eine links abschneidbare Reihe mit π (n) = 2n + 2:
quelle
1<$a.$b=+$a+$a=!$i+++$b%$n+=fgets(STDIN)
Oh Gott, das ist genau dort, wo es um die Ausbeutung von Operationen geht.PowerShell: 98
Golf Code:
Ungolfed, mit Kommentaren:
Anmerkungen:
Ich bin mir nicht sicher, wie hoch das maximale zuverlässige Limit für $ n mit diesem Skript ist. Es ist ziemlich wahrscheinlich weniger als 2 ^ 30, da $ x möglicherweise ein int32 überlaufen könnte, bevor $ n dort ankommt. Außerdem habe ich die Obergrenze nicht selbst getestet, da die Laufzeit des Skripts auf meinem System bereits 30 Sekunden für $ n = 1e7 betrug (was nur etwas über 2 ^ 23 liegt). Aus dem gleichen Grund bin ich nicht schnell dazu geneigt, zusätzliche Syntax zu testen und Fehler zu beheben, die zum Aktualisieren der Variablen auf uint32, int64 oder uint64 erforderlich sind, um den Bereich dieses Skripts zu erweitern.
Beispielausgabe:
Ich habe dies in eine andere for-Schleife eingewickelt:
Setzen Sie dann
$n=$i
statt=read-host
und ändern Sie die Ausgabe,"$i | $x"
um sich ein Bild von der allgemeinen Zuverlässigkeit des Skripts zu machen. Hier sind einige der Ausgaben:...
Nebenbemerkung:
Ich bin mir nicht sicher, wie einige Pisano-Perioden deutlich kürzer als $ n sind. Ist das normal oder stimmt etwas mit meinem Skript nicht?Nevermind - Ich habe mich gerade daran erinnert, dass Fibonacci-Zahlen nach 5 sehr schnell viel größer werden als ihre Position in der Sequenz. Das macht jetzt also Sinn.quelle
Perl,
75,61, 62 + 1 = 63Verwendung
Ungolfed
+1 Byte für
-n
Flag. Dank Gabriel Benamy 13 Bytes gespart.quelle
$n=<>;
(-6) loswerden und durch das-n
Flag (+1) ersetzen , dann können alle Instanzen von$n
durch ersetzt werden$_
. Sie können-M5.010
kostenlos verwenden, wodurch Sie densay
Befehl anstelle vonprint
(-2) verwenden können. Modifikatoranweisungenwhile
benötigen keine Klammern um die Bedingung (-2). Stattdessen@{[%h]}/2
können Sie einen Zähler$a++,
vor($m,$k)=
und dann nursay$a-1
am Ende haben (-2). Anstelle von"$m,$k"
use$m.$k
(-2). Dies sollte$k=1%$_;$a++,($m,$k)=($k,($m+$k)%$_)while!$h{$m.$k}++;say$a-1
mit dem-n
Flag für 61 + 1 = 62 Bytes erreicht werden."$m,$k"
statt$m.$k
(+2), aber Sie können 1 Byte sparen, indem Siewhile!$h
aufuntil$h
(-1) wechseln . Es tut uns leid!$m.$k
scheitert das? Es schien an meinem Ende zu arbeiten.Clojure, 102 Bytes
Nicht zu aufregend, iteriert die Formel, bis wir zurückkommen
[1 1]
(ich hoffe, das ist immer der Fall). Besondere Behandlung(f 1)
wie es konvergiert[0 0]
.quelle