9

Definieren wir die Fibonacci-Sequenz als

F(1) = 1

F(2) = 2

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

Wir haben also die unendliche Folge 1,2,3,5,8,13,... Es ist bekannt, dass jede positive ganze Zahl als Summe einiger Fibonacci-Zahlen geschrieben werden kann. Die einzige Einschränkung ist, dass diese Summe möglicherweise nicht eindeutig ist. Es gibt immer mindestens eine Möglichkeit, eine Zahl als Summe von Fibonacci-Zahlen zu schreiben, aber es kann noch viele weitere geben.

Ihre Herausforderung besteht darin, ein vollständiges Programm zu schreiben, das mit stdin eine positive ganze Zahl zwischen einer und einer Million einschließlich aufnimmt und dann mit stdout alle möglichen Summierungen von Fibonacci-Zahlen ausgibt, die sich zur Eingabe summieren. In einer Summe dürfen sich die Fibonacci-Zahlen nicht wiederholen und das schließt die Zahl ein 1. Wenn eine Summation 1vorhanden ist, darf sie nur einmal vorhanden sein, da sie in meiner Definition der obigen Sequenz 1nur einmal vorkommt. Summierungen mit nur Term sind gültig. Wenn die eingegebene Nummer eine Fibonacci-Nummer selbst ist, ist die Nummer selbst eine gültige Summierung und muss gedruckt werden. Wenn mehrere Summen vorhanden sind, muss zwischen zwei beliebigen Summen eine Leerzeile stehen, um leicht zwischen ihnen unterscheiden zu können.

Hier sind einige Beispiele.

./myfib 1
1

Es gibt nur eine solche Summe und sie hat nur einen Begriff, das ist alles, was gedruckt wird.

./myfib 2
2

Beachten Sie hier, dass dies 1+1keine gültige Summe ist, da sich dies 1wiederholt.

./myfib 3
1+2

3

Zwei Summen und beide werden mit einer Leerzeile dazwischen gedruckt.

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

Echter Code-Golf. Der kürzeste Code in einer Sprache gewinnt. Bitte posten Sie Ihren Code mit einigen Testfällen (außer dem oben angegebenen). Bei Krawatten wähle ich die mit den höchsten Stimmen aus, nachdem ich mindestens zwei Wochen und wahrscheinlich länger gewartet habe. Daher kann die Community gerne alle Lösungen bewerten, die Sie mögen. Die Klugheit / Schönheit des Codes ist viel wichtiger als die, die zuerst posten.

Viel Spaß beim Codieren!

code-golf fibonacci Fixpunkt
quelle

1

... Ich werde dies nur brutal erzwingen: P Wenn ich eine Antwort poste, erwarte nicht, dass sie gut funktioniert :)

Türknauf

Nun, es ist Code-Golf, nicht der schnellste Code. :-D

Fixpunkt

1

Ich habe es geschrieben und es läuft tatsächlich schnell: P

Türknauf

Nicht ganz ein Duplikat, aber eng verwandt mit codegolf.stackexchange.com/q/2677/194

Peter Taylor

1

@shiona Da ich nicht angegeben habe, wählen Sie Ihren Favoriten. :-)

Fixpunkt

9

GolfScript, 54 Zeichen

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

Testen Sie es online oder sehen Sie sich die Beispiele an:

> 54
2+5+13+34

> 55
1+2+5+13+34

3+5+13+34

8+13+34

21+34

55

Howard
quelle

4

Ruby, 118 114 (Array-Ausgabe) oder 138 134 (korrekte Ausgabe)

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

Probelauf:

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

Wechseln Sie getszu, $*[0]wenn Sie Befehlszeilenargumente ( >fibadd 100) möchten , jedoch +1 Zeichen.

Mit der richtigen Ausgabe:

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

'

Probeläufe:

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

Der letzte (12804) dauerte nur etwa 3 Sekunden!

Türknauf
quelle

4

Mathematica, 89 85 Zeichen

Dank David Carraher auf 85 Zeichen verkürzt.

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

Mathematica hat eine eingebaute Funktion Fibonacci, aber ich möchte sie nicht verwenden.

Alephalpha
quelle

Sehr kompakt. Nett.

Dr. Belisarius

1

76 Zeichen, wenn Sie nichts dagegen haben, als Liste der Summen zu i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &]

drucken

1

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

DavidC

2

Python ~~206~~ 181 Zeichen

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"

Probelauf:

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

Batman
quelle

Entfernen Sie all diese zusätzlichen Leerzeichen. Sie können einen Tabulator oder Leerzeichen verwenden, um Code einzurücken. Auch das Schreiben der Schleifencodes in einer Zeile, wenn möglich, ist kürzer, dhwhile i<1000000:v+=[i];i,j=j,i+j

Wasi

Einige Vorschläge (ich wollte nicht nur Ihre Antwort plagiieren und meine verkürzte Version veröffentlichen): import itertools as zEntfernen Sie die Zeilenumbrüche nach den Doppelpunkten, setzen Sie y=input()die x,y,vZeile ein und entfernen Sie den zusätzlichen Platz nach der endgültigen ifAnweisung.

SimonT

Ich habe Ihre Vorschläge in den Code aufgenommen. Danke :)

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

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

Die Methode Bgibt eine zurück IEnumerable, die die gesamte (unendliche) Fibonacci-Menge darstellt. Die zweite Methode, bei der eine Zahl angegeben ist n, betrachtet die ersten nFibonacci-Zahlen (hier ein großer Overkill), findet alle möglichen Teilmengen (die Potenzmenge) und filtert dann zu Teilmengen, deren Summe genau ist n, und druckt dann.

Ben Reich
quelle

1

APL (75)

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

Weniger wettbewerbsfähig als ich möchte, hauptsächlich wegen des Ausgabeformats.

Ausgabe:

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

Erläuterung:

I←⎕: Eingabe lesen, speichern in I.
⍳2: beginnend mit der Liste 1 2,
{⍵,+/¯2↑⍵}: Addiere die Summe der letzten beiden Elemente zur Liste,
⍣{I<⊃⌽⍺}: bis Iist kleiner als das letzte Element der Liste.
F←: speichern in F(dies sind die Fibonacci-Zahlen von 1bis I).
N←⍴F: Speichern Sie die Anzahl der Fibonacci-Zahlen in N.
↓⍉(N⍴2)⊤⍳2*N: Holen Sie sich die Zahlen von 1bis 2^Nals Bits.
S←/∘F¨: Verwenden Sie diese als Bitmaske auf F, speichern Sie in S.
I=+/¨S: Überprüfen Sie für jede Unterliste in S, ob die Summe gleich ist I.
S/⍨: Wählen Sie diese aus S. (Jetzt haben wir alle Listen von Fibonacci-Zahlen, die sich summieren I.)
{... }¨: für jede dieser:
- ,'+',⍪⍵: füge +vor jeder Zahl ein hinzu,
- 1↓: nimm den ersten +zurück,
- ⎕TC[2]: einen zusätzlichen Zeilenumbruch hinzufügen,
- ⎕←: und Ausgabe.

Marinus
quelle

1

Haskell - 127

Nach vielen Iterationen kam ich zu folgendem Code:

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

Ich hätte vielleicht ein Zeichen speichern können, indem ich betrogen und vor jeder Ausgabezeile eine zusätzliche "0+" hinzugefügt hätte.

Ich möchte eine andere Version (Länge 143) teilen, die ich mir ausgedacht habe, als ich versucht habe, die vorherige Lösung zu spielen. Ich habe Operatoren und Tupel noch nie so oft missbraucht:

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

Testfälle, 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

und 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

Einige Effizienzdaten, seit jemand dieses Zeug hatte:

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

0

05AB1E , 19 Bytes (nicht konkurrierend)

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

Probieren Sie es online aus!

Berechnet alle möglichen Summen für eine bestimmte n. Beispielausgabe für 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

Magische Krakenurne
quelle

Schreiben Sie eine Zahl als Fibonacci-Summe

Antworten: