9

Définissons la séquence de Fibonacci comme

F(1) = 1

F(2) = 2

F(n) = F(n - 2) + F(n - 1)

Nous avons donc la séquence infinie 1,2,3,5,8,13,... Il est bien connu que tout entier positif peut être écrit comme une somme de quelques nombres de Fibonacci. La seule mise en garde est que cette sommation n'est peut-être pas unique. Il existe toujours au moins une façon d'écrire un nombre sous la forme d'une somme de nombres de Fibonacci, mais il peut y en avoir beaucoup plus.

Votre défi est d'écrire un programme complet qui, à l'aide de stdin, prend un entier positif compris entre un et un million inclus, puis génère à l'aide de stdout toutes les sommations possibles des nombres de Fibonacci qui résument à l'entrée. En résumé, les nombres de Fibonacci ne doivent pas se répéter et cela inclut le nombre 1. Dans toute sommation, s'il 1est présent, il ne doit être présent qu'une seule fois car dans ma définition de la séquence ci-dessus 1n'apparaît qu'une seule fois. Les sommations avec un seul terme sont valides donc si le numéro d'entrée est un nombre de Fibonacci lui-même, alors le nombre lui-même est une sommation valide et doit être imprimé. Si plusieurs sommes, alors entre deux sommes, il doit y avoir une ligne vierge pour les distinguer facilement.

Voici quelques exemples.

./myfib 1
1

Il n'y a qu'une seule telle somme et elle n'a qu'un terme, c'est tout ce qui est imprimé.

./myfib 2
2

Notez ici que ce 1+1n'est pas une somme valide car elle se 1répète.

./myfib 3
1+2

3

Deux sommes et elles sont toutes les deux imprimées avec une ligne vierge entre les deux.

./myfib 10
2+8

2+3+5

./myfib 100
3+8+89

1+2+8+89

3+8+34+55

1+2+3+5+89

1+2+8+34+55

3+8+13+21+55

1+2+3+5+34+55

1+2+8+13+21+55

1+2+3+5+13+21+55

Véritable golf de code. Le code le plus court dans n'importe quelle langue gagne. Veuillez poster votre code avec quelques cas de test (en plus de celui que j'ai donné ci-dessus). En cas d'égalité, je choisis celui qui a le plus de votes positifs après avoir attendu au moins deux semaines et probablement plus. Alors, la communauté, n'hésitez pas à voter pour toutes les solutions que vous aimez. L'intelligence / la beauté du code importe beaucoup plus que celui qui publie en premier.

Bon codage!

code-golf fibonacci Un point fixe
la source

1

... Je vais juste forcer ceci: P Si je poste une réponse, ne vous attendez pas à ce qu'elle fonctionne bien :)

Poignée de porte

Eh bien, c'est le code-golf et non le code le plus rapide. :-D

Fixed Point

1

Je l'ai écrit, et ça tourne vite: P

Poignée de porte

Pas tout à fait un doublon, mais étroitement lié à codegolf.stackexchange.com/q/2677/194

Peter Taylor

1

@shiona Puisque je n'ai pas précisé, choisissez votre préféré. :-)

Fixed Point

9

GolfScript, 54 caractères

~1.{3$)<}{.@+}/<[[]]{{+}+1$%+}@/\{~)+{+}*!}+,{'+'*n.}/

Testez-le en ligne ou regardez les exemples:

> 54
2+5+13+34

> 55
1+2+5+13+34

3+5+13+34

8+13+34

21+34

55

Howard
la source

4

Ruby, 118 114 (sortie de réseau) ou 138 134 (sortie correcte)

i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
p (1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}

Exemple d'exécution:

c:\a\ruby>fibadd
100
[[3, 8, 89], [1, 2, 8, 89], [3, 8, 34, 55], [1, 2, 3, 5, 89], [1, 2, 8, 34, 55], [3, 8, 13, 21, 55], [1, 2, 3, 5, 34, 55], [1, 2, 8, 13, 21, 55], [1, 2, 3, 5, 13, 21, 55]]

Changer getsde $*[0]si vous voulez que des arguments de ligne de commande ( >fibadd 100), le caractère +1 cependant.

Avec la sortie correcte:

i=gets.to_i
a=[x=y=1]
a+=[y=x+x=y]until y>i
$><<(1..a.size).flat_map{|n|a.combination(n).select{|o|o.inject(:+)==i}}.map{|o|o*?+}*'

'

Exemples de cycles:

c:\a\ruby>fibadd
100
3+8+89

1+2+8+89

3+8+34+55

1+2+3+5+89

1+2+8+34+55

3+8+13+21+55

1+2+3+5+34+55

1+2+8+13+21+55

1+2+3+5+13+21+55
c:\a\ruby>fibadd
1000
13+987

5+8+987

13+377+610

2+3+8+987

5+8+377+610

13+144+233+610

2+3+8+377+610

5+8+144+233+610

13+55+89+233+610

2+3+8+144+233+610

5+8+55+89+233+610

13+21+34+89+233+610

2+3+8+55+89+233+610

5+8+21+34+89+233+610

2+3+8+21+34+89+233+610
c:\a\ruby>obfcaps
12804
2+5+21+233+1597+10946

2+5+8+13+233+1597+10946

2+5+21+89+144+1597+10946

2+5+21+233+610+987+10946

2+5+21+233+1597+4181+6765

2+5+8+13+89+144+1597+10946

2+5+8+13+233+610+987+10946

2+5+8+13+233+1597+4181+6765

2+5+21+34+55+144+1597+10946

2+5+21+89+144+610+987+10946

2+5+21+89+144+1597+4181+6765

2+5+21+233+610+987+4181+6765

2+5+8+13+34+55+144+1597+10946

2+5+8+13+89+144+610+987+10946

2+5+8+13+89+144+1597+4181+6765

2+5+8+13+233+610+987+4181+6765

2+5+21+34+55+144+610+987+10946

2+5+21+34+55+144+1597+4181+6765

2+5+21+89+144+233+377+987+10946

2+5+21+89+144+610+987+4181+6765

2+5+21+233+610+987+1597+2584+6765

2+5+8+13+34+55+144+610+987+10946

2+5+8+13+34+55+144+1597+4181+6765

2+5+8+13+89+144+233+377+987+10946

2+5+8+13+89+144+610+987+4181+6765

2+5+8+13+233+610+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+10946

2+5+21+34+55+144+610+987+4181+6765

2+5+21+89+144+233+377+987+4181+6765

2+5+21+89+144+610+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+10946

2+5+8+13+34+55+144+610+987+4181+6765

2+5+8+13+89+144+233+377+987+4181+6765

2+5+8+13+89+144+610+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+4181+6765

2+5+21+34+55+144+610+987+1597+2584+6765

2+5+21+89+144+233+377+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+4181+6765

2+5+8+13+34+55+144+610+987+1597+2584+6765

2+5+8+13+89+144+233+377+987+1597+2584+6765

2+5+21+34+55+144+233+377+987+1597+2584+6765

2+5+8+13+34+55+144+233+377+987+1597+2584+6765

Ce dernier (12804) n'a pris que 3 secondes environ!

Poignée de porte
la source

4

Mathematica, 89 85 caractères

Raccourci à 85 caractères grâce à David Carraher.

i=Input[];#~Row~"+"&/@Select[If[#>i,Subsets@{##},#0[#+#2,##]]&[2,1],Tr@#==i&]//Column

Mathematica a une fonction intégrée Fibonacci, mais je ne veux pas l'utiliser.

alephalpha
la source

Très compact. Agréable.

Dr belisarius

1

76 caractères si cela ne vous dérange pas d'imprimer comme une liste de sommes:i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &]

DavidC

1

84 caractères:i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &] // Column

DavidC

2

Python ~~206~~ 181 caractères

import itertools as a
i,j,v,y=1,2,[],input()
while i<1000000:v,i,j=v+[i],j,i+j
for t in range(len(v)+1):
 for s in a.combinations(v,t):
  if sum(s)==y:print "+".join(map(str,s))+"\n"

Exemple d'exécution:

25
1+3+21

1+3+8+13

1000
13+987

5+8+987

13+377+610

2+3+8+987

5+8+377+610

13+144+233+610

2+3+8+377+610

5+8+144+233+610

13+55+89+233+610

2+3+8+144+233+610

5+8+55+89+233+610

13+21+34+89+233+610

2+3+8+55+89+233+610

5+8+21+34+89+233+610

2+3+8+21+34+89+233+610

homme chauve-souris
la source

Débarrassez-vous de tous ces espaces supplémentaires. Vous pouvez utiliser un onglet ou des caractères d'espace pour indenter le code. L'écriture des codes de boucle sur une seule ligne lorsque cela est possible est plus courte, c'estwhile i<1000000:v+=[i];i,j=j,i+j

Wasi

Quelques suggestions (je ne voulais pas simplement plagier votre réponse et publier ma version abrégée) import itertools as z:, supprimez les retours à la ligne après les deux-points, mettez-les y=input()avec la x,y,vligne et supprimez l'espace supplémentaire après la ifdéclaration finale .

SimonT

J'ai inclus vos suggestions dans le code. Merci :)

batman

2

Scala, 171

def f(h:Int,n:Int):Stream[Int]=h#::f(n,h+n)
val x=readInt;(1 to x).flatMap(y=>f(1,2).takeWhile(_<=x).combinations(y).filter(_.sum==x)).foreach(z=>println(z.mkString("+")))

Dan G
la source

2

C #, 376 octets

class A{IEnumerable<int>B(int a,int b){yield return a+b;foreach(var c in B(b,a+b))yield return c;}void C(int n){foreach(var j in B(0,1).Take(n).Aggregate(new[]{Enumerable.Empty<int>()}.AsEnumerable(),(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]b})))).Where(s=>s.Sum()==n))Console.WriteLine(string.Join("+",j));}static void Main(){new A().C(int.Parse(Console.ReadLine()));}}

Non golfé:

class A
{
    IEnumerable<int>B(int a,int b){yield return a+b;foreach(var c in B(b,a+b))yield return c;}
    void C(int n){foreach(var j in B(0,1).Take(n).Aggregate(new[]{Enumerable.Empty<int>()}.AsEnumerable(),(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]{b})))).Where(s=>s.Sum()==n))Console.WriteLine(string.Join("+",j));}
    static void Main(){new A().C(int.Parse(Console.ReadLine()));}
}

La méthode Brenvoie un IEnumerablequi représente l'ensemble (infini) de Fibonacci. La deuxième méthode, étant donnée un nombre n, examine les premiers nnombres de Fibonacci (énorme surpuissance ici), trouve tous les sous-ensembles possibles (l'ensemble de puissance), puis filtre les sous-ensembles dont la somme est exactement n, puis imprime.

Ben Reich
la source

1

APL (75)

I←⎕⋄{⎕←⎕TC[2],1↓,'+',⍪⍵}¨S/⍨I=+/¨S←/∘F¨↓⍉(N⍴2)⊤⍳2*N←⍴F←{⍵,+/¯2↑⍵}⍣{I<⊃⌽⍺}⍳2

Moins compétitif que je ne le souhaiterais, principalement en raison du format de sortie.

Production:

⎕:
      100

 3 + 8 + 89 

 3 + 8 + 34 + 55 

 3 + 8 + 13 + 21 + 55 

 1 + 2 + 8 + 89 

 1 + 2 + 8 + 34 + 55 

 1 + 2 + 8 + 13 + 21 + 55 

 1 + 2 + 3 + 5 + 89 

 1 + 2 + 3 + 5 + 34 + 55 

 1 + 2 + 3 + 5 + 13 + 21 + 55

Explication:

I←⎕: lire l'entrée, stocker I.
⍳2: en commençant par la liste 1 2,
{⍵,+/¯2↑⍵}: ajouter la somme des deux derniers éléments à la liste,
⍣{I<⊃⌽⍺}: jusqu'à Iest plus petit que le dernier élément de la liste.
F←: stocker dans F(ce sont les nombres de fibonacci de 1à I).
N←⍴F: stocke le nombre de fibonacci dans N.
↓⍉(N⍴2)⊤⍳2*N: obtenir les nombres de 1à 2^N, sous forme de bits.
S←/∘F¨: utilisez chacun d'eux comme masque de bits F, stockez-le S.
I=+/¨S: pour chaque sous-liste dans S, voir si la somme est égale à I.
S/⍨: sélectionnez-les parmi S. (Nous avons maintenant toutes les listes de nombres de fibonacci qui se résument à I.)
{... }¨: pour chacun d'entre eux:
- ,'+',⍪⍵: ajoutez un +devant chaque numéro,
- 1↓: retirer le premier +,
- ⎕TC[2]: ajoutez une nouvelle ligne supplémentaire,
- ⎕←: et sortie.

marinus
la source

1

Haskell - 127

Après de nombreuses itérations, je me suis retrouvé avec le code suivant:

f=1:scanl(+)2f
main=getLine>>=putStr.a f "".read
a(f:g)s n|n==f=s++show f++"\n\n"|n<f=""|n>f=a g(s++show f++"+")(n-f)++a g s n

J'aurais pu sauver peut-être un caractère en trichant et en ajoutant un "0+" supplémentaire devant chaque ligne de sortie.

Je veux partager une autre version (longueur 143) que j'ai trouvée en essayant de jouer au golf avec la solution précédente. Je n'ai jamais autant abusé d'opérateurs et de tuples:

f=1:scanl(+)2f
main=getLine>>=(\x->putStr$f€("",read x))
o%p=o++show p;(f:g)€t@(s,n)|n==f=s%f++"\n\n"|n<f=""|n>f=g€(s%f++"+",n-f)++g€t

Cas de test, 256:

256
2+3+5+13+34+55+144

2+3+5+13+89+144

2+3+5+13+233

2+8+13+34+55+144

2+8+13+89+144

2+8+13+233

2+21+34+55+144

2+21+89+144

2+21+233

et 1000:

1000
2+3+8+21+34+89+233+610

2+3+8+55+89+233+610

2+3+8+144+233+610

2+3+8+377+610

2+3+8+987

5+8+21+34+89+233+610

5+8+55+89+233+610

5+8+144+233+610

5+8+377+610

5+8+987

13+21+34+89+233+610

13+55+89+233+610

13+144+233+610

13+377+610

13+987

Quelques données d'efficacité puisque quelqu'un avait ce genre de choses:

% echo "12804" | time ./fibsum-golf > /dev/null
./fibsum-golf > /dev/null  0.09s user 0.00s system 96% cpu 0.100 total
% echo "128040" | time ./fibsum-golf > /dev/null
./fibsum-golf > /dev/null  2.60s user 0.01s system 99% cpu 2.609 total

shiona
la source

0

05AB1E , 19 octets (non concurrent)

ÅFævy©O¹Qi®'+ý}})ê»

Essayez-le en ligne!

Calcule toutes les sommes possibles pour une donnée n. Exemple de sortie pour 1000:

1+1+3+8+144+233+610
1+1+3+8+21+34+89+233+610
1+1+3+8+377+610
1+1+3+8+55+89+233+610
1+1+3+8+987
13+144+233+610
13+21+34+89+233+610
13+377+610
13+55+89+233+610
13+987
2+3+8+144+233+610
2+3+8+21+34+89+233+610
2+3+8+377+610
2+3+8+55+89+233+610
2+3+8+987
5+8+144+233+610
5+8+21+34+89+233+610
5+8+377+610
5+8+55+89+233+610
5+8+987

Urne de poulpe magique
la source

Écrire un nombre sous forme de somme de Fibonacci

Réponses: