9

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!

code-golf fibonacci

— Fixed Point
źródło

1

... Zamierzam po prostu bruteforce to: P Jeśli opublikuję odpowiedź, nie oczekuj, że zadziała ona dobrze :)

— Klamka

Cóż, to kod do golfa, a nie najszybszy kod. :-D

— Fixed Point

1

Napisałem to i faktycznie działa szybko: P

— Klamka

Niezupełnie duplikat, ale ściśle związany z codegolf.stackexchange.com/q/2677/194

— Peter Taylor

1

@shiona Ponieważ nie określiłem, wybierz swój ulubiony. :-)

— Fixed Point

9

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

— Howard
źródło

4

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!

— Klamka
źródło

4

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

— alephalpha
źródło

Bardzo kompaktowy Miły.

— Dr Belisarius,

1

76 znaków, jeśli nie masz nic przeciwko drukowaniu jako listy sum:i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &]

— DavidC

1

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

— DavidC

2

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

— ordynans
źródło

Pozbądź się wszystkich tych dodatkowych spacji. Do wcięcia kodu możesz użyć jednej tabulacji lub znaków spacji. Również zapisywanie kodów pętli w jednym wierszu, jeśli to możliwe, jest krótsze, tj.while i<1000000:v+=[i];i,j=j,i+j

— Wasi

Kilka sugestii (nie chciałem po prostu plagiatować twojej odpowiedzi i opublikować moją skróconą wersję): import itertools as zusuń znaki nowej linii po dwukropkach, wstaw linię y=input()wraz z x,y,vlinią i usuń dodatkowe miejsce po końcowym ifstwierdzeniu.

— SimonT

Włączyłem twoje sugestie do kodu. Dzięki :)

— 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.
źródło

2

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.

— Ben Reich
źródło

1

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.

— marinus
źródło

1

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

— shiona
źródło

0

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

— Urna Magicznej Ośmiornicy
źródło

Napisz liczbę jako sumę Fibonacciego