9

Definamos la secuencia de Fibonacci como

F(1) = 1

F(2) = 2

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

Entonces tenemos la secuencia infinita 1,2,3,5,8,13,... Es bien sabido que cualquier entero positivo puede escribirse como la suma de algunos números de Fibonacci. La única advertencia es que esta suma podría no ser única. Siempre hay al menos una forma de escribir un número como una suma de números de Fibonacci, pero puede haber muchos más.

Su desafío es escribir un programa completo que use stdin toma un número entero positivo entre uno y un millón inclusive, y luego genera usando stdout todas las sumas posibles de números de Fibonacci que sumen la entrada. En resumen, los números de Fibonacci no deben repetirse y eso incluye el número 1. En cualquier suma, si 1está presente, debe estar presente solo una vez porque en mi definición de la secuencia anterior 1aparece solo una vez. Las sumas con un solo término son válidas, por lo que si el número de entrada es un número de Fibonacci en sí, entonces el número en sí es una suma válida y debe imprimirse. Si hay varias sumas, entonces entre dos sumas debe haber una línea en blanco para distinguirlas fácilmente.

Aquí hay algunas muestras.

./myfib 1
1

Solo hay una suma de este tipo y solo tiene un término, así que eso es todo lo que se imprime.

./myfib 2
2

Tenga en cuenta aquí que 1+1no es una suma válida porque se 1repite.

./myfib 3
1+2

3

Dos sumas y ambas están impresas con una línea en blanco en el medio.

./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

Verdadero código de golf. El código más corto en cualquier idioma gana. Publique su código con algunos casos de prueba (además del que le di anteriormente). En el caso de los empates, elijo el que tiene los votos más altos después de esperar al menos dos semanas y probablemente más. Por lo tanto, la comunidad no dude en votar las soluciones que desee. La inteligencia / belleza del código importa mucho más que quién publica primero.

¡Feliz codificación!

code-golf fibonacci Punto fijo
fuente

1

... solo voy a aplicar fuerza bruta a esto: P Si publico una respuesta, no espere que funcione bien :)

Pomo de la puerta

Bueno, es el código de golf, no el código más rápido. :-D

Punto fijo

1

Lo escribí y en realidad funciona rápido: P

Pomo de la puerta

No es un duplicado, pero está estrechamente relacionado con codegolf.stackexchange.com/q/2677/194

Peter Taylor

1

@shiona Ya que no especifiqué, elige tu favorito. :-)

Punto fijo

9

GolfScript, 54 caracteres

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

Pruébelo en línea o eche un vistazo a los ejemplos:

> 54
2+5+13+34

> 55
1+2+5+13+34

3+5+13+34

8+13+34

21+34

55

Howard
fuente

4

Ruby, 118114 (salida de matriz) o 138134 (salida correcta)

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}}

Ejecución de muestra:

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]]

Cambie getsa $*[0]si desea argumentos de línea de comando ( >fibadd 100), aunque con un carácter +1.

Con la salida correcta:

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*?+}*'

'

Ejecuciones de muestra:

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

¡Ese último (12804) solo tomó unos 3 segundos!

Pomo de la puerta
fuente

4

Mathematica, 89 85 caracteres

Acortado a 85 caracteres gracias a David Carraher.

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

Mathematica tiene una función incorporada Fibonacci, pero no quiero usarla.

alephalpha
fuente

Muy compacto Agradable.

Dr. belisarius

1

76 caracteres si no le importa imprimir como una lista de sumas:i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &]

DavidC

1

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

DavidC

2

Pitón ~~206~~ 181 caracteres

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"

Ejecución de muestra:

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

hombre murciélago
fuente

Deshágase de todos esos espacios adicionales. Puede usar una pestaña o caracteres de espacio para sangrar el código. También escribir los códigos de bucle en una sola línea cuando sea posible es más corto, es decirwhile i<1000000:v+=[i];i,j=j,i+j

Wasi

Algunas sugerencias (no quería simplemente plagiar su respuesta y publicar mi versión abreviada): import itertools as zelimine las nuevas líneas después de los dos puntos, coloque y=input()la x,y,vlínea y elimine el espacio adicional después de la ifdeclaración final .

SimonT

He incluido sus sugerencias en el código. Gracias :)

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
fuente

2

C #, 376 bytes

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()));}}

Sin 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()));}
}

El método Bdevuelve un IEnumerableque representa el conjunto completo (infinito) de Fibonacci. El segundo método, dado un número n, analiza los primeros nnúmeros de Fibonacci (gran exageración aquí), encuentra todos los subconjuntos posibles (el conjunto de potencia) y luego los filtra a subconjuntos cuya suma es exactamente n, y luego imprime.

Ben Reich
fuente

1

APL (75)

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

Menos competitivo de lo que me gustaría, principalmente debido al formato de salida.

Salida:

⎕:
      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

Explicación:

I←⎕: leer entrada, almacenar en I.
⍳2: comenzando con la lista 1 2,
{⍵,+/¯2↑⍵}: agrega la suma de los dos últimos elementos a la lista,
⍣{I<⊃⌽⍺}: hasta que Isea más pequeño que el último elemento de la lista.
F←: almacenar en F(estos son los números de Fibonacci de 1a I).
N←⍴F: almacena la cantidad de números de Fibonacci en N.
↓⍉(N⍴2)⊤⍳2*N: obtener los números de 1a 2^N, como bits.
S←/∘F¨: utilice cada uno de estos como una máscara de bits en F, almacenar en S.
I=+/¨S: para cada sublista en S, ver si la suma es igual a I.
S/⍨: seleccione estos de S. (Ahora tenemos todas las listas de números de Fibonacci que suman I).
{... }¨: para cada uno de estos:
- ,'+',⍪⍵: agregue un +delante de cada número,
- 1↓: tome la primera +vuelta,
- ⎕TC[2]: agregue una nueva línea adicional,
- ⎕←: y salida.

marinus
fuente

1

Haskell - 127

Después de muchas iteraciones terminé con el siguiente código:

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

Podría haber guardado tal vez un personaje haciendo trampa y agregando un "0+" adicional delante de cada línea de salida.

Quiero compartir otra versión (longitud 143) que se me ocurrió mientras intentaba jugar al golf con la solución anterior. Nunca antes había abusado tanto de operadores y tuplas:

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

Casos de prueba, 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

y 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

Algunos datos de eficiencia ya que alguien tenía estas cosas:

% 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
fuente

0

05AB1E , 19 bytes (no competidor)

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

Pruébalo en línea!

Calcula todas las sumas posibles para cualquier dado n. Ejemplo de salida para 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

Urna de pulpo mágico
fuente

Escribe un número como una suma de Fibonacci

Respuestas: