Vous pouvez décomposer un nombre supérieur à 0 comme une somme unique de nombres de Fibonacci positifs. Dans cette question, nous le faisons en soustrayant à plusieurs reprises le plus grand nombre de Fibonacci positif possible . Par exemple:

1 = 1
2 = 2
3 = 3
4 = 3 + 1
12 = 8 + 3 + 1
13 = 13
100 = 89 + 8 + 3

Maintenant, j'appelle un produit Fibonacci les mêmes listes que ci-dessus, mais avec l'addition remplacée par la multiplication. Par exemple f(100) = 89 * 8 * 3 = 2136,.

Écrivez un programme ou une fonction qui a donné un entier positif n renvoie le produit de Fibonacci de ce nombre.

Testcases:

1: 1
2: 2
3: 3
4: 3
5: 5
6: 5
7: 10
8: 8
9: 8
42: 272
1000: 12831
12345: 138481852236

Gelée , 16 15 octets

Rf1+С¤ṪạµÐĿIAP

Pas particulièrement rapide ou convivial, mais suffisamment efficace pour tous les cas de test. Essayez-le en ligne!

Comment ça fonctionne

Rf1+С¤ṪạµÐĿIAP  Main link. Argument: n (integer)

         µ       Combine the chain to the left into a link.
          ÐĿ     Apply that link until the results are no longer unique.
                 Return the list of unique results.
      ¤            Combine the two links to the left into a niladic chain.
  1                  Set the left (and right) argument to 1.
   +D¡               Apply + to the left and right argument, updating the left
                     argument with the sum, and the right argument with the
                     previous value of the left one. Return the list of results.
                     Repeat this process n times.
                   This yields n + 1 Fibonacci numbers, starting with 1, 2.
R                  Range; map k to [1, ..., k].
 f                 Filter; keep the items in the range that are Fibonacci numbers.
       Ṫ           Tail; yield the last one or 0 if the list is empty.
        ạ          Absolute difference with k.
                   This is the argument of the next iteration.
            I    Compute the increments of the arguments to the loop, yielding
                 the selected Fibonacci numbers (with changed sign).
             A   Apply absolute value to each.
              P  Compute their product.  

Python, 54 octets

f=lambda n,a=1,b=1:n<1or b>n and a*f(n-a)or f(n,b,a+b)

Juste une bonne vieille récursivité.

Perl, 69 63 + 4 ( -pl61indicateur) = 67 octets

#!perl -pl61
while($_){$n=$m=1;($n,$m)=($m,$n+$m)until$m>$_;$_-=$n;$\*=$n}}{

En utilisant:

> echo 42 | perl -pl61e 'while($_){$n=$m=1;($n,$m)=($m,$n+$m)until$m>$_;$_-=$n;$\*=$n}}{'

Non golfé:

while (<>) {
# code above added by -p
    # $_ has input value
    # $\ = 1 by -l61
    while ($_ != 0) {
        my $n = 1;
        my $m = 1;
        while ($m <= $_) {
            ($n, $m) = ($m, $n + $m);
        }
        $_ -= $n;
        $\ *= $n;
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}

Ideone .

JavaScript (ES6), 78 42 octets

f=(n,a=1,b=1)=>n?b>n?a*f(n-a):f(n,b,a+b):1

Port de la réponse de @ Sp3000. Version originale de 78 octets:

f=(n,a=[2,1])=>n>a[0]?f(n,[a[0]+a[1],...a]):a.map(e=>e>n?0:(r*=e,n-=e),r=1)&&r

> <> , 57 octets

111\ ;n{/
:@+>:{:})?\$:@@
~{*}:0=?\}>:0${:})?$~:{$-$:1@?$

Attend que le numéro d'entrée soit présent sur la pile au démarrage du programme.

Construit la séquence de Fibonacci ( f0, f1, f2, ..., fn) sur la pile jusqu'à ce qu'un nombre supérieur à l'entrée ( i) soit atteint . Ensuite, avec un produit ( p) initialisé à 1...

while (i != 0)
   if (fn <= i)
      i = i - fn
      p = p * fn
   else
      i = i - 0
      p = p * 1
   discard fn
output p

Essayez-le en ligne!

Pyth, 28 octets

K1WQJ0 .WgQH+Z~JZ1=*KJ=-QJ;K

Je pense qu'il peut être joué beaucoup plus loin ...

Essayez-le en ligne!

Pyth, 24 octets

W=-QeaYh.WgQeH,eZsZ1;*FY

Essayez-le en ligne: démonstration ou suite de tests

Explication:

Q est attribué avec le numéro d'entrée.

La partie h.WgQeH,eZsZ1calcule le plus grand nombre de Fibonacci, inférieur ou égal àQ

h.WgQeH,eZsZ1
            1   start with H=Z=1
 .WgQeH         while Q >= end(H):
       ,eZsZ       H=Z=(end(Z), sum(Z))
h               first

Donc, si Q = 10, il génère les nombres / paires:

1 -> (1,1) -> (1,2) -> (2,3) -> (3,5) -> (5,8) -> (8,13) -> 8

Le reste du code calcule la partition et multiplie les nombres ensemble:

W=-QeaY...;*FY    implicit: Y = empty list
     aY...        add the calculated Fibonacci number to the empty list
    e             take the last element of Y (yes the number we just added)
 =-Q              and update Q with the difference of Q and ^
W         ;       continue until Q == 0
           *FY    multiply all number in Y and print

Il y a évidemment beaucoup de solutions plus courtes (avec des temps d'exécution vraiment mauvais), comme *FhfqQsTyeM.u,eNsNQ1.

Haskell, 44 octets

Ouais pour la récursion mutuelle:

(a&b)c|c<1=1|b>c=a*f(c-a)|d<-a+b=b&d$c
f=0&1

• a est le numéro de Fibonacci précédent
• b est le nombre actuel de Fibonacci
• c est l'entrée
• f est la fonction souhaitée

Moins golfé:

(a & b) c | c == 0    = 1
          | c <  b    = a * f (c-a)
          | otherwise = b & (a + b) $ c
f x = (0 & 1) x

En fait, 22 octets

W;╗uR♂F;`╜≥`M░M;╜-WXkπ

Essayez-le en ligne!

Explication:

W;╗uR♂F;`╜≥`M░M;╜-WXkπ
                        (implicit input)
W                 W     while top of stack is truthy:
 ;╗                       push a copy of n to reg0
   uR♂F;                  push 2 copies of [Fib(a) for a in range(1, n+2)]
        `╜≥`M░            filter: take values where n <= Fib(a)
              M;          two copies of maximum (call it m)
                ╜-        subtract from n (this leaves n-m on top of the stack to be the new n next iteration, with a copy of m below it)
                   X    discard the 0 left over after the loop ends
                    kπ  product of all stack values

Javascript (ES6) 134 106 92 bytes

Merci pour @cat d'avoir repéré un espace.

n=>{for(c=[a=b=s=1,1];a+b<=n;)a+=b,c.unshift(b+=a,a);c.map(i=>i<=n&&(n-=i)&(s*=i));alert(s)}

Juste une version non optimisée faite sur mon téléphone, je la joue au golf, une fois à la maison. Les idées sont les bienvenues.

RETOUR , 44 octets

[a:[a;][1$[¤¤+$a;->~][]#%$␌a;\-a:]#␁[¤][×]#]

Try it here.

Lambda anonyme étonnamment inefficace qui laisse le résultat sur Stack2. Usage:

12345[a:[a;][1$[¤¤+$a;->~][]#%$␌a;\-a:]#␁[¤][×]#]!

REMARQUE: ␌ et ␁ sont des espaces réservés pour leurs caractères non imprimables respectifs: Form Feed et Start of Heading .

Explication

[                                           ]  lambda
 a:                                            store input to a
   [  ][                         ]#            while loop
    a;                                           check if a is truthy
        1$[¤¤+$a;->~][]#%                        if so, generate all fibonacci numbers less than a 
                         $␌                      push copy of TOS to stack2
                           a;\-a:                a-=TOS
                                   ␁[¤][×]#   get product of stack2

PHP, 119 octets

Le code (enroulé sur deux lignes pour plus de lisibilité):

for($o=$c=1;$c<=$n=$argv[1];$f[++$k]=$c,$a=$b,$b=$c,$c+=$a);
for($i=$k;$i;$i--)for(;$n>=$d=$f[$i];$n-=$d,$o*=$d);echo$o;

La première ligne calcule dans $fles nombres de Fibonacci inférieurs à $n(l'argument fourni dans la ligne de commande). La deuxième ligne calcule les facteurs de Fibonacci (par soustraction) et les multiplie pour calculer le produit en $o.

Ajoutez le code avec <?php(techniquement ne fait pas partie du programme), placez-le dans un fichier ( fibonacci-factors.php) puis exécutez-le en tant que:

$ php -d error_reporting=0 fibonacci-factors.php 100
# The output:
2136

Ou exécutez-le en utilisant php -d error_reporting=0 -r '... code here ...' 100.

Le code non golfé et la suite de tests peuvent être trouvés sur Github .

Q, 47 octets

m:{*/1_-':|(0<){y-x x bin y}[*+60(|+\)\1 0]\x}

Tester

+(i;m'i:1 2 3 4 5 6 7 8 9 42 1000 12345)

le lire sous forme de paires (i, map (m, i)), où m est la fonction de calcul et i les différents arguments

écrit

1     1
2     2
3     3
4     3
5     5
6     5
7     10
8     8
9     8
42    272
1000  12831
12345 138481852236

Explication

n funtion\arg applique la fonction (fonction (fonction (fonction (... fonction (args)))) n fois (utilise en interne la récursion tal) et renvoie la séquence de résultats. Nous calculons les 60 premiers éléments de la série fibonnaci comme *+60(|+\)\1 0. Dans ce cas, la fonction est ( | +): + \ appliqué sur une séquence calcule des sommes partielles (ex + \ 1 2 3 est 1 3 6), et | inverse la suite. Ainsi, à chaque 'itération', nous calculons des sommes partielles des deux nombres de fibonacci précédents et retournons la partie les sommes inversées 60(|+\)\1 0génèrent des séquences 1 0, 1 1, 2 1, 3 2, 5 3, 8 5, 13 8, 21 13, ...*+ appliquées sur ce résultat retournez-les (transposez) et prenez la première. Le résultat est la séquence 1 1 2 3 5 8 13 21 34 55 ..

(cond)function\args applique la fonction (fonction (.. fonction (args))) tandis que cond true, et renvoie la séquence de résultats partiels

function[arg] appliqué sur une fonction de plusieurs arguments crée une projection (application partielle)

Nous pouvons donner un nom aux arguments, mais les noms implicites sont x, y, z

{y-x x bin y}[*+60(|+\)\1 0]déclare un lambda avec args x, y avec projection partielle (arg x est une série de fibonacci, calcule comme * + 60 (| +) \ 1 0). x représente les valeurs de fibonacci, et y le nombre à traiter. La recherche binaire (bin) est utilisée pour localiser l'indice du plus grand nombre de fibonacci <= y ( x bin y), et soustraire la valeur correspondante de x.

Pour calculer le produit à partir de résuls partiels, nous les inversons et calculons la différence de chaque paire ( -':|), supprimons la première ( 1_car est 0) et multiplions sur ( */).

Si nous sommes intéressés par la somme accumulée, le code est le même, mais avec +/au lieu de */. Nous pouvons également utiliser n'importe quel autre opérateur diadique au lieu de + ou *

À propos de l'efficacité d'exécution

Je sais que dans ce concours, l'efficacité n'est pas un problème. Mais dans ce problème, nous pouvons aller du coût linéaire au coût exponentiel, donc je suis curieux de le savoir.

J'ai développé une deuxième version (longueur 48 octets hors commentaire) et répété des tests de batterie 1000 fois sur les deux versions.

f:*+60(|+\)\1 0;m:{*/1_-':|(0<){x-f f bin x}\x}    /new version

le temps d'exécution est: version originale 0'212 seg, nouvelle version 0'037 seg

La version originale calcule la série fibbonaci une fois par application de fonction; nouvelle version calcule fibonacci un seul.

Dans les deux cas, le calcul des séries de fibonacci utilise la récursivité de la queue