Tantangan
Dalam tugas ini Anda akan diberikan integer N (kurang dari 10 6 ), temukan cara minimum di mana Anda bisa menjumlahkan ke N hanya menggunakan angka Fibonacci - partisi ini disebut representasi Zeckendorf .
Anda bisa menggunakan angka Fibonacci lebih dari sekali dan jika ada lebih dari satu hasil representasi.
Misalnya jika inputnya adalah 67 maka satu kemungkinan output bisa menggunakan angka Fibonacci 1,3,8,55 yang juga merupakan angka minimum dari angka Fibonacci yang bisa digunakan untuk mendapatkan jumlah 67 .
Input N diberikan pada satu baris, input diakhiri oleh EOF.
Contohnya
Diberikan dalam format input: output
0: 0
47: 34+13
3788: 2584+987+144+55+13+5
1646: 1597+34+13+2
25347: 17711+6765+610+233+21+5+2
677: 610+55+8+3+1
343: 233+89+21
3434: 2584+610+233+5+2
Kendala
- Jumlah input tidak akan melebihi nilai 10 6 .
- Program Anda tidak boleh berjalan lebih dari 5 detik untuk semua input.
- Anda dapat menggunakan bahasa pilihan Anda.
- Solusi terpendek menang!
code-golf
fibonacci
integer-partitions
Pemurah
sumber
sumber
Jawaban:
Motorola 68000 assembly - 34 byte
(Sintaks assembler GNU)
34 → 34: Membuat generator Fibonacci berhenti pada overflow bukan dengan menghitung, dan memperbaiki
0
case sehingga menghasilkan[0]
bukan[]
. Namun, melewatiN
tabrakan negatif sekarang.Komentar di atas adalah prototipe C dari fungsi ini, menggunakan ekstensi bahasa untuk mengidentifikasi parameter apa yang pergi ke mana (secara default, mereka pergi di stack).
Saya TI-89 , dengan prosesor 10MHz nya, membutuhkan waktu 5 menit untuk menjalankan fungsi ini pada 1 - 1.000.000.
Meskipun kode mesin (saat ini) lebih sedikit byte daripada solusi GolfScript, mungkin tidak adil untuk menerima ini sebagai solusi terpendek karena:
Jika Anda memiliki TI-89/92 / V200, Anda dapat mengunduh proyek selengkapnya di sini (kedaluwarsa):
https://rapidshare.com/files/154945328/minfib.zip
Semoga berhasil membujuk RapidShare untuk memberi Anda file yang sebenarnya. Adakah yang tahu host yang bagus untuk file sebesar ini? 8940 adalah banyak sekali byte.
sumber
Javascript (142)
Hanya menangani input tunggal pada satu waktu. Karena input multi-baris tidak berguna untuk JavaScript.
http://jsfiddle.net/EqMXQ/
sumber
C, 244 karakter
Dengan spasi putih:
Program ini akan membaca angka dari input standar dan menulis ke output standar.
sumber
Golfscript, 43 karakter
Saya pikir ini mungkin dapat dikurangi dengan 3 hingga 5 karakter dengan lebih banyak usaha. Misalnya membuka untuk kemudian membuang array terasa sia-sia.
sumber
F # -
282 252241 karaktersumber
Python - 183 Chars
Mayoritas kode menangani banyak input :(
sumber
n=input()
di akhir baris sebelumnya?print
Mathematica 88
Contoh output
sumber
EXCEL: 89 karakter dalam kode unik:
sumber
Scala - 353 karakter (100 karakter untuk menangani beberapa input)
sumber
Iterator.continually(Console.readLine).takeWhile(_ != "").foreach(line => h(Integer.parseInt(line)))
dapat disingkat menjadiio.Source.stdin.getLines.foreach(l=>h(Integer.parseInt(l)))
untuk menyimpan 40-ish karakter.Python 3 (170 karakter)
Input multiline, berhenti di jalur kosong
sumber
C, 151 karakter
versi yang dapat dibaca:
sumber
R, 170
Menangani banyak input dan memberikan hasilnya ke STDOUT
sumber
R (460 karakter)
Versi lain menggunakan R.
Membaca dari file "input", output ke file "output"
"masukan" contoh
Contoh "output"
Versi yang lebih mudah dibaca:
sumber
D (196 karakter)
Jalankan dengan
rdmd --eval=…
. Ini dengan nyaman menyembunyikan boilerplateimport x, y, z;
danvoid main() {…}
:sumber
Menggunakan Java
sumber