Définition
La séquence de Fibonacci F(n)
, sur les entiers positifs, est définie comme telle:
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
Le Fibonacci-orial d'un entier positif est le produit de [F(1), F(2), ..., F(n)]
.
Tâche
Étant donné entier positif n
, trouver le Fibonacci-orial de n
.
Spécifications
Le fibronome de 100
doit calculer en moins de 5 secondes sur un ordinateur raisonnable.
Testcases
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
Réponses:
Mathematica, 10 octets
Un autre logiciel intégré Mathematica bien battu par une langue de golf sans le logiciel intégré.
la source
Gelée , 6 octets
L'entrée 100 se termine en 500 ms localement. Essayez-le en ligne!
Comment ça marche
la source
+¡1
un nth fibonacci non construit et+С1
est le n premiers nombres de Fibonacci?En fait , 4 octets
Exécute l’entrée 100 en 0,2 seconde. Code:
Explication:
Utilise le codage CP-437 . Essayez-le en ligne! .
la source
Brainfuck,
11981067817770741657611603Non compressé, avec des commentaires:
Essayez-le en ligne!
Le temps d’exécution pour n = 100 est inférieur à 1 seconde avec l’interprète en ligne (environ 0,2 seconde localement utilisant mon propre interprète). L'entrée maximale est de 255, mais l'interprète doit prendre en charge environ 54 000 cellules (l'interpréteur en ligne semble envelopper sur 64 Ko).
Changer le journal
Sauvegardé environ 130 octets avec une meilleure extraction du chiffre actuel à multiplier par, et en fusionnant ajouter et reporter en un seul passage. Cela semble aussi être un peu plus rapide.
Enregistré un autre 250 octets. J'ai réussi à réduire mon bloc-notes de multiplication de deux cellules, ce qui permet d'économiser des octets un peu partout, car je n'ai pas à changer autant de chiffres. J'ai également abandonné le report après l'avoir multiplié par un chiffre et effectuer un report complet tout en ajoutant au total cumulé.
Haché encore 50, encore une fois avec une meilleure extraction du chiffre actuel à multiplier, simplement en ne le déplaçant pas de la première itération et en partant de là où il se trouve. Quelques micro-optimisations plus bas représentent environ 10 octets.
30 autres sont partis. Marquer les chiffres déjà pris avec un 0 plutôt qu'un 1 facilite leur localisation. Cela permet également de vérifier si la boucle de multiplication est un peu plus simple.
J'ai réduit le bloc-notes d'une autre cellule, pour 80 octets supplémentaires. Pour ce faire, j'ai fusionné le marqueur du produit précédent et le total cumulé en cours, ce qui réduit les décalages entre les espaces et facilite la comptabilité.
Sauvegardé 50 autres, en éliminant une autre cellule, en réutilisant le marqueur pour les chiffres de fibonacci pour marquer également le dernier chiffre pris. J'ai également pu fusionner la boucle pour décaler les totaux précédents avec la boucle de multiplication en chiffres.
Sauvegardé 8 octets lors de l'analyse de l'entrée. Oops.
la source
Python, 45 octets
L'entrée est prise de stdin. La sortie pour n = 100 se termine trop rapidement pour que le temps soit précis. n = 1000 prend environ 1s.
Exemple d'utilisation
la source
Haskell
4129 octets1 + 11 octets enregistrés par les remarques de @ Laikoni.
1
,f
Et!!
sont des jetons séparés. Les premières lignes définissent la séquence de fibonacci, la seconde est une fonction qui calcule la séquence de fibonacci-orials et renvoie le n-ème pour un n donné. Il commence à imprimer les chiffres presque immédiatement, même pour n = 1000.la source
(scanl(*)1f!!)
.f=1:scanl(+)1f
42+
une fonction qui ajoute 42? Vous ne devriez pas, parce que c'est juste une expression inachevée. Mais en Haskell, nous pouvons ajouter des parenthèses et obtenir la section(42+)
, un moyen d’écrire la fonction\n->42+n
. Ici, c'est la même chose, seulement avec!!
(l'opérateur infixe binaire pour l'indexation) au lieu d'+
un premier opérande plus compliqué.Python 2, 39 octets
Testez-le sur Ideone .
la source
True
dans certains cas.True
pour l'entrée 0 , ce qui n'est pas positif.J,
1716 octets1 octet est joué au golf avec une solution encore meilleure par miles.
L'idée est la même que l'originale mais au lieu de former la matrice pour opérer sur des diagonales mineures, nous formons les diagonales à la volée.
Original
Pour obtenir les premiers n fibonomiaux:
Lecture de droite à gauche ...
Créez le tableau d’entiers consécutifs (
i.
) jusqu’à celui spécifié, à partir de ce tableau, créez le tableau (/~
) de coefficients binomiaux (!
) calculé à partir de chaque paire du tableau, ce tableau est le triangle situé en haut de Pascal la fin de la première ligne et tous les éléments sous la diagonale principale sont 0, heureusement pour la mise en œuvre de!
. Si vous additionnez (+/
) toutes les diagonales mineures (/.
), vous obtenez des nombres de Fibonacci, mais vous devez prendre ({.
) autant de premiers éléments du tableau résultant que la longueur (#
) de la table elle-même. Ensuite, le produit (*/
) appliqué à des préfixes consécutifs (\
) du tableau aboutit à la séquence souhaitée de fibonoriales.Si vous le souhaitez, vous ne pouvez prendre que le dernier en utilisant 2 octets supplémentaires ({:
), mais j’ai pensé que les afficher tous n’était pas un péché:)
.NB. the previous code block is not a J function
.Pour les grands nombres en J que vous utilisez
x
à la fin:Le programme fonctionne à 0,11 s en moyenne .
la source
[:*/+/@(!|.)\@i.
utilise 16 octets. Il forme les mêmes coefficients binomiaux le long de la table que vous générez en utilisant!/~
sauf qu'il le fait en prenant les préfixes dei.
.Pyth, 13 octets
Manifestation
Cela fait appel à une astuce intelligente, sans typographie. Cinq des caractères (
u*G ... Q1
) indiquent que la sortie est le produit de nombreux nombres saisis. Le reste du code génère les nombres.=[sZhZ)
met à jour la variableZ
dans la liste[s(Z), h(Z)]
. Puiss
somme cette liste, à multiplier.Z
est initialement 0.s
, sur ints, est la fonction identité.h
, sur son, est la+ 1
fonction. Ainsi, à la première itération,Z
devient[0, 1]
.s
sur les listes est la fonction somme, comme mentionné ci-dessus.h
est la fonction principale. Donc, la deuxième itération est[1, 0]
.Voici une liste:
Ces sommes sont multipliées pour donner le résultat.
la source
Mathematica
2524 bytesWith thanks to Martin Ender.
Timing: 63 microseconds.
la source
1##&@@Fibonacci~Array~#&
Jelly, 8 bytes
My first submission in Jelly. It's not as short as @Dennis' answer, but its only 2 bytes longer with a different method.
Locally, it requires about 400ms compared to 380ms with @Dennis' version for n = 100.
Try it online!
Explanation
la source
PARI/GP, 29 bytes
Or alternatively:
la source
R,
9996787666 bytesThis answer is uses Binet's Formula, as well as the
prod(x)
function. Since R doesn't have a build-inPhi
value, I defined it myself :It works under 5 seconds, but R tends to give
Inf
as an answer for those big numbers...Ungolfed :
-2 bytes thanks to @Cyoce !
Oh, do I love this site ! -10 bytes thanks to @user5957401
la source
sqrt(5)
to a variableN
once, you can just call scan inside the1:N
bit. i.e.for(n in 1:scan())
. You can also save a few characters by just using*
instead of theprod()
function in your for loop. Your for loop is only one line, so you don't need the curly braces either.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 w/ different input style)If we can just precede the code with the input number, we get the 48 byte
EDIT: New code. Original is below:
Won't return anything other than Inf for
a(100)
though. And it won't work for anything but non-negative integers.Ungolfed:
la source
Java, 165 bytes
Golfed:
This is yet another case where
BigInteger
being required due to large numbers. However, I was able to keep the textBigInteger
to a minimum, keeping the size down. I also compared with static imports, and it made the total length longer.This program works by tracking three numbers in an array. The first two are the previous two Fibonacci numbers. The third is the accumulated value. The loop starts out by calculating the next value and storing it in alternating (0, 1, 0, 1, ...) array indices. This avoids needing to shift values with costly (in terms of source size) assignment operations. Then grab that new value and multiply it into the accumulator.
By avoiding temporary objects and limiting the loop to two assignment operators, I was able to squeeze out quite a few bytes.
Ungolfed:
Program output:
la source
Brachylog, 31 bytes
Try it online!
la source
Ruby, 39 bytes
la source
Javascript (ES6),
5139 bytesRecursive implementation (39 bytes)
Original implementation (51 bytes)
Note: Starts rounding errors for the Fibonacci-orial of 16, 100 is just Infinity, runs in what appears to be <1 second.
la source
n=>[...Array(n)].reduce(p=>(c=a,a=b,p*=b+=c),a=1,b=0)
only to discover that you'd counted thef=
which isn't required saving you 2 bytes.DC (GNU or OpenBSD flavour), 36 bytes
File
A003266-v2.dc
:(no trailing newline)
...now the result is held on the stack instead of using a named register (is
Y
in version 1). Ther
command is not available in the originaldc
(see RosettaCode's Dc page).Run:
Trying to explain:
tos
is the contents of the top of the stack without removing it.nos
is the element belowtos
.DC, 41 bytes
...straight forward, no tricks:
File
A003266-v1.dc
:(no trailing newline)
Run:
la source
dc
code definitely is easier than explaining it...n
items to another stack at once. For now, though, I still don't know how to compiledc
from source. :/C#
11010910710310194 BytesExplanation
Iterative Fib algorithm
la source
Brain-Flak, 54 bytes
Try it online!
Multiplication in Brain-Flak takes a long time for large inputs. Just multiplying F100 by F99 with a generic multiplication algorithm would take billions of years.
Fortunately, there's a faster way. A generalized Fibonacci sequence starting with
(k, 0)
will generate the same terms as the usual sequence, multiplied byk
. Using this observation, Brain-Flak can multiply by a Fibonacci number just as easily as it can generate Fibonacci numbers.If the stack consists of
-n
followed by two numbers,{({}()<([({})]({}{}))>)}{}{}
will computen
iterations of the generalized Fibonacci sequence and discard all by the last. The rest of the program just sets up the initial 1 and loops through this for all numbers in the rangen...1
.Here's the same algorithm in the other languages provided by this interpreter:
Brain-Flak Classic, 52 bytes
Try it online!
Brain-Flueue, 58 bytes
Try it online!
Mini-Flak, 62 bytes
Try it online!
la source
Mathematica -
3226 bytes@MartinEnder chopped 6 bytes!
la source
GAP 28 Bytes
Didn't know before today that GAP has a
Fibonacci
builtin.la source
Ruby, 85 Bytes
Turned out fine, but there's probably a shorter solution.
Fast Fibonnaci calculation taken from here: link
Test it here
la source
Julia, 36 bytes
la source
Brain-Flak,
110104100 bytesTry it online!
Explanation
First we run an improved version of the Fibonacci sequence generator curtesy of Dr Green Eggs and Iron Man
Then while the stack has more than one item on it
multiply the top two items
and pop the extra zero
la source
Clojure, 70 bytes
Clojure isn't really a good language for code golf. Oh well.
Try it at http://tryclj.com.
la source
Forth, 55 bytes
Uses an iterative approach, built upon my Fibonacci answer in Forth. The results overflow arithmetically for
n > 10
. The answer is case-insensitive.Try it online
la source
Swift, 68 Bytes
la source
JavaScript (ES6), 46 bytes
Uses recursion and accumulator variables. Rounding errors start at
f(16)
.la source