Tulis Angka sebagai Jumlah Fibonacci

9

Mari kita mendefinisikan urutan Fibonacci sebagai 

F(1) = 1

F(2) = 2

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

Jadi kita memiliki urutan yang tak terbatas 1,2,3,5,8,13,... Sudah diketahui bahwa bilangan bulat positif dapat ditulis sebagai jumlah dari beberapa angka Fibonacci. Satu-satunya peringatan adalah bahwa penjumlahan ini mungkin tidak unik. Selalu ada setidaknya satu cara untuk menulis angka sebagai jumlah angka Fibonacci tetapi mungkin ada banyak lagi.

Tantangan Anda adalah untuk menulis program lengkap yang menggunakan stdin mengambil bilangan bulat positif antara satu dan satu juta inklusif, dan kemudian output menggunakan stdout semua kemungkinan penjumlahan angka-angka Fibonacci yang menjumlahkan ke input. Dalam penjumlahan, angka-angka Fibonacci tidak boleh diulang dan itu termasuk angka 1. Dalam penjumlahan apa pun, jika 1ada, itu harus hadir hanya sekali karena dalam definisi saya urutan di atas 1hanya muncul sekali. Penjumlahan dengan satu-satunya istilah adalah valid sehingga jika nomor input adalah angka Fibonacci itu sendiri, maka angka itu sendiri adalah penjumlahan yang valid dan harus dicetak. Jika banyak jumlah, maka di antara dua jumlah mana pun harus ada garis kosong agar mudah dibedakan di antara keduanya.

Berikut ini beberapa contohnya.

./myfib 1
1

Hanya ada satu jumlah seperti itu dan hanya memiliki jangka waktu sehingga hanya itu yang dicetak.

./myfib 2
2

Perhatikan di sini bahwa 1+1ini bukan jumlah yang valid karena 1berulang.

./myfib 3
1+2

3

Dua jumlah dan keduanya dicetak dengan garis kosong di antaranya.

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

Golf kode sejati. Kode terpendek dalam bahasa apa pun menang. Silakan kirim kode Anda dengan beberapa test case (selain yang saya berikan di atas). Dalam hal ikatan, saya memilih yang dengan upvotes tertinggi setelah menunggu setidaknya selama dua minggu dan mungkin lebih lama. Jadi komunitas jangan ragu untuk mengunggah solusi yang Anda suka. Kecerdasan / keindahan kode jauh lebih penting daripada siapa yang memposting terlebih dahulu.

Selamat coding!

code-golf fibonacci Titik pasti
sumber
1
... Saya hanya akan memaksa ini: P Jika saya mengirim jawaban, jangan berharap itu berfungsi dengan baik :)
Gagang Pintu
Yah itu kode-golf bukan kode tercepat. :-D
Fixed Point
1
Saya menulisnya, dan itu benar-benar berjalan cepat: P
Doorknob
Bukan duplikat, tetapi terkait erat dengan codegolf.stackexchange.com/q/2677/194
Peter Taylor
1
@shiona Karena saya tidak menentukan, pilih yang favorit Anda. :-)
Fixed Point

Jawaban:

9

GolfScript, 54 karakter

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

Uji secara online atau lihat contohnya:

> 54
2+5+13+34

> 55
1+2+5+13+34

3+5+13+34

8+13+34

21+34

55
Howard
sumber
4

Ruby, 118 114 (output array) atau 138 134 (output yang benar)

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

Contoh dijalankan:

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

Ubah getske $*[0]jika Anda ingin argumen baris perintah ( >fibadd 100), +1 karakter.

Dengan output yang benar:

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

'

Sampel berjalan:

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

Yang terakhir (12804) hanya membutuhkan waktu sekitar 3 detik!

Gagang pintu
sumber
4

Mathematica, 89 85 karakter

Disingkat menjadi 85 karakter berkat David Carraher.

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

Mathematica memiliki fungsi bawaan Fibonacci, tetapi saya tidak ingin menggunakannya.

alephalpha
sumber
Sangat kompak. Bagus.
Dr. belisarius
1
76 karakter jika Anda tidak keberatan mencetak sebagai daftar jumlah:i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &]
DavidC
1
84 karakter:i = Input[]; #~Row~"+" & /@ Select[If[# > i, Subsets@{##}, #0[# + #2, ##]] &[2, 1], Tr@# == i &] // Column
DavidC
2

Python 206 181 karakter

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"

Contoh Run:

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
sumber
Singkirkan semua ruang ekstra tersebut. Anda dapat menggunakan satu tab atau karakter spasi untuk memasukkan kode. Juga menulis kode loop dalam satu baris bila mungkin lebih pendek yaituwhile i<1000000:v+=[i];i,j=j,i+j
Wasi
Beberapa saran (saya tidak ingin menjiplak jawaban Anda dan memposting versi singkat saya) import itertools as z:, hapus baris baru setelah titik dua, masukkan garis y=input()dengan x,y,vgaris, dan hapus ruang ekstra setelah ifpernyataan akhir .
SimonT
Saya telah memasukkan saran Anda dalam kode. Terima kasih :)
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
sumber
2

C #, 376 byte

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

Tidak Disatukan:

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

Metode Bmengembalikan IEnumerableyang mewakili seluruh set Fibonacci (tak terbatas). Metode kedua, diberi nomor n, melihat nangka-angka Fibonacci pertama (berlebihan di sini), menemukan semua himpunan bagian yang mungkin (power set), dan kemudian menyaring ke himpunan bagian yang jumlahnya tepat n, dan kemudian dicetak.

Ben Reich
sumber
1

APL (75)

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

Kurang kompetitif daripada yang saya inginkan, sebagian besar karena format output.

Keluaran:

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

Penjelasan:

  • I←⎕: baca input, simpan di I.
  • ⍳2: dimulai dengan daftar 1 2,
  • {⍵,+/¯2↑⍵}: tambahkan jumlah dari dua elemen terakhir ke daftar,
  • ⍣{I<⊃⌽⍺}: hingga Ilebih kecil dari elemen terakhir dari daftar.
  • F←: store in F(ini adalah nomor fibonacci dari 1ke I).
  • N←⍴F: menyimpan jumlah angka fibonacci di N.
  • ↓⍉(N⍴2)⊤⍳2*N: dapatkan angka dari 1hingga 2^N, sebagai bit.
  • S←/∘F¨: gunakan masing-masing sebagai bitmask on F, simpan di S.
  • I=+/¨S: untuk setiap sub-daftar di S, lihat apakah jumlah itu sama dengan I.
  • S/⍨: pilih ini dari S. (Sekarang kami memiliki semua daftar nomor fibonacci yang dijumlahkan I.)
  • {... }¨: untuk masing-masing:
    • ,'+',⍪⍵: tambahkan +di depan setiap nomor,
    • 1↓: ambil +back off pertama ,
    • ⎕TC[2]: tambahkan baris baru ekstra,
    • ⎕←: dan output.
marinus
sumber
1

Haskell - 127

Setelah banyak iterasi saya berakhir dengan kode berikut:

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

Saya bisa menyelamatkan mungkin satu karakter dengan menipu dan menambahkan "0+" tambahan di depan setiap baris output.

Saya ingin berbagi versi lain (panjang 143) yang saya buat ketika mencoba golf solusi sebelumnya. Saya tidak pernah menyalahgunakan operator dan tuple sebanyak ini sebelumnya:

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

Kasus uji, 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

dan 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

Beberapa data efisiensi karena seseorang memiliki hal ini:

% 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
sumber
0

05AB1E , 19 byte (Tidak bersaing)

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

Cobalah online!

Hitung semua jumlah yang mungkin untuk setiap yang diberikan n. Contoh output untuk 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
Guci Gurita Ajaib
sumber