Zdefiniujmy sekwencję Fibonacciego jako

F(1) = 1

F(2) = 2

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

Mamy więc nieskończoną sekwencję 1,2,3,5,8,13,... Dobrze wiadomo, że każdą dodatnią liczbę całkowitą można zapisać jako sumę niektórych liczb Fibonacciego. Jedynym zastrzeżeniem jest to, że to podsumowanie może nie być wyjątkowe. Zawsze istnieje co najmniej jeden sposób na zapisanie liczby jako sumy liczb Fibonacciego, ale może być ich znacznie więcej.

Twoim wyzwaniem jest napisanie kompletnego programu, który za pomocą stdin przyjmuje dodatnią liczbę całkowitą od jednego do miliona włącznie, a następnie wypisuje za pomocą stdout wszystkie możliwe sumy liczb Fibonacciego, które sumują się do danych wejściowych. Podsumowując, liczby Fibonacciego nie mogą się powtarzać i obejmuje to liczbę 1. W każdym podsumowaniu, jeśli 1jest obecne, musi być obecne tylko raz, ponieważ w mojej definicji powyższej sekwencji 1pojawia się tylko raz. Sumy z tylko terminem są poprawne, więc jeśli liczbą wejściową jest sama liczba Fibonacciego, to sama liczba jest poprawną sumą i musi zostać wydrukowana. W przypadku wielu sum, pomiędzy dowolnymi dwoma sumami musi znajdować się pusty wiersz, aby łatwo je rozróżnić.

Oto kilka próbek.

./myfib 1
1

Jest tylko jedna taka suma i ma ona tylko termin, więc to wszystko, co jest drukowane.

./myfib 2
2

Zauważ, że 1+1nie jest to poprawna suma, ponieważ się 1powtarza.

./myfib 3
1+2

3

Dwie kwoty i obie są wydrukowane z pustą linią pomiędzy nimi.

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

Prawdziwy golf. Wygrywa najkrótszy kod w dowolnym języku. Proszę zamieścić kod wraz z niektórymi przypadkami testowymi (oprócz tego, który podałem powyżej). W przypadku remisów wybieram ten z najwyższymi ocenami po odczekaniu co najmniej dwóch tygodni i prawdopodobnie dłużej. Społeczność może więc głosować za rozwiązaniami, które lubisz. Sprytność / piękno kodu ma o wiele większe znaczenie niż to, kto pierwszy.

Miłego kodowania!

GolfScript, 54 znaki

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

Przetestuj online lub spójrz na przykłady:

> 54
2+5+13+34

> 55
1+2+5+13+34

3+5+13+34

8+13+34

21+34

55

Ruby, 118114 (wyjście z tablicy) lub 138 134 (prawidłowe wyjście)

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

Przykładowy przebieg:

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

Zmień getsna, $*[0]jeśli chcesz argumenty wiersza poleceń ( >fibadd 100), ale znak +1.

Przy prawidłowym wyjściu:

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

'

Przykładowe przebiegi:

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

Ten ostatni (12804) zajął tylko około 3 sekundy!

Mathematica, 89 85 znaków

Skrócony do 85 znaków dzięki Davidowi Carraherowi.

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

Mathematica ma wbudowaną funkcję Fibonacci, ale nie chcę jej używać.

Pyton 206 181 znaków

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"

Przykładowy przebieg:

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

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("+")))

C #, 376 bajtów

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

Nie golfowany:

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

Metoda Bzwraca an IEnumerablereprezentujący cały (nieskończony) zbiór Fibonacciego. Druga metoda, biorąc pod uwagę liczbę n, sprawdza pierwsze nliczby Fibonacciego (tutaj ogromna nadwyżka mocy), znajduje wszystkie możliwe podzbiory (zestaw mocy), a następnie filtruje do podzbiorów, których suma jest dokładnie n, a następnie drukuje.

APL (75)

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

Mniej konkurencyjny, niż bym chciał, głównie ze względu na format wyjściowy.

Wynik:

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

Wyjaśnienie:

• I←⎕: odczytać wejście, zapisać w I.
• ⍳2: zaczynając od listy 1 2,
• {⍵,+/¯2↑⍵}: dodaj sumę dwóch ostatnich elementów do listy,
• ⍣{I<⊃⌽⍺}: dopóki Ijest mniejszy niż ostatni element listy.
• F←: zapisz w F(są to liczby Fibonacciego od 1do I).
• N←⍴F: zapisz liczbę liczb Fibonacciego w N.
• ↓⍉(N⍴2)⊤⍳2*N: uzyskaj liczby od 1do 2^N, jako bity.
• S←/∘F¨: użyj każdego z nich jako maski bitowej F, zapisz w S.
• I=+/¨S: dla każdej podlisty w Ssprawdź, czy jej suma jest równa I.
• S/⍨: wybierz je z S. (Teraz mamy wszystkie listy liczb Fibonacciego, które się sumują I.)
• {... }¨: dla każdego z tych:
  • ,'+',⍪⍵: dodaj +przed każdym numerem,
  • 1↓: zdejmij pierwszy +,
  • ⎕TC[2]: dodaj dodatkową linię,
  • ⎕←: i wyjście.

Haskell - 127

Po wielu iteracjach otrzymałem następujący kod:

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

Mógłbym uratować może jedną postać, oszukując i dodając dodatkowe „0+” przed każdą linią wyjściową.

Chcę udostępnić inną wersję (długość 143), którą wymyśliłem, próbując zagrać w golfa w poprzednim rozwiązaniu. Nigdy wcześniej nie nadużywałem operatorów i krotek tak często:

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

Przypadki testowe, 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

i 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

Niektóre dane dotyczące wydajności, ponieważ ktoś miał te rzeczy:

% 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

05AB1E , 19 bajtów ( niekonkurencyjny )

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

Wypróbuj online!

Oblicza wszystkie możliwe sumy dla danego n. Przykładowe dane wyjściowe dla 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