9

Vamos definir a sequência de Fibonacci como

F(1) = 1

F(2) = 2

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

Portanto, temos a sequência infinita 1,2,3,5,8,13,... É sabido que qualquer número inteiro positivo pode ser escrito como uma soma de alguns números de Fibonacci. A única ressalva é que esse somatório pode não ser único. Sempre há pelo menos uma maneira de escrever um número como uma soma dos números de Fibonacci, mas pode haver muitos mais.

Seu desafio é escrever um programa completo que, usando stdin, receba um número inteiro positivo entre um e um milhão, inclusive, e emita usando stdout todas as somas possíveis de números de Fibonacci que somam a entrada. Em resumo, os números de Fibonacci não devem se repetir e isso inclui o número 1. Em qualquer soma, se 1estiver presente, deve estar presente apenas uma vez, porque na minha definição da sequência acima 1aparece apenas uma vez. As somas com apenas um termo são válidas, portanto, se o número de entrada for um número de Fibonacci, o número em si será uma soma válida e deverá ser impresso. Se várias somas, entre duas somas, deve haver uma linha em branco para distinguir facilmente entre elas.

Aqui estão algumas amostras.

./myfib 1
1

Existe apenas uma dessas somas e tem apenas um termo, e é isso que é impresso.

./myfib 2
2

Observe aqui que 1+1não é uma soma válida porque se 1repete.

./myfib 3
1+2

3

Duas somas e ambas são impressas com uma linha em branco no meio.

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

Verdadeiro código de golfe. O código mais curto em qualquer idioma vence. Poste seu código com alguns casos de teste (além do que eu forneci acima). No caso de empate, eu escolho aquele com os votos mais altos depois de esperar pelo menos por duas semanas e provavelmente mais. Portanto, a comunidade sinta-se à vontade para votar em qualquer solução que desejar. A inteligência / beleza do código é muito mais importante do que quem publica primeiro.

Feliz codificação!

code-golf fibonacci Ponto fixo
fonte

11

... Vou usar força bruta para isso: P Se eu postar uma resposta, não espere que ela tenha um bom desempenho :) #

Maçaneta da porta

Bem, é código-golfe, não código mais rápido. :-D

Ponto fixo

11

Eu escrevi e realmente funciona rápido: P

Maçaneta da porta

Não é uma duplicata, mas está intimamente relacionado a codegolf.stackexchange.com/q/2677/194 #

Peter Taylor

11

@ shiona Desde que eu não especifiquei, escolha o seu favorito. :-)

Ponto fixo

9

GolfScript, 54 caracteres

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

Teste on - line ou veja os exemplos:

> 54
2+5+13+34

> 55
1+2+5+13+34

3+5+13+34

8+13+34

21+34

55

Howard
fonte

4

Ruby, 118 114 (saída da matriz) ou 138 134 (saída correta)

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

Exemplo de execução:

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

Altere getspara $*[0]se você deseja argumentos da linha de comando ( >fibadd 100), com um caractere +1.

Com a saída correta:

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

'

Amostras de execuções:

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

Esse último (12804) levou apenas cerca de 3 segundos!

Maçaneta da porta
fonte

4

Mathematica, 89 85 caracteres

Reduzido para 85 caracteres graças a David Carraher.

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

O Mathematica tem uma função interna Fibonacci, mas não quero usá-la.

alefalpha
fonte

Muito compacto. Agradável.

Dr. belisarius

11

76 caracteres se você não se importa de imprimir como uma lista de somas:i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &]

DavidC 19/12/2013

11

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

DavidC

2

Pitão ~~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"

Exemplo de execução:

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

homem Morcego
fonte

Livre-se de todos esses espaços extras. Você pode usar uma guia ou caracteres de espaço para recuar o código. Também escrever os códigos de loop em uma única linha, quando possível, é mais curto, ou seja,while i<1000000:v+=[i];i,j=j,i+j

Wasi

Algumas sugestões (eu não queria plagiar sua resposta e postar minha versão abreviada): import itertools as zremova as novas linhas após os dois pontos, insira y=input()a x,y,vlinha e remova o espaço extra após a ifdeclaração final .

SimonT

Incluímos suas sugestões no código. Obrigado :)

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
fonte

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

Ungolfed:

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

O método Bretorna um IEnumerableque representa todo o conjunto (infinito) de Fibonacci. O segundo método, dado um número n, analisa os primeiros nnúmeros de Fibonacci (enorme exagero aqui), encontra todos os subconjuntos possíveis (o conjunto de potência) e depois filtra para os subconjuntos cuja soma é exatamente ne depois imprime.

Ben Reich
fonte

1

APL (75)

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

Menos competitivo do que eu gostaria, principalmente por causa do formato de saída.

Resultado:

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

Explicação:

I←⎕: ler entrada, armazenar em I.
⍳2: começando com a lista 1 2,
{⍵,+/¯2↑⍵}: adicione a soma dos dois últimos elementos à lista,
⍣{I<⊃⌽⍺}: até Ié menor que o último elemento da lista.
F←: armazenar em F(estes são os números de fibonacci de 1a I).
N←⍴F: armazene a quantidade de números de fibonacci em N.
↓⍉(N⍴2)⊤⍳2*N: obtenha os números de 1para 2^N, como bits.
S←/∘F¨: use cada um deles como máscara de bit F, armazene S.
I=+/¨S: para cada sub-lista S, veja se a soma é igual a I.
S/⍨: selecione estes de S. (Agora, temos todas as listas de números de fibonacci que somam I.)
{... }¨: para cada um destes:
- ,'+',⍪⍵: adicione um +na frente de cada número,
- 1↓: retire a primeira +,
- ⎕TC[2]: adicione uma nova linha extra,
- ⎕←: e saída.

marinus
fonte

1

Haskell - 127

Após muitas iterações, acabei com o seguinte 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

Eu poderia ter salvo talvez um caractere trapaceando e adicionando um "0+" extra na frente de cada linha de saída.

Quero compartilhar outra versão (comprimento 143) que eu criei enquanto tentava jogar a solução anterior. Nunca abusei tanto de operadores e de tuplas antes:

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 teste, 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

e 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

Alguns dados de eficiência, já que alguém tinha essas coisas:

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

0

05AB1E , 19 bytes (Não concorrente)

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

Experimente online!

Calcula todas as somas possíveis para qualquer dado n. Exemplo de saída 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 polvo mágico
fonte

Escreva um número como uma soma de Fibonacci

Respostas: