Liczby całkowite gaussowskie są liczbami zespolonymi w postaci a+bi
gdzie a
i b
oba są liczbami całkowitymi. W bazie -1 + i wszystkie liczby całkowite Gaussa mogą być jednoznacznie reprezentowane za pomocą cyfr 0
i 1
bez potrzeby oznaczania znaku symbolem.
Na przykład 1100
w podstawie -1 + i reprezentuje liczbę dziesiętną 2, ponieważ
1*(-1+i)^3 + 1*(-1+i)^2 + 0*(-1+i)^1 + 0*(-1+i)^0
= (2+2i) + (-2i) + 0 + 0
= 2
Wejściami będą dwie liczby całkowite Gaussa w podstawie -1 + i reprezentowane za pomocą cyfr 01
. Może to mieć jedną z następujących postaci:
- Dwa oddzielne ciągi cyfr,
- Dwie liczby całkowite dziesiętne polegające na
01
reprezentowaniu liczb podstawowych -1 + i (np.1100
Dla 2 w bazie -1 + i), - Dwie binarne liczby całkowite reprezentujące liczby podstawowe -1 + i (np. Dziesiętne
12
lub0b1100
dla 2 w bazie -1 + i) - Pojedynczy ciąg oddzielający dwucyfrowe ciągi / binarne liczby całkowite przez pojedynczy niealfanumeryczny separator (np.
1100 1100
Lub12,12
dla 2 + 2)
Wyprowadza sumę dwóch liczb całkowitych Gaussa, również w bazie -1 + i, reprezentowanych za pomocą cyfr 01
(w jednym z formatów dozwolonych jako dane wejściowe, niekoniecznie ten sam wybór). Dane wyjściowe mogą zawierać skończoną liczbę zer wiodących.
Twoja funkcja lub program musi zakończyć się w ciągu 2 sekund dla wprowadzania co najwyżej 30 cyfr.
Dodatkowe wyjaśnienia
- Możesz założyć, że dane wejściowe nie zawierają zewnętrznych zer wiodących. W specjalnym przypadku 0 możesz wybrać jeden
0
lub pusty ciąg jako reprezentację.
Przypadki testowe
0, 0 => 0 # 0 + 0 = 0
0, 1 => 1 # 0 + 1 = 1
1, 1 => 1100 # 1 + 1 = 2
1100, 1100 => 111010000 # 2 + 2 = 4
1101, 1101 => 111011100 # 3 + 3 = 6
110111001100, 1110011011100 => 0 # 42 + (-42) = 0
11, 111 => 0 # i + (-i) = 0
11, 110 => 11101 # i + (-1-i) = -1
10101, 11011 => 10010 # (-3-2i) + (-2+3i) = (-5+i)
1010100101, 111101 => 1110100000100 # (-19+2i) + (3-4i) = (-16-2i)
Dłuższe przypadki testowe:
11011011010110101110010001001, 111100010100101001001010010101 => 0
111111111111111111111111111111, 111111111111111111111111111111 => 100100100100100100100100100100
101101110111011101110111011101, 101101110111011101110111011101 => 11101001010001000100010001000100011100
100100010101001101010110101010, 100010011101001011111110101000 => 110000110010101100001100111100010
źródło
-1+i
nai-1
w tytule.Odpowiedzi:
Python 2,
98979184 bajtówRobi to we / wy dziesiętnie. Liczby całkowite muszą być oddzielone znakiem niealfanumerycznym
+
.Dzięki @xnor za grę w golfa z 2 bajtów!
Wypróbuj na Ideone .
Jak to działa
W Arytmetyki w złożonych bazach autor pokazuje, jak dodawać i pomnożyć liczby zespolone w bazach postaci -n + i .
Dla podstawy -1 + i dodawanie odbywa się podobnie do zwykłego dodawania binarnego z przeniesieniem, z dwiema różnicami:
Zamiast przenosić 1 do następnej wyższej pozycji, przenosimy 110 do następnych trzech.
Przenoszenie cyfr może się rozprzestrzeniać w nieskończoność. Jednak bez zer wiodących suma a + b ma najwyżej osiem cyfr więcej niż maksimum a i b .
Postępujemy następująco.
Najpierw dodamy A i B tak, jakby były ich cyfr po przecinku.
W przypadku a = 10101 i B = 11011 , daje 21112 .
Następnie tworzymy nowy numer, zamieniając cyfry większe niż 1 na 1 , inne na 0 . 1
Dla sumy 21112 daje to 10001 .
Dla każdej cyfry większej niż 1 musimy odjąć 2 od tej cyfry i przenieść 110 do następnych trzech wyższych pozycji. Ponieważ 1098 = 10 * 110 - 2 , możemy to osiągnąć, mnożąc wynik z kroku 2 przez 1098 , a następnie dodając ten produkt do sumy. 2)
Dla sumy 21112 daje to 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210 .
Powtarzamy kroki 2 i 3 łącznie d * 8 razy, gdzie d jest liczbą cyfr a + b . 3)
Dla sumy początkowej 21112 wyniki są następujące
Bierzemy końcową sumę modulo 10 d + 8 , odrzucając wszystkie oprócz ostatnich d + 8 cyfr.
W przypadku kwoty początkowej 21112 końcowy wynik to 10010 .
1 Osiąga się to dzięki tłumaczeniu . Powtarzanie ciągu 0011 64 razy tworzy jedną linię powtórzenia z sekwencją znaków ASCII 0123 , osiągając pożądaną zamianę.
2 Zauważ, że cyfry tej sumy nie mogą przekraczać 3 (wartość początkowa 1 plus dwa 1 -te z przeniesień).
3 Dzieje się tak, gdy działa dla d = 1 , a d * 8> d + 8 w przeciwnym razie. Kod może powtórzyć kroki (d + 1) * 8 razy, ponieważ s ma końcowe L, jeśli s jest długą liczbą całkowitą.
źródło
input()
oczekuje? (Dostaję,21112
gdy wprowadzę10101, 11011
.)d+8
a nie powiedzmyd+9
? W jaki sposób????Pyth, 34 bajty
Wypróbuj online: pakiet demonstracyjny lub testowy (zajmuje to sporo czasu). Powinien jednak łatwo spełniać ograniczenia czasowe, ponieważ kompilator online jest dość powolny w porównaniu z normalnym (offline) kompilatorem.
Wyjaśnienie:
Mój algorytm jest w zasadzie implementacją dodawania z przenoszeniem. Ale zamiast nosić
1
muszę nosić110
(1100
w bazie-1+i
jest to samo, co2
w bazie-1+i
). Działa to głównie dobrze, ale możesz utknąć w nieskończonej pętli drukującej zera. Na przykład, jeśli dodajesz za1
pomocą11
i obecnie masz carry110
. Więc w zasadzie dodaję, aż utknę w pętli, a potem przestanę. Myślę, że pętla, w której pętla zawsze będzie drukować zera, dlatego powinna być w porządku.źródło
Python 2,
6967 bajtówI / O odbywa się przy użyciu liczb całkowitych bazowych 2.
-2 dzięki @Dennis.
źródło
a*a+b*b^58==0
kiedya
ib
są odwrócone? Jak to działa?a*a+b*b==58
gdy jeden z nich ma 3, a drugi 7(3,7)
to jedyna para, która daje cykl i potrzebuje specjalnej obudowy. Jeśli to prawda, musisz tylko sprawdzić(a,b)==(3,7)
w tej kolejności, ponieważ(7,3)
powtarza się(3,7)
, i może jest na to krótsze wyrażenie.^
jest XOR, nie potęgowanie, lub (b) XOR ma niższy priorytet niż+
.Siatkówka , 100 bajtów
Spowoduje to oddzielenie danych wejściowych przecinkiem. Wyjście zawsze zaczyna się od trzech wiodących zer.
Wypróbuj online!
Naprawdę zastanawiam się, czy istnieje krótsze rozwiązanie dla pierwszego etapu ...
źródło
Galaretka,
292826242120 bajtówRobi to we / wy dziesiętnie. Liczby całkowite muszą być oddzielone znakiem niealfanumerycznym
+
.Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .
tło
W Arytmetyki w złożonych bazach autor pokazuje, jak dodawać i pomnożyć liczby zespolone w bazach postaci -n + i .
Dla podstawy -1 + i dodawanie odbywa się podobnie do zwykłego dodawania binarnego z przeniesieniem, z dwiema różnicami:
Zamiast przenosić 1 do następnej wyższej pozycji, przenosimy 110 do następnych trzech.
Przenoszenie cyfr może się rozprzestrzeniać w nieskończoność. Jednak bez zer wiodących suma a + b ma najwyżej osiem cyfr więcej niż maksimum a i b .
Postępujemy następująco.
Najpierw dodamy A i B tak, jakby były ich cyfr po przecinku.
W przypadku a = 10101 i B = 11011 , daje 21112 .
Dla każdej cyfry większej niż 1 musimy odjąć 2 od tej cyfry i przenieść 110 do następnych trzech wyższych pozycji. Można to osiągnąć przez przeprowadzenie każdej cyfry dziesiętnej binarnego powstałe tablice binarne z podstawy 1100, do liczby całkowitej, i interpretowania otrzymanej listy 0 „s, 1 ” S, 1100 -tych i 1101 -tych, jako Niekanoniczne 10 numer. 1
Dla sumy 21112 daje to 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210 .
Powtarzamy kroki 2 łącznie d + 8 razy, gdzie d jest liczbą cyfr a + b .
Dla sumy początkowej 21112 wyniki są następujące
Odrzucamy wszystkie oprócz ostatnich d + 8 cyfr z wyniku końcowego. Osiąga się to poprzez odrzucenie wszystkiego po ostatnich 2 . 2)
W przypadku kwoty początkowej 21112 końcowy wynik to 10010 .
Jak to działa
1 Zauważ, że cyfry tej sumy nie mogą przekraczać 3 (wartość początkowa 1 plus dwa 1 -te z przeniesień).
2 Działa, ponieważ ostatnia cyfra, która anuluje, nie może być 3 .
źródło
Python 3, 289 bajtów
Dokonuje cyfrowego dodawania od najmniej znaczącej cyfry (innymi słowy dokładnie ten sam algorytm, którego nauczyłeś się w szkole podstawowej). Różnice polegają na tym, że (a) ma postać binarną, a nie dziesiętną, więc przenosisz za każdym razem, gdy cyfra ma 2 lub więcej, i (b)
1 + 1 = 1100
nie10
.W rzeczywistości należy również zauważyć, że
11 + 111 = 0
w przeciwnym razie sumy, które powinny być zerowe, nigdy się nie zakończą.Z pewnością więcej golfa jest możliwe.
źródło
Siatkówka,
157151134133124 124123 bajtów1 bajt off dzięki Martinowi Büttnerowi.
Wypróbuj online!
Konwertuje na unary, a następnie powtórz następujące zamiany (pokazane tutaj po przecinku):
Zasadniczo, gdy jest większy niż dwa: zabierz dwa, nie dodawaj nic do poprzedniej cyfry, dodaj jeden do poprzedniej cyfry, a następnie dodaj jeden do poprzedniej cyfry.
W pseudokodzie:
Jednolite wdrożenie:
Każda cyfra (np.
3
) Jest pokazana jako liczbax
s (np.xxx
), A następnie poprzedzona znakiem0
.Na przykład
1234
byłby wyrażony jako0x0xx0xxx0xxxx
.Pozostawia to
0
bez zmian, jak101
by to wyraził0x00x
.Ponieważ początkowo i na końcu jest tylko
0
i1
, konwersja może być łatwo wykonana przez1->0x
i0x->1
.Kliknij tutaj, aby zobaczyć każdy krok .
źródło
JavaScript (ES6),
146126 bajtówg
przekształca Gaussa całkowitą (rzeczywista i urojona) do podstawyi-1
, ar
ii
przetwarza podstawyi-1
całkowitą w całkowitej Gaussa (części rzeczywistych i urojonych, odpowiednio). Kiedy konwersje są na miejscu, muszę tylko wykonać arytmetykę.Edycja: Zapisano 20 bajtów, obliczając osobno rzeczywistą i urojoną część.
źródło
C ++ 416 bajtów plus
#include <vector>\n#include <algorithm>\n
(kolejne 40)lub z większą ilością białych znaków:
Ledwo grał w golfa. Pobiera dane wejściowe jako wektor liczb całkowitych i zwraca wektor liczb całkowitych.
Przykład na żywo .
źródło