Konversikan angka menjadi biner ... tetapi Anda juga dapat menggunakan keduanya

20

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 2s 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,, 201dan 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
Alconja
sumber
1
Dua? Dalam biner? Apakah ini komputasi kuantum?
Matius Roh

Jawaban:

10

GolfScript (25 byte) / CJam ( 19 17 byte)

GolfScript:

{:^.*,{3base}%{2base^=},}

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)

{:X_*,3fb{2bX=},}

Pembedahan

{             # Function boilerplate
  :^          # Store parameter as variable ^
  .*          # Square parameter - see detailed explanation below
  ,{3base}%   # Produce an array of 0 to ^*^-1 in ternary
  {2base^=},  # Filter to those which evaluate to ^ in binary
}

Alasan untuk operasi kuadrat adalah bahwa kita perlu beralih ke nilai terbesar yang mungkin yang representasi ternernya, yang ditafsirkan dalam biner, sama dengan ^. Karena 2 = 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 kekuatan ln 3/ln 2 ~= 1.585, tetapi mengkuadratkan jauh lebih pendek.

Peter Taylor
sumber
Saya yakin terjemahan CJam akan jauh lebih kecil.
Pengoptimal
1
@Optimizer silakan ;-)
John Dvorak
GolfScript? Bung aku noob
pythonian29033
8

Python 2 (59 byte)

S=lambda n,B="":[B][n:]or~n%2*S(n/2-1,"2"+B)+S(n/2,`n&1`+B)

(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 nekspansi biner berakhir dengan a 1, maka setiap ekspansi pseudo-biner ("biner, tetapi dengan dua") juga harus diakhiri dengan a 1. Kalau tidak bisa diakhiri dengan 0atau 2.

Karenanya kita melihat bagian terakhir dari n, bagikan dan cabang sesuai.

Pembedahan

S=lambda n,B="":           # Lambda expression
[B][n:]or                  # Short circuit, return [B] if n==0 else what follows
~n%2*                      # Keep next list result if n is even else turn into []
S(n/2-1,"2"+B)             # Add a "2" to B, recurse
+
S(n/2,`n&1`+B)             # Add "0" or "1" to B depending on n's last bit, recurse

Variabel:

  • n: Jumlah yang ingin kami temukan pseudo-binary ekspansi
  • B: Sebuah string pseudo-binary yang sedang dibangun dari kanan ke kiri
Sp3000
sumber
5

Bash + coreutils, 77

f()(seq `dc -e2o$1p`|sed '/[3-9]/d;s/.*/&n9P2i&pAi/'|dc|grep -Po ".*(?= $1)")

(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 dcmemiliki 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).

seqmembuat daftar semua angka desimal hingga representasi biner standar dari n, diuraikan sebagai desimal. Kemudian semua angka yang mengandung selain {0,1,2} disaring. Kemudian dcparsing 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:

$ f 2
2   
10  
$ f 9
121 
201 
1001    
$
Trauma Digital
sumber
4

Haskell, 82

t n=[dropWhile(==0)s|s<-mapM(\_->[0..2])[0..n],n==sum[2^(n-i)*v|(i,v)<-zip[0..]s]]

ini hanya solusi brute-force. ini sangat tidak efisien, karena diharapkan dapat menembus 3 kemungkinan.

haskeller bangga
sumber
3

Jelly , 10 byte, tantangan tanggal kiriman bahasa

ṗ@3Ḷ¤Ḅ=¥Ðf

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

ṗ@3Ḷ¤Ḅ=¥Ðf
ṗ@            Construct all lists with the given length, and elements taken from
  3Ḷ¤         the list [0,1,2]
        Ðf    then take only those elements which
     Ḅ=¥      when interpreted as binary, equal {the original number}

sumber
2

PHP, 138 Bytes

function p($v,$i=0,$r=""){global$a;if($v==0)$a[]=$r?:0;elseif($v>0)for(;$l<3;)p($v-2**$i*$l,$i+1,+$l++.$r);}p($argv[1]);echo join(",",$a);

Kerusakan

function p($v,$i=0,$r=""){
    global$a;
    if($v==0)$a[]=$r?:0;  # fill result array
    elseif($v>0) # make permutations
        for(;$l<3;)
            p($v-2**$i*$l,$i+1,+$l++.$r); #recursive
}
p($argv[1]);
echo join(",",$a); # Output
Jörg Hülsermann
sumber
1

C ++, 159 byte

void c(int x,string r){int i,t=0,s=r.size();if(s<8){if(r[0]>48){for(i=0;i<s;i++)t+=(r[s-i-1]-48)*1<<i;if(t==x)cout<<r<<" ";}for(char n=48;n<51;n++)c(x,r+n);}}

Uji di sini

Johan du Toit
sumber
1

k, 21 byte

Menggunakan metode yang sama dengan jawaban Golfscript Peter Taylor

{X@&x=2/:'X:3\:'!x*x}

Contoh:

k) {X@&x=2/:'X:3\:'!x*x}9
(1 2 1;2 0 1;1 0 0 1)
k) {X@&x=2/:'X:3\:'!x*x}10
(1 2 2;2 0 2;2 1 0;1 0 0 2;1 0 1 0)
skeevey
sumber