Ambil bilangan bulat positif n sebagai input, dan hasilkan (beberapa) angka desimal yang dapat dibuat menggunakan n bit, diurutkan dengan cara berikut:
Pertama daftar semua angka yang dapat dibuat hanya dengan satu 1
, dan sisanya 0
di representasi biner (diurutkan), lalu semua angka yang dapat dibuat dengan dua berturut-turut 1
, sisanya 0
, lalu tiga berturut 1
- turut dan seterusnya.
Mari kita lihat seperti apa bentuk ini untuk n = 4 :
0001 - 1
0010 - 2
0100 - 4
1000 - 8
0011 - 3
0110 - 6
1100 - 12
0111 - 7
1110 - 14
1111 - 15
Jadi, output untuk n = 4 adalah: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (format output opsional).
Kasus uji:
n = 1
1
n = 2
1 2 3
n = 3
1, 2, 4, 3, 6, 7
n = 8
1, 2, 4, 8, 16, 32, 64, 128, 3, 6, 12, 24, 48, 96, 192, 7, 14, 28, 56, 112, 224, 15, 30, 60, 120, 240, 31, 62, 124, 248, 63, 126, 252, 127, 254, 255
n = 17
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 7, 14, 28, 56, 112, 224, 448, 896, 1792, 3584, 7168, 14336, 28672, 57344, 114688, 15, 30, 60, 120, 240, 480, 960, 1920, 3840, 7680, 15360, 30720, 61440, 122880, 31, 62, 124, 248, 496, 992, 1984, 3968, 7936, 15872, 31744, 63488, 126976, 63, 126, 252, 504, 1008, 2016, 4032, 8064, 16128, 32256, 64512, 129024, 127, 254, 508, 1016, 2032, 4064, 8128, 16256, 32512, 65024, 130048, 255, 510, 1020, 2040, 4080, 8160, 16320, 32640, 65280, 130560, 511, 1022, 2044, 4088, 8176, 16352, 32704, 65408, 130816, 1023, 2046, 4092, 8184, 16368, 32736, 65472, 130944, 2047, 4094, 8188, 16376, 32752, 65504, 131008, 4095, 8190, 16380, 32760, 65520, 131040, 8191, 16382, 32764, 65528, 131056,16383, 32766, 65532, 131064, 32767, 65534, 131068, 65535, 131070, 131071
Ini adalah kode-golf , jadi kode terpendek di setiap bahasa menang!
Penjelasan yang baik sangat dianjurkan , juga untuk solusi dalam "bahasa reguler"!
code-golf
sorting
base-conversion
binary
Stewie Griffin
sumber
sumber
Jawaban:
Python , 53 byte
Cobalah online!
Fungsi rekursif menghasilkan daftar yang disortir sebagai pre-order walk down tree ini (contoh dengan
n=4
):Cabang kiri menggandakan nilainya, dan cabang kanan melakukan
i->i*2+1
dan ada hanya untuk ganjili
. Jadi, jalan pre-order untuk non-daun adalahT(i)=[i]+T(i*2)+i%2*T(i*2+1)
.Pohon berakhir di kedalaman
n
, di manan
input. Ini dicapai dengan mengurangin
setiap langkah ke bawah dan berhenti ketika itu 0.Strategi alternatif adalah untuk mengakhiri nilai-nilai yang
i
melebihi2**n
, daripada melacak kedalaman. Saya menemukan ini satu byte lebih lama:sumber
[f]
adalah sentuhan yang lucu, tidak bisa mengatakan saya pernah melihatnya sebelumnya.Jelly , 6 byte
Ini memenuhi syarat untuk bonus imajiner .
Cobalah online!
Bagaimana itu bekerja
sumber
Ẇ
adalah built-in yang ideal untuk tantangan ini, dan itu diterapkan sehingga hasilnya berada dalam urutan yang tepat untuk tantangan ini. Bagus sekali :-)Mathematica, 40 byte
Setiap angka dalam daftar yang diinginkan adalah selisih dua kekuatan 2, jadi kami cukup membuatnya dalam rangka menggunakan
Table
dan kemudian meratakan daftar. Saya pikir ini menghasilkan bonus imajiner Stewie Griffin :)Mathematica, 35 byte
Port algoritme Dennis's Jelly . Saya tidak tahu tentang
Subsequences
ini sebelumnya! (Saya juga tidak melihat bahwa mil telah mengirimkan jawaban yang tepat ini ... lanjutkan!)sumber
JavaScript (ES6),
595855 byteProgram lengkap yang menerima input melalui prompt dan memberi tahu setiap nomor secara berurutan. Ini juga memenuhi syarat untuk bonus imajiner .
Cuplikan tes
(Catatan: gunakan
console.log
bukanalert
)Tampilkan cuplikan kode
sumber
JavaScript (ES6),
5551 byteMengembalikan daftar bilangan bulat yang dipisahkan oleh ruang.
Bonus imajiner ramah.
Diformat dan dikomentari
Uji kasus
Tampilkan cuplikan kode
sumber
Python 2 ,
6461 byte-3 byte terima kasih kepada Dennis
Cobalah online!
sumber
Mathematica, 35 byte
sumber
Python 2 ,
656358 byteCobalah online!
sumber
(2<<i)-1<<j
... dan Anda sudah menemukan jawabannya. Kerja bagus! Juga, pekerjaan yang baik untuk menyingkirkan rentang gandaHaskell , 37 byte
Cobalah online!
sumber
Haskell, 47 byte
Contoh penggunaan:
f 4
->[1,2,4,8,3,6,12,7,14,15]
. Cobalah online!.Cara kerjanya: untuk setiap angka
b
dalam[1..n]
, mulailah dengan2^b-1
dan gandakan nilai berulang kali dan ambiln-b+1
elemen dari daftar ini.sumber
05AB1E , 6 byte
Cobalah online! atau sebagai Test suite
Penjelasan
Menggunakan trik daftar-jumlah seperti yang ditunjukkan dalam jawaban Dennis 'Jelly
sumber
Groovy,
9089 byteKonversi biner begitu bodoh di groovy.
-1 terima kasih kepada Gurupad Mamadapur
sumber
{(1..<2**it)...
menghemat satu byte.Pyth, 7 byte
Cobalah online.
Menggunakan algoritma Dennis.
sumber
Utilitas Bash + Unix, 51 byte
Cobalah online!
Input n diteruskan dalam argumen.
Gunakan seq untuk mencetak semua angka dengan n atau lebih sedikit digit. (Ini adalah angka dasar-10, jadi ada banyak angka tambahan di sini. Ini boros dan memakan waktu, tapi ini kode golf!)
Panggilan untuk grep hanya menyimpan angka-angka yang terdiri dari 1s diikuti oleh 0s.
Kemudian gunakan sort -r untuk mengurutkan ini dalam urutan leksikografis terbalik.
Akhirnya, dc diatur ke input basis 2 - mendorong angka yang diurutkan pada tumpukan dan kemudian mencetak tumpukan dari atas ke bawah. (Ini mencetak item terakhir yang didorong pertama kali, dll., Itulah sebabnya saya menggunakan sort -r bukan hanya sortir.)
Memperbaiki bug: Saya telah menghilangkan opsi -f% .f ke seq, yang diperlukan untuk penghitungan bilangan bulat dari 1000000 pada. (Terima kasih kepada @TobySpeight untuk menunjukkan bahwa ada masalah.)
sumber
dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc -
hanya melaporkan 12 nilai. Saya pikir Anda ingin yanggrep ^1[01]*$
sebaliknya.Mathematica / Mathics , 69 bytes
Cobalah online!
sumber
Perl 6 , 38 byte
Bagaimana itu bekerja
Yaitu itu membangun angka-angka seperti ini:
Kode:
Perl 6 , 44 byte
Ini adalah pendekatan pertama saya sebelum saya memikirkan solusi bit-shift (sebenarnya lebih sederhana) di atas.
Bagaimana itu bekerja
Yaitu itu membangun angka-angka seperti ini:
sumber
Haskell
5946 BytesSaya mulai dengan
f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]
dari jawaban nimi di atas diperoleh wawasan yang
sum.map(2^)$[0..x]
bisa diringkas menjadi2^x-1
Berakhir dengan
e n=[1..n]>>= \x->map(\y->2^y*(2^x-1))[0..n-x]
[1..n] - daftar dengan jumlah bit berurutan yang ingin kami daur ulang`
>> = --diterjemahkan secara otomatis untuk setiap elemen dalam daftar di sebelah kiri, serahkan ke fungsi di sebelah kanan dan gabungkan semua hasil
\ x -> - deklarasi fungsi lambda dengan satu argumen
map xy - menerapkan fungsi x untuk semua anggota daftar y
Dalam kasus kami x = (\ y-> 2 ^ y * (2 ^ x-1)) - fungsi lambda lain 2 ^ y * (2 ^ x-1)). Rumus ini muncul dari perkalian dengan dua menambahkan nol ke kanan dalam biner (misalnya 0001 hingga 0010). 2 ^ x - 1 adalah jumlah bit yang kami kerjakan. jadi untuk 11 kita memiliki 2 ^ 0 * 3 (yaitu tidak bergeser sama sekali) == 0011, kemudian 2 ^ 1 * 3 = 0110 kemudian 2 ^ 2 * 3 - 1100.
[0..nx] Membuat daftar berapa kali kami dapat menggeser bit. Jika kita bekerja dengan satu 1 maka melihat 0001 kita ingin bergeser 3 kali (4-1). Jika kita bekerja dua 11 kita ingin 4-2 dan seterusnya.
sumber
Python 3, 59 byte
Catatan: ini dibuat secara terpisah dari solusi ovs dan Dennis , meskipun sangat mirip dengan keduanya.
Bagaimana itu bekerja:
Cobalah online!
Tips (baik coding dan uang tunai) selalu diterima!
sumber
Japt , 11 byte
Uji secara online!
Penjelasan
Ini cukup banyak menggunakan pendekatan @ Dennis:
sumber
Python ,
6159 byteCobalah online!
sumber
PHP,
59 5653 bytemenerima input dari STDIN; jalankan bersama
-R
.kerusakan
sumber
$argn
ide yang sangat bagus. Setelah membaca pertanyaan yang saya miliki di kepala saya solusi dengan lebih dari 200 BytesJ , 19 byte
Ini menggunakan metode yang sama dalam solusi @Dennis .
Cobalah online!
Penjelasan
sumber
Python 3, 91 byte
Program lengkap, dengan output yang dipisahkan koma + ruang, seperti yang ditentukan.
Penjelasan:
Notasi bintang membongkar daftar. Begitu
print(*[1,2,3])
juga denganprint(1,2,3)
. Berikanint()
konstruktor string berturut-turut '1's.-~b
mengevaluasib+1
, tetapi Anda tidak harus mengelilinginya dengan tanda kurung saat mengalikan string.Bitshift integer yang dihasilkan semakin banyak kali.
print()
memiliki argumen sep opsional, menentukan string untuk dimasukkan di antara setiap item dalam daftar yang belum dibongkar.sumber
Java 7, 108 byte
Menggandakan nilai awal selama hasilnya lebih kecil dari
2^n
. Setelah itu, perbarui nilai awal menjadi(initial_value * 2) + 1
dan mulai lagi dari sana hingga akhirnya tercapai(2^n)-1
.misalnya untuk
n=4
:Cobalah online!
sumber
Ruby, 50 byte
Saya mencoba beberapa pendekatan "pintar", tetapi ini tampaknya yang terpendek (secara harfiah mengikuti instruksi)
Penjelasan:
Setiap iterasi dimulai dengan 2 ^ n-1 dan dikalikan 2 hingga batas atas tercapai. Tidak ada yang mewah, hanya matematika dasar.
sumber
QBIC , 37 byte - bonus imajiner = masih 37 byte ...
Sayang saya belum memiliki
while-wend
QBIC ... Penjelasan:EDIT: QBIC sekarang memiliki dukungan untuk
WHILE
:Ini hanya 26 byte! Inilah
WHILE
:sumber
MATL,
1918 byte1 byte disimpan berkat @Luis
Cobalah secara Online
sumber
R ,
694846 byteSetiap angka desimal yang sesuai dengan
i in 1..n
yang ada dalam sistem biner dikalikan dengan2^(0..n-i)
, yaitun-i+1
kekuatan pertama dari dua (1, 2, 4, ...).Cobalah online!
sumber
Stax , 9 byte
Jalankan dan debug online!
Penjelasan
Ya, tidak ada konversi basis di sini.
Menggunakan versi yang belum dibongkar (10 byte) untuk menjelaskan.
sumber
Batch, 92 - 0 = 92 byte
Mengurangi 0 untuk bonus imajiner @ StewieGriffin.
sumber