Otrzymasz numer x, gdzie 0 <= x <= 2^32 - 1.

Powinieneś wypisać listę liczb dziesiętnych po rekurencyjnym podziale w formacie binarnym.

Przykłady:

Przykład 1:

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

Obecna lista jest po prostu 255.

Binarna reprezentacja 255to 1111 1111. Rozdzielając go, otrzymujemy 1111i 1111, które w systemie dziesiętnym są 15i 15.

Dodajemy je do listy, więc będziemy mieć 255 15 15.

Teraz liczby 15i 15będą służyć jako dane wejściowe i liczby te zostaną podzielone.

Robi to ponownie, mamy ( 3 3z obu 15s) 255 15 15 3 3 3 3.

Kontynuując logikę, ostateczna lista będzie 255 15 15 3 3 3 3 1 1 1 1 1 1 1 1. A ponieważ 1nie można go już podzielić, wyjście zatrzymuje się.

Przykład 2:

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

Lista początkowa to 225.

Binarna reprezentacja 225to 1110 0001. Rozdzielając go, otrzymujemy 1110i 0001, które w systemie dziesiętnym są 14i 1.

Dodając je do listy, otrzymujemy 225 14 1.

Teraz liczby 14i 1będą służyć jako dane wejściowe i liczby te zostaną podzielone.

Ponieważ 1nie można go podzielić, wynik będzie 225 14 1 3 2.

Przykład 3:

32 -> 32 4 0 1 0

Warunki :

1. Jeśli liczba cyfr binarnych jest nieparzysta, pierwsza liczba będzie miała jedną cyfrę binarną mniejszą niż następna. Przykład 20 (10100)zostanie podzielony jako 10i 100, przy czym wyjście dziesiętne to 2i 4.
2. Obowiązują standardowe zasady dotyczące luk.
3. 0si 1nie rozprzestrzeniają się dalej.
4. Awaria programu przy próbie wyświetlenia zbyt wielu liczb jest prawidłowym warunkiem wyjścia.

Pyth, 18 bajtów

u+QiR2smc2+0dt#.BM

Zestaw testowy

Ten kod robi coś bardzo skomplikowanego i sprytnego z uoperatorem punktu stałego Pytha.

Ciało funkcji, które jest wszystkim innym niż u, jest dość proste:

+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

Ten kod usuwa zera i jedynki, dzieli każdą liczbę i dodaje dane wejściowe z przodu.

u uruchomi tę funkcję na podstawie wcześniejszego wyniku funkcji, aż wynik przestanie się zmieniać.

Jaka jest wartość początkowa u? To sprytna część: kod nie określa, jakiej wartości użyć, więc domyślnie jest to wejście. Ale dane wejściowe nie są listą liczb - to liczba. Pyth niejawnie wymusza liczbę w czasie pierwszej pięści przez pętlę do zakresu liczby - [0, 1, ..., Q-1]. To nie przypomina niczego, co chcemy uzyskać. Na szczęście uznajdzie poprawny wynik niezależnie od tego, jakie jest początkowe wejście - pożądane wyjście jest jedynym stałym punktem funkcji, a powtarzająca się aplikacja zawsze go osiągnie.

Spójrzmy na wartości pośrednie programu z danymi wejściowymi 7. Podkreśliłem prefiks wyniku, który z pewnością jest poprawny, bez względu na początkowe dane wejściowe:

1. 7(Niejawnie [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]

Który jest wynikiem.

Pakiety Pyth, 16 bajtów

Zauważ, że ponieważ Pyth używa tylko zakresu 0-127 ASCII, można go skompresować przy użyciu kodowania 7-bitowego zamiast 8-bitowego. Tak więc powyższy program można spakować do 16 bajtów. Wynikowy program to:

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

zrzut heksowy:

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

Tłumacz znajduje się tutaj . Podaj dane wejściowe jako argument wiersza poleceń.

Strona kodowa tego języka (Packed Pyth) to zakres ASCII 0-127, a każdy znak jest reprezentowany przez 7 bitów, wypełnionych na końcu. Tak więc powyższy nieczytelny zrzut heksowy reprezentuje:

u+QiR2smc2+0dt#.BM

Ale w 16 bajtach.

05AB1E , 21 20 18 17 bajtów

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

Wypróbuj online!

Wyjaśnienie

,¸[Ž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

JavaScript (ES6), 99 bajtów

To wygląda trochę za długo. Może być lepszy sposób na uzyskanie prawidłowej kolejności.

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)

Próbny

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)

console.log(JSON.stringify(f(255)))
console.log(JSON.stringify(f(225)))
console.log(JSON.stringify(f(32)))

Galaretka , 21 20 bajtów

-1 bajt poprzez usunięcie łańcucha monadycznego, a następnie radzenie sobie z konsekwencją konwersji pustej listy z binarnego zwracania 0 później.

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

Łącze monadyczne pobierające numer i zwracające określoną listę.

Wypróbuj online!

W jaki sposób?

ỊÐḟ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

Java 7, 541 bajtów

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);}

Utrzymanie oryginalnego porządku doprowadziło mnie do szału, w przeciwnym razie byłaby to prosta pętla i zasada rekurencyjnego wywoływania. Mimo to fajne wyzwanie, aby dowiedzieć się, zachowując porządek.

Wyjaśnienie:

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)

Kod testowy:

Wypróbuj tutaj.

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));
  }
}

Wynik:

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 

Python 2 , 110 bajtów

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

Wypróbuj online!

Siatkówka , 142 bajty

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

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

}`^;|;\B

¶
;
;;

1
01
+`10
011
0\B

1+
$.&

Wypróbuj online!

PHP, 132 bajtów

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);

Wypróbuj online!

Rubin , 102 bajty

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]}

Wypróbuj online!

Rubinowy , 98 bajtów

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)]:[]}]}

Wypróbuj online!

Po prostu podstawowa optymalizacja odpowiedzi Value Ink : użyj flat_map zamiast map ... spłaszcz i użyj

a==[]?a zamiast a==[]?[]