Teorema Zeckendorf menunjukkan bahwa setiap bilangan bulat positif dapat secara unik direpresentasikan sebagai jumlah angka Fibonacci yang tidak berdekatan. Dalam tantangan ini, Anda harus menghitung jumlah dua angka dalam representasi Zeckendorf.
Biarkan F n menjadi nomor Fibonacci ke- n di mana
F 1 = 1,
F 2 = 2 dan
untuk semua k > 2, F k = F k - 1 + F k - 2 .
The Zeckendorf representasi Z ( n ) dari bilangan bulat non-negatif n adalah himpunan bilangan bulat positif sehingga
n = Σ i ∈ Z ( n ) F i dan
∀ i ∈ Z ( n ) i + 1 ∉ Z ( n ).
(dalam bahasa prosa: representasi Zeckendorf dari angka n adalah himpunan bilangan bulat positif sehingga angka Fibonacci untuk indeks ini berjumlah hingga n dan tidak ada dua bilangan bulat yang berdekatan adalah bagian dari himpunan itu)
Khususnya, representasi Zeckendorf unik. Berikut adalah beberapa contoh untuk representasi Zeckendorf:
Z (0) = ∅ (set kosong)
Z (1) = {1}
Z (2) = {2}
Z (3) = {3} ({1, 2} bukan representasi Zeckendorf dari 3)
Z (10) = {5, 2}
Z (100) = {3, 5, 10}
Dalam tantangan ini, representasi Zeckendorf dikodekan sebagai set bit di mana bit paling signifikan mewakili jika 1
merupakan bagian dari set, dll. Anda dapat mengasumsikan bahwa representasi Zeckendorf dari input dan output cocok menjadi 31 bit.
Tugas Anda adalah menghitung Z ( n + m ) yang diberikan Z ( n ) dan Z ( m ). Solusi dengan panjang terpendek dalam kemenangan oktet.
Anda dapat menemukan implementasi referensi yang ditulis dalam ANSI C di sini . Itu juga dapat digunakan untuk menghasilkan representasi Zeckendorf atau menghitung angka dari representasi Zeckendorf-nya.
Berikut adalah beberapa pasang sampel input dan output, di mana dua kolom pertama berisi input dan kolom ketiga berisi output:
73865 9077257 9478805
139808 287648018 287965250
34 279004309 279004425
139940 68437025 69241105
272794768 1051152 273846948
16405 78284865 83888256
9576577 4718601 19013770
269128740 591914 270574722
8410276 2768969 11184785
16384 340 16724
Jawaban:
K (ngn / k) ,
45 43 4241 byteCobalah online!
@ Algoritma Bubbler
{
}
berfungsi dengan argumenx
64(
)/0
lakukan 64 kali, menggunakan 0 sebagai nilai awal:1,
tambahkan 1+':
tambahkan setiap sebelumnya (biarkan elemen pertama utuh)F:
ditugaskanF
untuk "Urutan fibonacci"|
balik(
..){y!x}\
.. dimulai dengan nilai di sebelah kiri, hitung sisa kumulatif (kiri-ke-kanan) untuk daftar di sebelah kanan. nilai di sebelah kiri adalah jumlah sederhana dari input tanpa representasi zeckendorf:2\x
biner mengkodekan input. ini akan menjadi matriks nbits-by-2|
balik+/'
jumlahkan masing-masing&
dimana 1s? - daftar indeks. jika ada 2s, indeks yang sesuai diulang dua kali.F@
pengindeksan array menjadiF
+/
jumlah<':
kurang dari masing-masing sebelumnya (yang pertama hasilnya akan selalu palsu)2/
decode binersumber
CJam,
7674706359 byteCobalah online di juru bahasa CJam atau verifikasi semua kasus uji sekaligus .
Ide
Kita mulai dengan mendefinisikan variasi kecil dari urutan dalam pertanyaan:
Dengan cara ini, bit 0 (LSB) dari bit array input atau output sesuai dengan angka Fibonacci G 0 dan, secara umum, bit k ke G k .
Sekarang, kami mengganti setiap bit dalam Z (n) dan Z (m) dengan indeks yang dikodekan.
Misalnya, input 532 10 = 1000010100 2 ditransformasikan menjadi [2 4 9] .
Ini menghasilkan dua array integer, yang dapat kita gabungkan untuk membentuk satu array.
Misalnya, jika n = m = 100 , hasilnya adalah A: = [2 4 9 2 4 9] .
Jika kita mengganti setiap k di A dengan G k dan menambahkan hasil, kita memperoleh n + m = 200 , sehingga A adalah suatu cara untuk menguraikan 200 menjadi angka Fibonacci, tetapi tentu bukan satu dari teorema Zeckendorf ini.
Perlu diingat bahwa G k + G k + 1 = G k + 2 dan G k + G k = G k + G k-1 + G k-2 = G k + 1 + G k-2 , kita bisa mengganti berturut-turut dan indeks yang digandakan oleh orang lain (yaitu, (k, k + 1) oleh k + 2 dan (k, k) oleh (k + 1, k - 2) ), mengulangi pergantian-pergantian itu berulang-ulang sampai perwakilan Zeckendorf tercapai. 1
Kasus khusus harus diambil untuk menghasilkan indeks negatif. Karena G -2 = 0 , indeks -2 dapat diabaikan begitu saja. Juga, G -1 = 0 = G 0 , jadi setiap -1 yang dihasilkan harus diganti dengan 0 .
Sebagai contoh kami A , kami mendapatkan representasi (diurutkan) berikut, yang terakhir adalah representasi Zeckendorf.
[2 2 4 4 9 9] → [0 3 4 4 9 9] → [0 5 4 9 9] → [0 6 9 9] → [0 6 7 10] → [0 8 10]
Akhirnya, kami mengkonversi kembali dari array integer ke array bit.
Kode
1 Implementasi mencoba menggantikan 32 kali dan tidak memeriksa apakah representasi Zeckendorf telah tercapai. Saya tidak memiliki bukti formal bahwa ini sudah cukup, tetapi saya sudah menguji semua kemungkinan jumlah representasi 15-bit (yang jumlah penjumlahannya membutuhkan hingga 17 bit) dan 6 pengulangan sudah cukup untuk semuanya. Dalam kasus apa pun, menambah jumlah pengulangan ke 99 dimungkinkan tanpa menambah jumlah byte, tetapi itu akan melumpuhkan kinerja.
sumber
APL (Dyalog Extended) , 39 byte
Cobalah online!
Berubah menjadi program lengkap yang mengambil satu argumen dengan panjang 2, dan juga mengubah generator Fibonacci. Terima kasih kepada @ngn untuk banyak ide.
Digunakan
⎕IO←0
sehingga⍳2
dievaluasi menjadi0 1
.Generator Fibonacci (baru)
Perhatikan bahwa dua angka terakhir tidak akurat, tetapi tidak mengubah output program.
Zeckendorf ke polos (sebagian)
APL (Dyalog Extended) , 47 byte
Cobalah online!
Mengubah Bagian 1 dari jawaban sebelumnya untuk menggunakan kembali angka Fibonacci. Juga, letakkan duplikat 1 untuk menyimpan beberapa byte di tempat lain.
Bagian 1 (baru)
APL (Dyalog Extended) , 52 byte
Cobalah online!
Bagaimana itu bekerja
Tidak ada algoritma yang bagus untuk melakukan penambahan di Zeckendorf karena APL tidak dikenal untuk operasi pada elemen individu dalam sebuah array. Sebagai gantinya, saya melanjutkan untuk mengubah dua input dari Zeckendorf ke integer polos, menambahkannya, dan mengubahnya kembali.
Bagian 1: Zeckendorf to plain integer
Bagian 2: Tambahkan dua bilangan bulat polos
Bagian 3: Konversi jumlah kembali ke Zeckendorf
"Anda dapat berasumsi bahwa representasi Zeckendorf dari input dan output cocok menjadi 31 bit" cukup berguna.
Generator Fibonacci
Ini mengikuti dari properti nomor Fibonacci: jika Fibonacci didefinisikan sebagai
kemudian
Digit Fibonacci ke Zeckendorf
sumber
Haskell, 325
396byteEDIT: versi baru:
z
melakukan pekerjaan.sumber
=
, sehingga orang tua di sana tidak diperlukan , dan seterusnya dan seterusnya, dan perhatikan bahwa:
mengaitkan ke kanan dan Anda dapat memotong beberapa di sana. Tapi, selamat, selamat! Terlihat sangat rumit. Tidak sabar untuk mencari tahu bagaimana ini bekerja!ES6, 130 byte
Saya awalnya mencoba menghitung jumlah di tempat (efektif sepanjang garis implementasi CJam) tetapi saya terus kehabisan sementara, jadi saya hanya mengkonversi angka ke dan kembali dari bilangan bulat nyata.
(Ya, saya mungkin bisa menyimpan byte dengan menggunakan eval.)
sumber
Ruby ,
85 7365 byteCobalah online!
Bagaimana?
Pertama, dapatkan batas atas untuk jumlah yang disandikan: (a + b) * 2 ok.
Sekarang filter semua nomor non-zeckendorf dari (0..limit).
Kami memiliki tabel pencarian, itu menurun dari sini.
sumber
Python 3, 207 byte
Cobalah secara Online! (Verifikasi semua kasus uji)
Penjelasan
Program ini secara langsung memanipulasi terjemahan biner dari representasi Zeckendorf. Fungsi
a(n,m)
melakukan perhitungan utama, dans(n)
merupakan fungsi pembantu yang menghilangkan angka berdekatan yang terdapat dalam representasi Zeckendorf.Mari kita mulai dengan fungsi
s(n)
(diperluas untuk kejelasan):Misalnya, angka 107 (
1101011
dalam biner, mewakili 1 + 2 + 5 + 13 + 21 = 42), mengalami proses berikut:Cobalah secara Online! (s dengan output terperinci)
Ini adalah versi yang diperluas dari
a(n,m)
:Fungsi ini mengubah dua representasi Zeckendorf menjadi empat angka biner yang lebih mudah untuk digabungkan. Baris (A) adalah bitwise OR dari dua representasi biner Zeckendorf - ini sesuai dengan satu salinan dari setiap nomor Fibonacci di kedua kelompok. (B) dan (C) adalah bitwise AND dari dua angka yang bergeser-kanan masing-masing 1 dan 2 kali. Kita tahu bahwa ketika angka-angka Fibonacci yang sesuai untuk (B) dan (C) ditambahkan bersama-sama, mereka akan setara dengan bitwise AND dari
n
danm
karena F (n) = F (n-1) + F (n-2) .Sebagai contoh, katakanlah kita memiliki angka biner n = 101001 (sesuai dengan 1 + 5 + 13) dan m = 110110 (2 + 3 + 8 + 13). Maka kita akan memiliki (A) = 111111 (1 + 2 + 3 + 5 + 8 + 13), yang dikonversi menjadi 1010100 (3 + 8 + 21) dengan fungsi kami
s
, (B) = 10000 (8), dan ( C) = 1000 (5). Kita dapat memeriksa bahwa (1 + 5 + 13) + (2 + 3 + 8 + 13) = (3 + 8 + 21) + (8) + (5) = 45. Proses ini berulang dengan ((3 + 8 + 21) + (8)) + (5) = ((3 + 8 + 21) + (5) + (3)) + (5), dll.Satu kesulitan dengan sistem ini adalah tidak berfungsi untuk angka Fibonacci 1 dan 2, karena mereka tidak mematuhi properti
F(n)=F(n-1)+F(n-2)
(mereka adalah dua angka terendah)! Karena itu, setiap kali 1 atau 2 terkandung dalam keduanyan
danm
, mereka dikeluarkan dari A, B, dan C, maka jumlah mereka ditempatkan di D di bawah properti yang 1 + 1 = 2 dan 2 + 2 = 1 + 3. Misalnya, jika kita menambahkan 1 + 3 (101) + 1 + 3 + 5 (1101), kita mendapatkan:(A): 3 + 5 (1100) = 8 (10000)
(B): 2 (10)
(C): 1 (1)
(D): 2 (10)
Perhatikan bahwa 3 dan 5 ditempatkan dalam A, duplikat 3 dipecah menjadi 2 + 1 dalam B dan C, dan duplikat 1 dihapus dari A, B, dan C, ditambahkan bersama-sama, dan dimasukkan ke dalam D. Demikian pula, jika kita tambahkan 2 + 3 (110) + 2 + 3 + 5 (1110), kita mendapatkan:
(A): 3 + 5 (1100) = 8 (10000)
(B): 2 (10)
(C): 1 (1)
(D): 1 + 3 (101)
Cobalah online! (a dengan output terperinci)
sumber
Bahasa Wolfram (Mathematica) , 218 byte
Cobalah online!
Cukup pencocokan pola.
Tidak Disatukan:
sumber