Zwykle rozkładamy liczbę na cyfry binarne, przypisując jej potęgę 2, o współczynniku 0lub 1dla każdego terminu:

25 = 1*16 + 1*8 + 0*4 + 0*2 + 1*1

Wybór 0i 1... nie jest bardzo binarny. Dokonamy prawdziwej ekspansji binarnej poprzez rozszerzenie o potęgach 2, ale o współczynniku 1lub -1zamiast tego:

25 = 1*16 + 1*8 + 1*4 - 1*2 - 1*1

Teraz wygląda to na binarne.

Biorąc pod uwagę dowolną liczbę dodatnią, stwierdzenie, że:

• Każda liczba nieparzysta ma nieskończenie wiele prawdziwych rozszerzeń binarnych
• Każda liczba parzysta nie ma prawdziwych rozszerzeń binarnych

Dlatego, aby prawdziwa interpretacja binarna była dobrze zdefiniowana, wymagamy, aby była ona najmniejsza , tj. Najkrótsza.

Biorąc pod uwagę każdą dodatnią, nieparzystą liczbę całkowitą n, zwróć jej prawdziwe rozwinięcie binarne, od najbardziej znaczącej cyfry do najmniej znaczącej cyfry (lub w odwrotnej kolejności).

Zasady:

• Jak to jest golf-golf, powinieneś dążyć do tego, aby uzyskać jak najkrótszą liczbę bajtów. Wbudowane są dozwolone.
• Dowolne dane wyjściowe, które mogą przedstawiać i wyświetlać współczynniki, są dopuszczalne: tablica, ciąg współczynników z separatorami itp.
• Obowiązują standardowe luki w grze w golfa.
• Twój program powinien działać dla wartości w standardowym rozmiarze całkowitym twojego języka.

Przypadki testowe

25 -> [1,1,1,-1,-1]
47 -> [1,1,-1,1,1,1]
1 -> [1]
3 -> [1,1]
1234567 -> [1,1,-1,-1,1,-1,1,1,-1,1,-1,1,1,-1,1,-1,-1,-1,-1,1,1]

Japt , 6 bajtów

¤é r0J

Wypróbuj online!

Wyjaśnienie:

¤é r0J  // Test input:                  25
¤       // Binary the input:            11001
 é      // Rotate 1 chars to the right: 11100
   r0J  // Replace 0s with -1:          111-1-1

Pyth ,  12  11 bajtów

|R_1.>jQ2 1

Wypróbuj tutaj!

W jaki sposób?

| R_1.> JQ2 1 Pełny program.

      jQ2 Konwertuj dane wejściowe na listę binarną.
     .> 1 Cyklicznie obracaj powyższą listę o 1 miejsce w prawo.
| R_1 Zamień 0 na -1.
               Wyjściowy wynik.

Po pierwsze, zauważamy, że zadaniem jest po prostu „zastąpić 0s w zapisie binarnym -1s i przesunąć w prawo o 1 miejsce”. - Właśnie to powinniśmy zrobić! Konwersja binarna daje nam listę 0s i 1s. Wszystko trzeba zrobić tutaj jest znalezienie Golfy sposób przekonwertować 0do -1. Operator bitowy |(bitowy OR) jest naszym przyjacielem. Mapa nad reprezentacją binarną przesunięta o |i -1. Jeśli bieżący numer to 0, zostanie przekonwertowany na -1.

Perl 6

Wersja łańcuchowa, 31 bajtów

1~(*+>1).base(2).subst(0,-1,:g)

Wypróbuj online!

Wersja listy, 36 bajtów

{map * *2-1,1,|($_+>1).base(2).comb}

Wypróbuj online!

JavaScript (ES6), 35 34 bajtów

f=n=>n?[...f(n>>=1),!n|n%2||-1]:[]

Testowy fragment kodu

let f=n=>n?[...f(n>>=1),!n|n%2||-1]:[];

[25, 47, 1, 3, 1234567].map(x => console.log(x + ":", JSON.stringify(f(x))))

Perl 6 , 72 bajtów

Z pewnością jest lepszy sposób, ale to właśnie mam ...

->$a {grep {$a==[+] @^a.reverse Z+< ^∞},[X] (1,-1)xx $a.base(2).chars}

Wypróbuj online!

Objaśnienie : Jest to funkcja, która pobiera jeden argument ( ->$a). Najpierw otrzymujemy wymaganą liczbę współczynników ( $a.base(2).chars= liczbę znaków w reprezentacji podstawy 2), a następnie tworzymy iloczyn kartezjański ( X) z wielu par (1,-1). ( [X]Oznacza: zmniejsz poniższą listę za pomocą X.) Otrzymujemy więc listę wszystkich możliwych kombinacji 1s i -1s. Następnie filtrujemy ( grep) tylko listy, które kodują podaną liczbę $a. Jest tylko jedna, więc otrzymujemy listę jednej listy ze współczynnikami.

Blok grep robi to: bierze argument jako list ( @^a), odwraca go i zamyka z nieskończoną listą 0,1,2,...za pomocą operatora „left bit shift” +<. Zipowanie zatrzymuje się, gdy tylko krótsza lista się wyczerpie (dla nas dobre!) Następnie sumujemy wszystkie wyniki i porównujemy je z podaną liczbą. Musieliśmy użyć, .reverseponieważ PO wymaga, aby współczynniki były w kolejności od najbardziej znaczącej do najmniej znaczącej.

Galaretka , 5 bajtów

Bṙ-o-

Wypróbuj online!

05AB1E , 6 5 bajtów

bÁ0®:

Wypróbuj online!

J, 11 bajtów

1-~2*_1|.#:

Wypróbuj online!

Dzięki @JosiahWinslow za algorytm.

Masz jakieś przemyślenia na temat skrócenia konwersji? !.Myślę o użyciu -fit (nvm, to tylko zmienia tolerancję konwersji).

Użycie {-take jest dłuższe o 1 znak.

_1 1{~_1|.#:

Java 8, 101 bajtów

n->{String s=n.toString(n,2);return(s.charAt(s.length()-1)+s.replaceAll(".$","")).replace("0","-1");}

Port odpowiedzi Japt @Oliver , z kilkoma dodatkowymi bajtami ..;)

Można zdecydowanie zagrać w golfa, stosując podejście matematyczne zamiast tego podejścia strunowego.

Wyjaśnienie:

Wypróbuj tutaj.

n->{                             // Method with Integer parameter and String return-type
  String s=n.toString(n,2);      //  Convert the Integer to a binary String
  return(s.charAt(s.length()-1)  //  Get the last character of the binary String
    +s.replaceAll(".$","")       //   + everything except the last character
   ).replace("0","-1");          //  Then replace all zeroes with -1, and return the result
}                                // End of method

R , 90 88 46 bajtów

function(n)c((n%/%2^(0:log2(n))%%2)[-1],1)*2-1

Wypróbuj online!

Implementuje algorytm Olivera , ale zwraca cyfry w odwrotnej kolejności. Ponieważ gwarantujemy, że nnigdy się nie wyrówna, zawsze jest najmniej znaczący bit (pierwszy) 1, więc usuwamy go i dopisujemy 1do końca, aby symulować obrót w R. Dzięki Shaggy za nakłonienie mnie do poprawienia matematyki .

Po prostu rev( ) wywołań funkcji w stopce powinno zwrócić wartości w tej samej kolejności.

oryginalna odpowiedź, 88 bajtów:

function(n,b=2^(0:log2(n)))(m=t(t(expand.grid(rep(list(c(-1,1)),sum(b|1))))))[m%*%b==n,]

Funkcja anonimowa; zwraca wartości w odwrotnej kolejności z dołączonymi nazwami kolumn.

Wypróbuj online!

Wyjaśnienie:

function(n){
 b <- 2^(0:log2(n))         # powers of 2 less than n
 m <- expand.grid(rep(list(c(-1,1)),sum(b|1))) # all combinations of -1,1 at each position in b, as data frame
 m <- t(t(m))               # convert to matrix
 idx <- m%*%b==n            # rows where the matrix product is `n`
 m[idx,]                    # return those rows
}

Perl 5 , 30 bajtów

Kod 29 bajtów, 1 bajt na -pprzełącznik.

$_=sprintf'1%b',$_/2;s/0/-1/g

Wypróbuj online!

CJam, 12 bajtów

Port mojej odpowiedzi w Golfscript.

qi2b{_+(}%)\

Rubinowy , 44 37 33 32 bajty

->n{("1%b"%n).chop.gsub ?0,"-1"}

Wypróbuj online!

Golfscript, 14 13 14 bajtów

-1 bajt, ponieważ zapomniałem o %istnieniu. +1 bajt, ponieważ zapomniałem również, że jest to ciąg znaków.

~2base{.+(}%)\