Bagi saya menjadi dua

15

Anda akan diberi nomor x, di mana 0 <= x <= 2^32 - 1.

Anda harus menampilkan daftar angka dalam desimal, setelah pemisahan rekursif dalam format biner.

Contoh:

Contoh 1:

255 -> 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1

Daftar saat ini adil 255.

Representasi biner dari 255is 1111 1111. Memisahkannya, kita dapatkan 1111dan 1111, yang dalam desimal adalah 15dan 15.

Kami menambahkannya ke daftar, jadi kami akan memilikinya 255 15 15.

Sekarang angka 15dan 15akan berfungsi sebagai input dan angka-angka ini harus dibagi.

Melakukannya lagi, kita mendapatkan ( 3 3dari kedua 15s): 255 15 15 3 3 3 3.

Melanjutkan logika, daftar akhir akan 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1. Dan karena 1tidak lagi dapat dibagi, output berhenti.

Contoh 2:

225 -> 225 14 1 3 2 1 1 1 0

Daftar awal adalah 225.

Representasi biner dari 225is 1110 0001. Memisahkannya, kita dapatkan 1110dan 0001, yang dalam desimal adalah 14dan 1.

Menambahkan itu ke daftar, kita dapatkan 225 14 1.

Sekarang angka 14dan 1akan berfungsi sebagai input dan angka-angka ini harus dibagi.

Karena 1tidak ada splittable, hasilnya akan menjadi 225 14 1 3 2.

Contoh 3:

32 -> 32 4 0 1 0

Ketentuan :

  1. Jika jumlah digit biner ganjil, angka pertama akan memiliki satu digit biner lebih sedikit dari yang berikutnya. Contoh, 20 (10100)akan dibagi menjadi 10dan 100, dengan output desimal menjadi 2dan 4.
  2. Aturan celah standar berlaku.
  3. 0dan 1tidak menyebar lebih jauh.
  4. Program macet karena mencoba menampilkan terlalu banyak angka adalah kondisi keluar yang valid.
ctrl-shift-esc
sumber
Hanya sebuah saran tetapi bagaimana dengan memiliki digit biner yang diisi dengan 0ketika panjangnya aneh?
caird coinheringaahing
1
@ Setan'sSon Jika Anda membungkuk di depan, itu setara dengan deskripsi.
isaacg
1
Apakah urutan output yang ditentukan diperlukan atau hanya nilai-nilainya?
Jonathan Allan
@ Setan'sSon. Tidak ada bantalan dengan 0s.
ctrl-shift-esc
1
@ JonathanAllan Perintah output yang ditentukan diperlukan.
ctrl-shift-esc

Jawaban:

13

Pyth, 18 byte

u+QiR2smc2+0dt#.BM

Suite uji

Kode ini melakukan sesuatu yang sangat rumit dan pintar u, operator titik tetap Pyth.

Tubuh fungsi, yang merupakan segalanya selain u, cukup mudah:

+QiR2smc2+0dt#.BM
+QiR2smc2+0dt#.BMG    Implicit variable
                      G will store the list of numbers from the previous iteration.
              .BMG    Map each number to its binary representation
            t#        Filter out the ones of length 1 (0 and 1)
      m               Map the remaining binary
         +0d          Prefix with a 0
       c2             Chop in half.
                      Since c puts the larger half first, prefixing with a 0
                      makes the chop work out right, and doesn't change the value.
     s                Concatenate
  iR2                 Map back to binary
+Q                    Add the input to the front of the list

Kode ini menghilangkan 0s dan 1s, membagi setiap angka, dan menambahkan input di depan.

u akan menjalankan fungsi ini pada hasil sebelumnya dari fungsi sampai hasilnya berhenti berubah.

Nilai awal apa yang udigunakan? Itu bagian yang pintar: kode tidak menentukan nilai apa yang digunakan, jadi default untuk input. Tetapi input bukan daftar angka - ini nomor. Pyth secara implisit memaksa angka pada waktu pertama melalui loop ke kisaran angka - [0, 1, ..., Q-1]. Itu tidak terlihat seperti output yang ingin kita dapatkan. Untungnya, uakan menemukan hasil yang benar terlepas dari apa input awal - output yang diinginkan adalah satu-satunya titik tetap dari fungsi, dan aplikasi berulang akan selalu mencapainya.

Mari kita lihat nilai tengah dari program dengan input 7. Saya telah menyoroti awalan hasil yang dijamin benar, terlepas dari input awal:

  1. 7(Secara implisit [0, 1, 2, 3, 4, 5, 6])

  2. [7,1, 0, 1, 1, 1, 0, 1, 1, 1, 2]

  3. [7, 1, 3,1, 0]

  4. [7, 1, 3, 1, 1]

Yang merupakan output.


Dikemas Pyth, 16 byte

Perhatikan bahwa karena Pyth hanya menggunakan rentang 0-127 ASCII, ia dapat dikompresi dengan menggunakan pengkodean 7-bit daripada pengodean 8 bit. Dengan demikian, program di atas dapat dikemas menjadi 16 byte. Program yang dihasilkan adalah:

ꮎ�L����[
    ���4

hexdump:

0000000: eaae 8e9a 4cb9 edc6 c95b 0c9d 11ae 8534  ....L....[.....4

Penerjemah ditemukan di sini . Berikan input sebagai argumen baris perintah.

Halaman kode bahasa ini (Packed Pyth) adalah rentang 0-127 ASCII, dan setiap karakter diwakili dengan 7 bit, diisi pada bagian akhir. Dengan demikian, hexdump yang tidak dapat dibaca di atas mewakili:

u+QiR2smc2+0dt#.BM

Namun dalam 16 byte.

isaacg
sumber
6

05AB1E , 21 20 18 17 byte

,¸[Žrbvy0ì2äCʒ=1›

Cobalah online!

Penjelasan

,¸[Žrbvy0ì2äCʒ=1›   Argument n
,¸                  Print n and push n as array
  [Ž                Loop until stack is empty
    r               Reverse stack
     b              Convert elements in array to binary
      v             For each y in array
       y0ì2ä        Prepend '0' to y and split it into 2 elements
                    (the first element will take the additional character)
            C       Convert elements to decimal
             ʒ=1›   Keep only elements greater than 1, while printing each element
kalsowerus
sumber
@ JonathanAllan Yap memperbaikinya sekarang. Tampaknya menjadi masalah contoh-contoh tidak mencakup, terima kasih :)
kalsowerus
ʒ- Codepage baru ini ... Sejak kapan 05AB1E Jelly? Saya suka
Magic Gurita Guci
4

JavaScript (ES6), 99 byte

Ini terlihat agak terlalu lama. Mungkin ada cara yang lebih baik untuk mendapatkan urutan yang benar.

f=(n,p=(a=[],1),i=33-Math.clz32(n)>>1)=>(a[p]=n)>1?f(n>>i,p*=2)&&f(n&(1<<i)-1,p+1):a.filter(n=>1/n)

Demo

Arnauld
sumber
4

Jelly , 21 20 byte

-1 byte dengan menghapus rantai monadik dan kemudian berurusan dengan konsekuensi dari daftar kosong yang dikonversi dari biner menghasilkan 0 nanti.

ỊÐḟBUœs€2UḄF
WÇÐĿṖUF

Tautan monadik yang mengambil nomor dan mengembalikan daftar yang ditentukan.

Cobalah online!

Bagaimana?

ỊÐḟBUœs€2UḄF - Link 1, perform an iteration: list of numbers
 Ðḟ          - filter out if:
Ị            -   insignificant (absolute value <= 1 - hence any 0s or 1s)
   B         - convert to a binary list (vectorises)
    U        - upend (reverse each)
     œs€2    - split €ach into 2 equal chunks (the first half is longer if odd ...hence
         U   - upend (reverse each)         ...this upend and the previous one)
          Ḅ  - convert from binary list to number (vectorises, although when the filter
             -                                     removes everything a zero is yielded)
           F - flatten the resulting list of lists to a single list

WÇÐĿṖUF - Main link: number
W       - wrap in a list
  ÐĿ    - loop and collect results until no change occurs:
 Ç      -   call last link (1) as a monad
    Ṗ   - pop (remove the last element - a list containing a single zero which results
        -     from the effect of Ḅ when link 1's input only contained ones and zeros)
     U  - upend (put the iterations into the required order)
      F - flatten to yield a single list
Jonathan Allan
sumber
Bagaimana cara kerjanya?
caird coinheringaahing
@ Setan'sSon Saya menambahkan penjelasan sekarang
Jonathan Allan
Anda menambahkannya pada saat yang sama saya berkomentar: D
caird coinheringaahing
@ ØrjanJohansen keduanya memiliki biaya byte yang sama
Jonathan Allan
Oh, tidak melihat jawaban Pyth pertama, yang sudah menggunakan trik itu.
Ørjan Johansen
2

Java 7, 541 byte

import java.util.*;List l=new ArrayList(),L=new ArrayList();String c(int n){l.add(x(n));return a(n+" ",l,n);}String a(String r,List q,Integer n){boolean e=q.equals(l),E=q.equals(L);if(e)L.clear();else l.clear();for(String i:new ArrayList<String>(q)){int s=i.length()/2,a=n.parseInt(i.substring(0,s),2),z=n.parseInt(i.substring(s),2);r+=a+" "+z+" ";if(e&a>1)L.add(x(a));if(e&z>1)L.add(x(z));if(E&a>1)l.add(x(a));if(E&z>1)l.add(x(z));}if(e&L.size()>0)r=a(r,L,n);if(E&l.size()>0)r=a(r,l,n);return r;}String x(Integer n){return n.toString(n,2);}

Menjaga pesanan asli mengacaukan waktu saya, jika tidak, itu hanya akan menjadi loop mudah dan prinsip panggilan rekursif. Tetap saja, tantangan yang menyenangkan untuk mencari tahu sambil mempertahankan pesanan.

Penjelasan:

import java.util.*;                    // Required import for List and Array List

List l=new ArrayList(),L=new ArrayList(); 
                                       // Two Lists on class-level

String c(int n){                       // Method (1) with integer parameter and String return-type
  l.add(x(n));                         //  Start by adding the binary-String of the input integer to list `l`
  return a(n+" ",l,n);                 //  And let the magic begin in method `a` (2)
}                                      // End of method (1)

String a(String r,List q,Integer n){   // Method (2) with a bunch of parameters and String return-type
  boolean e=q.equals(l),E=q.equals(L); //  Determine which of the two class-level Lists the parameter-List is
  if(e)                                //  If it's `l`:
    L.clear();                         //   Empty `L`
  else                                 //  If it's `L` instead:
    l.clear();                         //   Empty `l`
  for(String i:new ArrayList<String>(q)){
                                       //  Loop over the input list (as new ArrayList to remove the reference)
    int s=i.length()/2,                //   Get the length of the current item in the list divided by 2
                                       //   NOTE: Java automatically floors on integer division,
                                       //   which is exactly what we want for the splitting of odd-length binary-Strings
    a=n.parseInt(i.substring(0,s),2),  //   Split the current binary-String item in halve, and convert the first halve to an integer
    z=n.parseInt(i.substring(s),2);    //   And do the same for the second halve
    r+=a+" "+z+" ";                    //   Append the result-String with these two integers
    if(e&a>1)                          //   If the parameter List is `l` and the first halve integer is not 0:
      L.add(x(a));                     //    Add this integer as binary-String to list `L`
    if(e&z>1)                          //   If the parameter List is `l` and the second halve integer is not 0:
      L.add(x(z));                     //    Add this integer as binary-String to List `L`
    if(E&a>1)                          //   If the parameter List is `L` and the first halve integer is not 0:
      l.add(x(a));                     //    Add this integer as binary-String to List `l`
    if(E&z>1)                          //   If the parameter List is `L` and the second halve integer is not 0:
      l.add(x(z));                     //    Add this integer as binary-String to List `l`
  }                                    //  End of loop
  if(e&L.size()>0)                     //  If the parameter List is `l` and List `L` now contains any items:
    r=a(r,L,n);                        //   Recursive call with List `L` as parameter
  if(E&l.size()>0)                     //  If the parameter List is `L` and List `l` now contains any items:
    r=a(r,l,n);                        //   Recursive call with List `l` as parameter
  return r;                            //  Return the result-String with the now appended numbers
}                                      // End of method (2)

String x(Integer n){                   // Method (3) with Integer parameter and String return-type
  return n.toString(n,2);              //  Convert the integer to its Binary-String
}                                      // End of method (3)

Kode uji:

Coba di sini.

import java.util.*;
class M{
  List l=new ArrayList(),L=new ArrayList();String c(int n){l.add(x(n));return a(n+" ",l,n);}String a(String r,List q,Integer n){boolean e=q.equals(l),E=q.equals(L);if(e)L.clear();else l.clear();for(String i:new ArrayList<String>(q)){int s=i.length()/2,a=n.parseInt(i.substring(0,s),2),z=n.parseInt(i.substring(s),2);r+=a+" "+z+" ";if(e&a>1)L.add(x(a));if(e&z>1)L.add(x(z));if(E&a>1)l.add(x(a));if(E&z>1)l.add(x(z));}if(e&L.size()>0)r=a(r,L,n);if(E&l.size()>0)r=a(r,l,n);return r;}String x(Integer n){return n.toString(n,2);}

  public static void main(String[] a){
    M m=new M();
    System.out.println(m.c(255));
    m.l.clear();
    m.L.clear();
    System.out.println(m.c(225));
    m.l.clear();
    m.L.clear();
    System.out.println(m.c(32));
  }
}

Keluaran:

255 15 15 3 3 3 3 1 1 1 1 1 1 1 1 
225 14 1 3 2 1 1 1 0 
32 4 0 1 0 
Kevin Cruijssen
sumber
2

Python 2 , 110 byte

l=[input()];i=1
while i:
 z=0
 for k in l[-i:]:
	if k>1:b=~-len(bin(k))/2;l+=[k>>b,k&2**b-1];z+=2
 i=z
print l

Cobalah online!

ovs
sumber
2

Retina , 142 byte

.+
$*
+`(1+)\1
${1}0
01
1
{`.+$
$&¶<$&>
+`;(\d*)>
>;<$1>
<.>

{`(\d)>
>$1
}`<(\d)
$1<
<>
;
\b0+\B

}`^;|;\B

¶
;
;;

1
01
+`10
011
0\B

1+
$.&

Cobalah online!

Neil
sumber
2

PHP, 132 Bytes

for($r=[$argn];""<$n=$r[+$i++];)$n<2?:[$r[]=bindec(substr($d=decbin($n),0,$p=strlen($d)/2)),$r[]=bindec(substr($d,$p))];print_r($r);

Cobalah online!

Jörg Hülsermann
sumber
Ini tidak berfungsi, menurut sistem Coba online di halaman ini,
Martin Barker
@ MartinBarker apa maksudmu?
Jörg Hülsermann
tio.run/nexus/… => Array( [0] => 225 [1] => 14 [2] => 1 [3] => 3 [4] => 2 [5] => 1 [6] => 1 [7] => 1 [8] => 0 )ketika tidak = 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1
Martin Barker
@ MartinBarker Anda harus mengubah input di Versi header. Ubah variabel $argnVariabel ini tersedia jika Anda menjalankan PHP dari baris perintah dengan -Ropsi. Berikut adalah contoh untuk input 255 Cobalah online!
Jörg Hülsermann
Itulah yang saya coba katakan tidak bekerja sesuai dengan sistem online coba. (ditautkan dalam pos)
Martin Barker
1

Ruby , 102 byte

f=->*a{a==[]?[]:a+=f[*a.map{|i|s='%b'%i;i>1?[s[0...h=s.size/2].to_i(2),s[h..-1].to_i(2)]:[]}.flatten]}

Cobalah online!

Nilai Tinta
sumber
1

Ruby , 98 byte

f=->*a{a==[]?a:a+=f[*a.flat_map{|i|s='%b'%i;i>1?[s[0...h=s.size/2].to_i(2),s[h..-1].to_i(2)]:[]}]}

Cobalah online!

Cukup optimalisasi dasar jawaban Value Ink : gunakan flat_map alih-alih peta ... ratakan, dan gunakan

a==[]?a dari pada a==[]?[]

Jenkar
sumber