Berdasarkan notasi "biner, tetapi dengan dua-dua" yang disebutkan dalam video numberfile ini , tulis sebuah fungsi yang mengambil nomor tunggal sebagai input dan output semua variasi nomor itu dalam sistem "biner" di mana dua-dua diperbolehkan.
Aturan
- Kode hanya boleh berupa fungsi / metode, bukan program lengkap
- Input adalah bilangan bulat yang diteruskan sebagai parameter tunggal ke fungsi
- Output adalah semua variasi yang valid dari nomor input yang dikonversi menjadi "binary, tetapi dengan notasi dua-duanya"
- Output adalah nilai pengembalian fungsi, tetapi bisa dalam format apa pun yang nyaman selama itu jelas (misalnya, 3 int, 3 string, string yang dibatasi koma / spasi, array int, dll), pesanan tidak penting
- Jika suatu bahasa mengandung fungsi bawaan untuk mencapai hasil, bahasa tersebut tidak diizinkan
- Kode terpendek dalam byte adalah pemenangnya
Penjelasan dari output
Sebagai contoh, jika Anda melewati angka 9
, Anda dapat mengubahnya menjadi biner 1001
, tetapi jika Anda mengizinkan 2
s di setiap posisi, Anda juga bisa menuliskannya sebagai 201
(yaitu 2*4 + 0*2 + 1*1
), atau 121
(yaitu 1*4 + 2*2 + 1*1
), seperti yang ditunjukkan dalam tabel ini:
+----+----+----+----+
| 8s | 4s | 2s | 1s |
+----+----+----+----+
| 1 | 0 | 0 | 1 |
| 0 | 2 | 0 | 1 |
| 0 | 1 | 2 | 1 |
+----+----+----+----+
Jadi, jika dilewati 9
, fungsi Anda perlu mengembalikan tiga angka 1001
,, 201
dan 121
.
Format dan ketertiban tidak relevan, asalkan sudah jelas (yaitu [121,201,1001]
, "0201 0121 1001"
, ("1001","121","201")
adalah hasil yang valid ketika diberi masukan dari 9
).
Contohnya
2
=>10, 2
9
=>1001, 201, 121
10
=>1010, 210, 202, 1002, 122
23
=>2111, 10111
37
=>100101, 20101, 100021, 20021, 12101, 12021, 11221
sumber
Jawaban:
GolfScript (25 byte) / CJam (
1917 byte)GolfScript:
Ini menciptakan fungsi anonim (lihat diskusi meta tentang izin fungsi anonim ).
Demo online
Terjemahan langsung ke CJam adalah (dengan terima kasih kepada Martin Büttner karena telah mencukur beberapa karakter)
Pembedahan
Alasan untuk operasi kuadrat adalah bahwa kita perlu beralih ke nilai terbesar yang mungkin yang representasi ternernya, yang ditafsirkan dalam biner, sama dengan
^
. Karena2 = 10
, representasi biner "normal"^
adalah yang penting. Jika kita mengonversikannya menjadi terner, kita menemukan bahwa kasus "terburuk" adalah kekuatan 2. Pendekatan yang optimal adalah dengan membawa argumen ke kekuatanln 3/ln 2 ~= 1.585
, tetapi mengkuadratkan jauh lebih pendek.sumber
Python 2 (59 byte)
(Terima kasih banyak kepada @grc, @xnor, dan @PeterTaylor karena telah membantu mengobrol)
Rekursi sederhana, panggilan dengan
S(23)
atau serupa.Penjelasan
Gagasan umum adalah bahwa jika
n
ekspansi biner berakhir dengan a1
, maka setiap ekspansi pseudo-biner ("biner, tetapi dengan dua") juga harus diakhiri dengan a1
. Kalau tidak bisa diakhiri dengan0
atau2
.Karenanya kita melihat bagian terakhir dari
n
, bagikan dan cabang sesuai.Pembedahan
Variabel:
n
: Jumlah yang ingin kami temukan pseudo-binary ekspansiB
: Sebuah string pseudo-binary yang sedang dibangun dari kanan ke kirisumber
Bash + coreutils, 77
(Itu adalah TABkarakter dalam ekspresi grep.)
Ini sedikit menekuk aturan ini:
"Seandainya suatu bahasa mengandung fungsi bawaan untuk mencapai hasil, bahasa tersebut tidak diizinkan"
Ternyata yang
dc
memiliki kebalikan dari apa yang kita butuhkan dibangun. Misalnya jika kita menetapkan basis input ke 2 dan memasukkan angka biner dengan dua, itu akan benar menguraikannya. (Demikian pula jika mode input adalah basis 10, maka AF diuraikan sebagai "digit" desimal 10-15).seq
membuat daftar semua angka desimal hingga representasi biner standar dari n, diuraikan sebagai desimal. Kemudian semua angka yang mengandung selain {0,1,2} disaring. Kemudiandc
parsing angka yang tersisa sebagai biner untuk melihat mana yang mengevaluasi kembali ke n.Fungsi Bash hanya dapat "mengembalikan" bilangan bulat skalar 0-255. Jadi saya mengambil kebebasan untuk mencetak daftar ke STDOUT sebagai cara saya "kembali". Ini idiomatis untuk skrip shell.
Keluaran:
sumber
Haskell, 82
ini hanya solusi brute-force. ini sangat tidak efisien, karena diharapkan dapat menembus 3 kemungkinan.
sumber
Jelly , 10 byte, tantangan tanggal kiriman bahasa
Cobalah online!
Solusi bruteforce hingga sejumlah hiperbasi sama dengan input (format ini dikenal sebagai "hiperbinari"). Karena itu, sangat tidak efisien, berjalan di O (3 n ).
Penjelasan
sumber
PHP, 138 Bytes
Kerusakan
sumber
C ++, 159 byte
Uji di sini
sumber
k, 21 byte
Menggunakan metode yang sama dengan jawaban Golfscript Peter Taylor
Contoh:
sumber