Definition
Die Fibonacci-Sequenz F(n)
auf den positiven ganzen Zahlen ist wie folgt definiert:
1. F(1) = 1
2. F(2) = 1
3. F(n) = F(n-1) + F(n-2), where n is an integer and n > 2
Das Fibonacci-Orial einer positiven ganzen Zahl ist das Produkt von [F(1), F(2), ..., F(n)]
.
Aufgabe
Bei positiver Ganzzahl n
finden Sie das Fibonacci-Orial von n
.
Technische Daten
Die Fibonacci-Zeitmessung von 100
muss auf einem vernünftigen Computer in weniger als 5 Sekunden berechnet werden.
Testfälle
n Fibonacci-orial of n
1 1
2 1
3 2
4 6
5 30
6 240
7 3120
8 65520
9 2227680
10 122522400
11 10904493600
12 1570247078400
13 365867569267200
14 137932073613734400
15 84138564904377984000
16 83044763560621070208000
17 132622487406311849122176000
18 342696507457909818131702784000
19 1432814097681520949608649339904000
20 9692987370815489224102512784450560000
100 3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000
Antworten:
Mathematica, 10 Bytes
Ein weiteres Mathematica-System, das von einer Golfsprache ohne das eingebaute System geschlagen wird.
quelle
Gelee , 6 Bytes
Die Eingabe 100 wird in 500 ms lokal beendet. Probieren Sie es online!
Wie es funktioniert
quelle
+¡1
ein nicht in n gebautes Fibonacci und+С1
sind die ersten n Fibonacci-Zahlen?Eigentlich 4 Bytes
Führt die Eingabe 100 innerhalb von 0,2 Sekunden aus. Code:
Erläuterung:
Verwendet die CP-437- Codierung. Probieren Sie es online! .
quelle
Brainfuck,
11981067817770741657611603Unkomprimiert mit Kommentaren:
Probieren Sie es online!
Die Laufzeit für n = 100 ist mit dem Online-Interpreter kürzer als 1 Sekunde (ca. 0,2s lokal mit meinem eigenen Interpreter). Die maximale Eingabe beträgt 255, der Interpreter muss jedoch ~ 54000 Zellen unterstützen (der Online-Interpreter scheint 64 KB zu verarbeiten).
Änderungsprotokoll
Es wurden ca. 130 Bytes gespeichert, wobei die aktuelle Ziffer besser extrahiert und durch Zusammenführen von Addieren und Übertragen in einem Durchgang multipliziert werden konnte. Es scheint auch ein bisschen schneller zu sein.
Weitere 250 Bytes gespeichert. Ich habe es geschafft, meinen Multiplikations-Notizblock um zwei Zellen zu verkleinern, wodurch fast überall Bytes gespart werden, da ich nicht so weit zwischen den Ziffern wechseln muss. Ich habe auch den Übertrag nach dem Multiplizieren mit einer Ziffer verworfen und stattdessen einen vollständigen Übertrag ausgeführt, während ich die laufende Summe addiere.
Hieb weitere 50 ab, wieder mit besserer Extraktion der aktuellen Ziffer zum Multiplizieren mit, indem man sie einfach die erste Iteration nicht vorwärts bewegt und von dort aus arbeitet, wo sie ist. Ein paar Mikrooptimierungen weiter unten machen ungefähr 10 Bytes aus.
30 weitere sind weg. Das Markieren von Ziffern, die bereits mit einer 0 statt einer 1 belegt wurden, erleichtert das Auffinden. Außerdem wird die Prüfung, ob die Multiplikationsschleife beendet ist, einfacher.
Ich habe den Notizblock um eine weitere Zelle verkleinert, um weitere 80 Byte. Ich habe dazu den Marker für das vorherige Produkt und die aktuelle laufende Summe zusammengeführt, was die Verschiebungen zwischen den Lücken verringert und die Buchhaltung ein wenig erleichtert.
Sparte weitere 50, indem du eine weitere Zelle eliminierst und den Marker für die Fibonacci-Ziffern wieder verwendest, um auch die zuletzt aufgenommene Ziffer zu markieren. Ich konnte auch die Schleife zusammenführen, um die vorherigen Summen mit der ziffernweisen Multiplikationsschleife zu verschieben.
8 Bytes beim Parsing der Eingabe gespeichert. Hoppla.
quelle
Python, 45 Bytes
Die Eingabe erfolgt aus stdin. Die Ausgabe für n = 100 wird zu schnell beendet, um eine genaue Zeitangabe zu erhalten. n = 1000 dauert ungefähr 1s.
Beispielnutzung
quelle
Haskell
4129 Bytes1 + 11 Bytes, die durch @ Laikonis Bemerkungen gespeichert wurden.
1
,f
Und!!
sind separate Token. Die erste Zeile definiert die Fibonacci-Sequenz, die zweite ist eine Funktion, die die Sequenz der Fibonacci-Orials berechnet und das n-te für ein gegebenes n zurückgibt. Es wird fast sofort mit dem Drucken von Ziffern begonnen, auch bei n = 1000.quelle
(scanl(*)1f!!)
.f=1:scanl(+)1f
42+
als eine Funktion akzeptieren , die 42 hinzufügt? Das solltest du nicht, denn es ist nur ein unvollendeter Ausdruck. Aber in Haskell können wir Klammern hinzufügen und den Abschnitt erhalten(42+)
, eine Möglichkeit, die Funktion zu schreiben\n->42+n
. Hier ist es dasselbe, nur mit!!
(dem binären Infix-Operator für die Indizierung)+
und einem komplizierteren ersten Operanden.Python 2, 39 Bytes
Teste es auf Ideone .
quelle
True
in einigen Fällen zurückgegeben wird.True
für den Eingang 0 zurückkehren , was nicht positiv ist.J,
1716 Bytes1 Byte ist meilenweit mit einer noch besseren Lösung golfen.
Die Idee ist die gleiche wie im Original, aber anstatt die Matrix für kleine Diagonalen zu bilden, bilden wir die Diagonalen im laufenden Betrieb.
Original
So erhalten Sie die ersten n Fibonomials:
Lesen von rechts nach links ...
Erstellen Sie das Array von aufeinanderfolgenden ganzen Zahlen (
i.
) bis zu einer bestimmten Zahl. Erstellen Sie aus diesem Array die Tabelle (/~
) der Binomialkoeffizienten (!
), die aus jedem Paar im Array berechnet wird das ende der ersten reihe und alle elemente unter der hauptdiagonale sind 0, danke für die umsetzung von!
. Wenn Sie+/
alle kleinen Diagonalen (/.
) summieren , erhalten Sie Fibonacci-Zahlen, aber Sie müssen{.
so viele erste Elemente aus dem resultierenden Array nehmen wie die Länge (#
) der Tabelle selbst. Dann ergibt das Produkt (*/
), das auf aufeinanderfolgende Präfixe (\
) des Arrays angewendet wird, die gewünschte Folge von Fibonorials.Wenn Sie möchten, können Sie nur das letzte mit 2 weiteren Bytes ({:
) nehmen, aber ich dachte, dass das Anzeigen aller Bytes keine Sünde ist:)
.NB. the previous code block is not a J function
.Für große Zahlen in J verwenden Sie
x
am Ende:Das Programm läuft mit durchschnittlich 0,11s .
quelle
[:*/+/@(!|.)\@i.
verwendet 16 Bytes. Es bildet dieselben Binomialkoeffizienten entlang der von Ihnen generierten Tabelle, mit der!/~
Ausnahme, dass es diese bildet, indem Präfixe von verwendet werdeni.
.Pyth, 13 Bytes
Demonstration
Dies setzt einen cleveren, nicht typsicheren Trick ein. Fünf der Zeichen (
u*G ... Q1
) geben an, dass die Ausgabe das Produkt der Eingabe vieler Zahlen ist. Der Rest des Codes generiert die Zahlen.=[sZhZ)
Aktualisiert die VariableZ
in der Liste[s(Z), h(Z)]
. Danns
summiert diese Liste, um multipliziert zu werden.Z
ist anfangs 0.s
ints ist die Identitätsfunktion.h
ist die+ 1
Funktion. Also auf der ersten IterationZ
wird[0, 1]
.s
auf Listen ist die Summenfunktion, wie oben erwähnt.h
ist die Kopffunktion. Die zweite Iteration ist also[1, 0]
.Hier ist eine Liste:
Diese Summen werden multipliziert, um das Ergebnis zu erhalten.
quelle
Mathematica
2524 BytesMit Dank an Martin Ender.
Timing: 63 Mikrosekunden.
quelle
1##&@@Fibonacci~Array~#&
Gelee, 8 Bytes
Meine erste Einreichung in Jelly. Es ist nicht so kurz wie die Antwort von @Dennis , aber mit einer anderen Methode nur 2 Byte länger.
Vor Ort sind etwa 400 ms erforderlich, verglichen mit 380 ms bei der @ Tennis-Version für n = 100.
Probieren Sie es online!
Erläuterung
quelle
PARI / GP, 29 Bytes
Oder alternativ:
quelle
R
9996787666 BytesDiese Antwort verwendet die Binet-Formel sowie die
prod(x)
Funktion. Da R keinen eingebautenPhi
Wert hat, habe ich es selbst definiert:Es funktioniert unter 5 Sekunden, aber R neigt dazu zu geben
Inf
als Antwort auf diese großen Zahlen zu geben ...Ungolfed:
-2 Bytes dank @Cyoce!
Oh, liebe ich diese Seite? -10 Bytes dank @ user5957401
quelle
sqrt(5)
N
einmal verwenden, können Sie nur Scan innerhalb des1:N
Bits aufrufen . dhfor(n in 1:scan())
. Sie können auch einige Zeichen speichern, indem Sie*
anstelle derprod()
Funktion in Ihrer for-Schleife verwenden. Ihre for-Schleife besteht nur aus einer Zeile, daher benötigen Sie auch keine geschweiften Klammern.function(n,N=1:n,p=5^.5)prod(((1+p)^N-(1-p)^N)/2^N/p)
R,
82,53, 49 Bytes (48 Bytes mit unterschiedlichem Eingabestil)Wenn wir dem Code nur die eingegebene Nummer voranstellen können, erhalten wir die 48 Byte
EDIT: Neuer Code. Original ist unten:
Gibt nichts anderes als Inf für zurück
a(100)
. Und es funktioniert nur für nicht negative ganze Zahlen.Ungolfed:
quelle
Java, 165 Bytes
Golf gespielt:
Dies ist ein weiterer Fall, bei
BigInteger
dem aufgrund der großen Anzahl Bedarf besteht. Es gelang mir jedoch, den TextBigInteger
auf ein Minimum zu beschränken und die Größe gering zu halten. Ich habe es auch mit statischen Importen verglichen und es hat die Gesamtlänge verlängert.Dieses Programm verfolgt drei Zahlen in einem Array. Die ersten beiden sind die vorherigen beiden Fibonacci-Zahlen. Der dritte ist der akkumulierte Wert. Die Schleife beginnt damit, dass der nächste Wert berechnet und in abwechselnden (0, 1, 0, 1, ...) Array-Indizes gespeichert wird. Dies vermeidet, dass Werte mit kostspieligen (in Bezug auf die Quellgröße) Zuweisungsoperationen verschoben werden müssen. Nehmen Sie dann diesen neuen Wert und multiplizieren Sie ihn mit dem Akku.
Durch die Vermeidung temporärer Objekte und die Beschränkung der Schleife auf zwei Zuweisungsoperatoren konnte ich einige Bytes herauspressen.
Ungolfed:
Programmausgabe:
quelle
Brachylog , 31 Bytes
Probieren Sie es online!
quelle
Ruby, 39 Bytes
quelle
Javascript (ES6),
5139 BytesRekursive Implementierung (39 Bytes)
Ursprüngliche Implementierung (51 Byte)
Hinweis: Startet Rundungsfehler für das Fibonacci-Orial von 16, 100 ist nur Unendlich, läuft in scheinbar <1 Sekunde.
quelle
n=>[...Array(n)].reduce(p=>(c=a,a=b,p*=b+=c),a=1,b=0)
nur um festzustellen, dass Sie die gezählt haben,f=
die Sie nicht benötigen, um 2 Byte zu sparen.DC (GNU- oder OpenBSD-Variante) , 36 Bytes
Datei
A003266-v2.dc
:(kein abschließender Zeilenumbruch)
... jetzt wird das Ergebnis auf dem Stack gehalten, anstatt ein benanntes Register zu verwenden (ist
Y
in Version 1). Derr
Befehl ist im Original nicht verfügbardc
(siehe RosettaCodes Dc-Seite ).Lauf:
Ich versuche zu erklären:
tos
ist der Inhalt der Oberseite des Stapels, ohne ihn zu entfernen.nos
ist das Element untentos
.DC , 41 Bytes
... geradeaus, keine Tricks:
Datei
A003266-v1.dc
:(kein abschließender Zeilenumbruch)
Lauf:
quelle
dc
Code zu schreiben ist definitiv einfacher als es zu erklären ...n
Elemente möglicherweise sofort auf einen anderen Stapel verschieben. Derzeit weiß ich jedoch noch nicht, wie ichdc
aus dem Quellcode kompilieren soll . : /C #
11010910710310194 BytesErläuterung
Iterativer Fib-Algorithmus
quelle
Brain-Flak , 54 Bytes
Probieren Sie es online!
Die Multiplikation in Brain-Flak benötigt für große Eingaben viel Zeit. Allein die Multiplikation von F 100 mit F 99 mit einem generischen Multiplikationsalgorithmus würde Milliarden von Jahren dauern.
Zum Glück gibt es einen schnelleren Weg. Eine verallgemeinerte Fibonacci-Sequenz, die mit beginnt
(k, 0)
, erzeugt dieselben Terme wie die übliche Sequenz, multipliziert mitk
. Mit dieser Beobachtung kann Brain-Flak genauso einfach mit einer Fibonacci-Zahl multiplizieren, wie es Fibonacci-Zahlen erzeugen kann.Wenn der Stapel aus
-n
zwei{({}()<([({})]({}{}))>)}{}{}
aufeinanderfolgenden Zahlen besteht, werdenn
Iterationen der verallgemeinerten Fibonacci-Sequenz berechnet und alle bis zum letzten verworfen. Der Rest des Programms richtet nur die anfängliche 1 ein und durchläuft diese für alle Zahlen im Bereichn...1
.Hier ist der gleiche Algorithmus in den anderen Sprachen, die von diesem Interpreter bereitgestellt werden:
Brain-Flak Classic, 52 Bytes
Probieren Sie es online!
Brain-Flueue, 58 Bytes
Probieren Sie es online!
Mini-Flak, 62 Bytes
Probieren Sie es online!
quelle
Mathematica -
3226 Bytes@MartinEnder 6 Bytes gehackt!
quelle
SPALT 28 Bytes
Fibonacci
Wusste bis heute nicht, dass GAP eine eingebaute hat.quelle
Rubin, 85 Bytes
Hat sich als gut herausgestellt, aber es gibt wahrscheinlich eine kürzere Lösung.
Schnelle Fibonnaci-Berechnung von hier: Link
Teste es hier
quelle
Julia, 36 Bytes
quelle
Brain-Flak ,
110104100 BytesProbieren Sie es online!
Erläuterung
Zuerst führen wir eine verbesserte Version des Fibonacci-Sequenzgenerators von Dr. Green Eggs und Iron Man aus
Dann, während der Stapel mehr als einen Gegenstand hat
Multipliziere die beiden obersten Punkte
und die zusätzliche Null platzen lassen
quelle
Clojure, 70 Bytes
Clojure ist keine gute Sprache für Code-Golf. Naja.
Probieren Sie es unter http://tryclj.com .
quelle
Viertens 55 Bytes
Verwendet einen iterativen Ansatz, der auf meiner Fibonacci-Antwort in Forth aufbaut. Die Ergebnisse laufen arithmetisch für über
n > 10
. Die Antwort ist unabhängig von Groß- und Kleinschreibung.Probieren Sie es online aus
quelle
Schnell, 68 Bytes
quelle
JavaScript (ES6), 46 Byte
Verwendet Rekursions- und Akkumulatorvariablen. Rundungsfehler beginnen bei
f(16)
.quelle