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]

— Woal
źródło

Powiązane, ale zupełnie inne.

— Giuseppe,

4

Prosty algorytm: Konwertuj na bazę 2, zamień 0 na -1, umieść LSD z przodu.

— Josiah Winslow

Voile: Nie tłumaczyłem głosów negatywnych, po prostu nakreśliłem algorytm dla ludzi, którzy mają polecenia konwersji bazy w swoim języku.

— Josiah Winslow,

Skoro tak bardzo chcesz być naprawdę binarny, czy możemy zwrócić tę wartość jako spakowane bity ze zwykłą wartością wartość-miejsce, ale nową interpretacją dwóch stanów? tzn. elektrycznie jest to po prostu wysokie lub niskie napięcie (lub cokolwiek innego) i to nie moja wina, że standardowe debuggery drukują 0zamiast stanu -1niskiego napięcia. Dzwoniący odbierający bity wie, co mają na myśli. (To wciąż nie jest trywialne ćwiczenie polegające na manipulowaniu bitami, ponieważ obrót w prawo działa tylko wtedy, gdy ma 32 znaczące bity. Np. Liczba 5-bitowa wymaga szerokości obrotu 5).

— Peter Cordes

Czy dane wyjściowe muszą zawierać separatory? Czy 111-1-1ważne jest wyjście dla 25?

— Oliver

7

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

— Oliver
źródło

1

Ach, obrót; że dlatego, że nie działa dla mnie.

— Kudłaty

2

Obracać się??? dagnabbit.

— Giuseppe,

3

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.

— Pan Xcoder
źródło

Nie sądzę, że jest lepszy sposób. ;)

— Josiah Winslow,

@JosiahWinslow I do ... Próbuję to znaleźć

— Mr. Xcoder

Hm? Algorytm wydaje się optymalny, może dlatego, że nie znam Pytha.

— Josiah Winslow,

@JosiahWinslow Znalazłem lepszy sposób. Lepszy sposób syntaktyczny, a nie lepszy algorytm.

— Pan Xcoder,

@ Mr.Xcoder A teraz naprawdę nie ma dla mnie żadnej.

— Erik the Outgolfer,

3

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!

— nwellnhof
źródło

3

JavaScript (ES6), 35 34 bajtów

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

Testowy fragment kodu

Pokaż 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))))

Rozwiń fragment kodu

— ETHprodukcje
źródło

2

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.

— Ramillies
źródło

1

Galaretka , 5 bajtów

Bṙ-o-

Wypróbuj online!

— Erik the Outgolfer
źródło

1

05AB1E , 6 5 bajtów

bÁ0®:

Wypróbuj online!

— Okx
źródło

D<może być ®( ®jest domyślny -1).

— Erik the Outgolfer

@EriktheOutgolfer Thanks! Nie zdawałem sobie z tego sprawy.

— Okx,

1

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|.#:

— kapusta
źródło

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

— Kevin Cruijssen
źródło

1

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
}

— Giuseppe
źródło

Nie uważałbym tego wyniku za prawidłowy; zasugeruj poproszenie autora wyzwania o potwierdzenie.

— Kudłaty

@Shaggy odwrócona kolejność jest wyraźnie dozwolona: from the most significant digit to the least significant digit (or in reversed order).dlatego powinno to być całkowicie dopuszczalne.

— Giuseppe,

1

Odwrócona kolejność , nie odwrócone znaki. Oznacza to 25, że na przykład prawidłowym wyjściem byłoby [1,1,1,-1,-1]lub [-1,-1,1,1,1].

— Shaggy

1

@Shaggy ah, masz rację, po prostu źle zrobiłem matematykę! powinno być 2*bits - 1zamiast 1-2*bits. Dziękuję Ci.

— Giuseppe,

1

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!

— nwellnhof
źródło

0

CJam, 12 bajtów

Port mojej odpowiedzi w Golfscript.

qi2b{_+(}%)\

— Josiah Winslow
źródło

0

Rubinowy , 44 37 33 32 bajty

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

Wypróbuj online!

— GB
źródło

0

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{.+(}%)\

— Josiah Winslow
źródło

1

Jeśli zamierzasz założyć, że dane wejściowe są liczbą całkowitą, powinieneś owinąć kod, {}aby był blokiem. Pełne programy mogą pobierać dane tylko jako ciągi znaków.

— Peter Taylor

Co? Chodzi mi o to, że liczba jest wypychana jako liczba całkowita, zamiast ciągu zawierającego liczbę.

— Josiah Winslow,

W takim przypadku twoja odpowiedź nie jest pełnym programem, a więc musi być „funkcją” , aw przypadku GolfScript blokiem. Dlatego {2base{.+(}%\}dotyczy 15 bajtów. Podobnie twoja odpowiedź na CJam.

— Peter Taylor,

To jest pełny program. Dane wejściowe w Golfscript są domyślnie wypychane na stos na początku programu, a dane wejściowe w CJam są określane przed wykonaniem i dostępne za pomocą polecenia q.

— Josiah Winslow,

Mam pewną znajomość GolfScript . ( I CJam ). Jeśli chcesz twierdzić, że jest to pełny program, musisz go poprzedzić ~.

— Peter Taylor,

Binarne rozszerzenie binarne

Zasady:

Przypadki testowe

Japt , 6 bajtów

Wyjaśnienie:

Pyth , 12 11 bajtów

W jaki sposób?

Perl 6

JavaScript (ES6), 35 34 bajtów

Testowy fragment kodu

Perl 6 , 72 bajtów

Galaretka , 5 bajtów

05AB1E , 6 5 bajtów

J, 11 bajtów

Java 8, 101 bajtów

R , 90 88 46 bajtów

oryginalna odpowiedź, 88 bajtów:

Perl 5 , 30 bajtów

CJam, 12 bajtów

Rubinowy , 44 37 33 32 bajty

Golfscript, 14 13 14 bajtów