Hintergrund
Die Fibonacci-Sequenz ist definiert als
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)
Das Fibonorial ist ähnlich wie die Fakultät das Produkt der ersten n Fibonacci-Zahlen.
g(n) = f(1) * f(2) * ... * f(n-1) * f(n)
Der Fibonomialkoeffizient, ähnlich dem Binomialkoeffizienten, ist definiert als
a(n, 0) = 1
a(n, k) = g(n) / ( g(n-k) * g(k) )
= f(n) * f(n-1) * ... * f(n-k+1) / ( f(1) * f(2) * ... * f(k) )
Aufgabe
Ihr Ziel ist es, eine Funktion oder ein Programm zur Berechnung des Fibonomialkoeffizienten bei zwei nicht negativen ganzen Zahlen n und k mit k ≤ n zu erstellen .
Testfälle
a(0, 0) = 1
a(1, 1) = 1
a(2, 0) = 1
a(3, 2) = 2
a(8, 3) = 1092
a(11, 5) = 1514513
a(22, 7) = 7158243695757340957617
a(25, 3) = 49845401197200
a(50, 2) = 97905340104793732225
a(100, 1) = 354224848179261915075
Regeln
- Dies ist Code-Golf, also gewinnt der kürzeste Code.
- Builtins sind erlaubt.
verbunden
- A000045 - Herausforderung - Fibonacci-Sequenz
- A003266 - Herausforderung - Fibonorial
- A010048 - Fibonomialkoeffizient
code-golf
fibonacci
approximation
Meilen
quelle
quelle
1335
Werte in der Sequenz Fibonomial Coefficient aufgeführt sind.a(50, 2)
Testfall eine Führung9
?Antworten:
Gelee , 16 Bytes
Probieren Sie es online aus!
Dank an Dennis für den Fibonacci-Orial-Helfer-Link.
quelle
Haskell, 46 Bytes
Ausgänge schweben. Erzeugt die unendliche Fibonacci-Liste. Dann erfolgt die Binomialrekusion, Multiplikation und Division durch Elemente aus der Fibonacci-Liste.
quelle
Python 67 Bytes
Rufen Sie mit an
a(n,k)
. Verwendet die fibonorische Antwort von @Dennis (ist das erlaubt?) Und ansonsten eine einfache Implementierung der Frage.quelle
lambda n,k:f(n)/f(k)/f(n-k)
; eine Benennung ist nicht erforderlich.Haskell,
77 57 55 5250 BytesDie erste Zeile stammt ursprünglich aus der Fibonacci-Funktions- oder Sequenz- Challenge und wurde von @Anon geschrieben.
Die zweite Zeile wurde in der Fibonacci-orial Challenge von @ChristianSievers hinzugefügt.
Jetzt habe ich die dritte Zeile hinzugefügt. Wie weit werden diese Herausforderungen noch gehen? =)
Danke für 5 Bytes @xnor!
quelle
/
lieber alsdiv
?C, 206 Bytes:
Fordert bei der Ausführung 2 durch Leerzeichen getrennte Ganzzahlen als Eingabe an. Der
#include
Präprozessor ist erforderlich , da er ohne ihnuint_64
kein gültiger Typ ist. Die einzige andere Möglichkeit, diese Funktion für relativ große Ausgaben zu verwenden, besteht darin,unsigned long long
Rückgabetypen sowohl für die FunktionenF
(Fibonacci) als auch für dieG
Funktionen (Fibonorial) zu verwenden, was viel länger als nur ist einschließlich der<inttypes.h>
und unter Verwendung von 3uint64_t
Typdeklarationen. Aber auch bei , daß, stoppt sie korrekt an Eingabewerten arbeitet14 1
(bestätigt durch Verwendung von dieser , die Listen , die die ersten1325
Werte in der Fibonomial Koeffizientenfolge), wahrscheinlich weil die Fibonacci und / oder Fibnorial Darstellung von Zahlen15
und vor Überlauf der 64-Bit - ganzzahliger Typ verwendet.C Es online! (Ideone)
quelle
uint_64
Cheddar ,
7564 BytesVerwendung
quelle
MATL ,
2523 BytesProbieren Sie es online aus!
Erläuterung
quelle
R, 120 Bytes
Etwas mehr Golf ist wahrscheinlich möglich, daher sind Kommentare natürlich willkommen!
Ich habe meine Antwort auf die Fibonacci- Frage am Anfang des Codes verwendet:
Ungolfed:
quelle
Java:
304260257Ich habe einige Bytes gespart, indem ich die Memoisierungsfunktion ein wenig komprimiert und
f(n)
vollständig entfernt und durch direkten Array-Zugriff ersetzt habe.Leider
BigInteger
ist wegen Überläufen erforderlich und ich musste Memoization hinzufügen. Selbst bei einer Generation 6 i7 dauerte es viel zu lange, um mit großen Eingaben zu arbeiten.Ungolfed, mit Boilerplate
class
undmain
Code:Programmausgabe:
quelle
JavaScript (ES6), 70 Byte
Rufen Sie mit
c(n)(k)
, ziemlich einfach.quelle
Ruby, 72 Bytes
Besonderer Dank geht an @ st0le für den wirklich kurzen Fibonacci-Generierungscode .
quelle
Gleichstrom, 67 Bytes
Die Eingabe erfolgt als durch Leerzeichen getrennte Dezimalkonstanten in einer einzelnen Zeile.
Dies verwendet meine Antwort auf die
/Fibon(acci-)?orial/
Frage, bei der im letzten Schritt alle Zahlen auf dem Stapel multipliziert werden und die anderen Zahlen an anderer Stelle gespeichert werden müssen, während die anderen Fibonorials berechnet werden.quelle
Julia, 53 Bytes
Dank an @Lynn für seine Fibonorial-Antwort .
quelle
Axiom 108 Bytes
ein Test
Typ: Tuple Fraction Integer
quelle
Mathematica, 30 Bytes
quelle