Bilangan bulat gaussian adalah bilangan kompleks dari bentuk di a+bi
mana a
dan b
keduanya bilangan bulat. Dalam basis -1 + i, semua bilangan bulat Gaussian dapat diwakili secara unik menggunakan digit 0
dan 1
, tanpa perlu simbol untuk menunjukkan tanda.
Misalnya, 1100
dalam basis -1 + i mewakili angka desimal 2, karena
1*(-1+i)^3 + 1*(-1+i)^2 + 0*(-1+i)^1 + 0*(-1+i)^0
= (2+2i) + (-2i) + 0 + 0
= 2
Input akan berupa dua bilangan bulat Gaussian di basis -1 + i yang diwakili menggunakan digit 01
. Ini dapat mengambil salah satu bentuk berikut:
- Dua string angka yang terpisah,
- Dua bilangan bulat desimal yang terdiri dari
01
mewakili basa -1 + i angka (misalnya1100
untuk 2 di basis -1 + i), - Dua bilangan bulat biner yang mewakili angka dasar -1 + i (mis. Desimal
12
atau0b1100
untuk 2 pada basis -1 + i) - Sebuah string tunggal yang memisahkan dua digit string / integer biner oleh pemisah non-alfanumerik tunggal (misalnya
1100 1100
atau12,12
untuk 2 + 2)
Keluarkan jumlah dari dua bilangan bulat Gaussian, juga dalam basis -1 + i dan diwakili menggunakan digit 01
(dalam salah satu format yang diizinkan sebagai input, tidak harus pilihan yang sama). Outputnya diizinkan mengandung angka nol terdepan yang terbatas.
Fungsi atau program Anda harus berakhir dalam 2 detik untuk input paling banyak masing-masing 30 digit.
Klarifikasi tambahan
- Anda dapat berasumsi bahwa input tidak mengandung nol terkemuka di luar. Untuk kasus khusus 0, Anda dapat memilih salah satu
0
atau string kosong sebagai representasi.
Uji kasus
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)
Kasus uji yang lebih panjang:
11011011010110101110010001001, 111100010100101001001010010101 => 0
111111111111111111111111111111, 111111111111111111111111111111 => 100100100100100100100100100100
101101110111011101110111011101, 101101110111011101110111011101 => 11101001010001000100010001000100011100
100100010101001101010110101010, 100010011101001011111110101000 => 110000110010101100001100111100010
sumber
-1+i
kei-1
dalam judul.Jawaban:
Python 2,
98979184 byteIni saya / O dalam desimal. Bilangan bulat harus dipisahkan oleh karakter non-alfanumerik
+
.Terima kasih kepada @xnor karena bermain golf 2 byte!
Cobalah di Ideone .
Bagaimana itu bekerja
Dalam Aritmatika dalam Basa Kompleks , penulis menunjukkan cara menambahkan dan mengalikan bilangan kompleks dalam basis -n + i .
Untuk basis -1 + i , penambahan dilakukan mirip dengan penambahan biner biasa dengan carry, dengan dua perbedaan:
Alih-alih membawa 1 ke posisi lebih tinggi berikutnya, kami membawa 110 ke tiga berikutnya.
Membawa angka dapat diperbanyak tanpa batas. Namun, tanpa angka nol di depan, jumlah a + b memiliki paling banyak delapan digit lebih dari maksimum a dan b .
Kami melanjutkan sebagai berikut.
Pertama, kita menambahkan a dan b seolah-olah digit mereka adalah angka desimal.
Untuk a = 10101 dan b = 11011 , ini memberikan 21112 .
Selanjutnya, kami membentuk angka baru dengan mengganti angka yang lebih besar dari 1 dengan 1 , yang lain dengan 0 . 1
Untuk jumlah 21112 , ini memberi 10001 .
Untuk setiap digit yang lebih besar dari 1 , kita harus mengurangi 2 dari angka itu dan membawa 110 ke tiga posisi berikutnya yang lebih tinggi. Karena 1098 = 10 * 110 - 2 , kita dapat mencapai ini dengan mengalikan hasil dari langkah 2 dengan 1098 , lalu menambahkan produk tersebut ke jumlah. 2
Untuk jumlah 21112 , ini memberi 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210 .
Kami mengulangi langkah 2 dan 3 total d * 8 kali, di mana d adalah jumlah digit a + b . 3
Untuk jumlah awal 21112 , hasilnya adalah
Kami mengambil jumlah akhir modulo 10 d + 8 , membuang semua kecuali d + 8 digit terakhir.
Untuk jumlah awal 21112 , hasil akhirnya adalah 10010 .
1 Ini dicapai dengan terjemahan . Mengulang string 0011 64 kali membuat satu pengulangan berbaris dengan urutan karakter ASCII 0123 , mencapai penggantian yang diinginkan.
2 Perhatikan bahwa angka-angka dari jumlah ini tidak dapat melebihi 3 (nilai awal 1 ditambah dua 1 dari carry).
3 Ini berlaku untuk d = 1 , dan d * 8> d + 8 sebaliknya. Kode dapat mengulangi langkah-langkah (d + 1) * 8 kali, karena s memiliki trailing L jika s adalah bilangan bulat panjang .
sumber
input()
diharapkan? (Saya dapatkan21112
ketika saya input10101, 11011
.)d+8
dan tidak, katakanlahd+9
,? Bagaimana????Pyth, 34 byte
Cobalah online: Demonstrasi atau Test Suite (membutuhkan waktu cukup lama). Ini harus memenuhi batasan waktu dengan mudah, karena kompiler online cukup lambat dibandingkan dengan kompiler normal (offline).
Penjelasan:
Algoritma saya pada dasarnya adalah implementasi dari penambahan dengan membawa. Tapi alih-alih membawa
1
, saya harus membawa110
(1100
di pangkalan-1+i
sama dengan2
di pangkalan-1+i
). Ini berfungsi sebagian besar baik-baik saja, tetapi Anda bisa terjebak dalam nol nol pencetakan lingkaran tak terbatas. Misalnya jika Anda menambahkan1
dengan11
dan saat ini memiliki carry110
. Jadi saya pada dasarnya menambahkan sampai saya terjebak dalam satu lingkaran dan kemudian berhenti. Saya berpikir bahwa loop yang loop akan selalu mencetak nol dan karena itu ini harus baik-baik saja.sumber
Python 2,
6967 byteI / O dilakukan dengan basis 2 integer.
-2 terima kasih @Dennis.
sumber
a*a+b*b^58==0
kapana
danb
apakah itu invers? Bagaimana cara kerjanya?a*a+b*b==58
ketika salah satu dari mereka adalah 3 dan yang lainnya adalah 7.(3,7)
hanya pasangan yang memberikan siklus dan membutuhkan casing khusus. Jika itu benar, maka Anda hanya perlu memeriksa(a,b)==(3,7)
urutan itu, sejak(7,3)
berulang hingga(3,7)
, dan mungkin ada ungkapan yang lebih pendek untuk itu.^
adalah XOR, bukan eksponensial, atau (b) XOR memiliki prioritas lebih rendah daripada+
.Retina , 100 byte
Ini mengambil input yang dipisahkan dengan koma. Output selalu dimulai dengan tiga nol terkemuka.
Cobalah online!
Saya benar-benar bertanya-tanya apakah ada solusi yang lebih pendek untuk tahap pertama ...
sumber
Jelly,
292826242120 byteIni saya / O dalam desimal. Bilangan bulat harus dipisahkan oleh karakter non-alfanumerik
+
.Cobalah online! atau verifikasi semua kasus uji .
Latar Belakang
Dalam Aritmatika dalam Basa Kompleks , penulis menunjukkan cara menambahkan dan mengalikan bilangan kompleks dalam basis -n + i .
Untuk basis -1 + i , penambahan dilakukan mirip dengan penambahan biner biasa dengan carry, dengan dua perbedaan:
Alih-alih membawa 1 ke posisi lebih tinggi berikutnya, kami membawa 110 ke tiga berikutnya.
Membawa angka dapat diperbanyak tanpa batas. Namun, tanpa angka nol di depan, jumlah a + b memiliki paling banyak delapan digit lebih dari maksimum a dan b .
Kami melanjutkan sebagai berikut.
Pertama, kita menambahkan a dan b seolah-olah digit mereka adalah angka desimal.
Untuk a = 10101 dan b = 11011 , ini memberikan 21112 .
Untuk setiap digit yang lebih besar dari 1 , kita harus mengurangi 2 dari angka itu dan membawa 110 ke tiga posisi berikutnya yang lebih tinggi. Kita dapat mencapai ini dengan mengkonversi masing-masing digit desimal ke biner, sehingga array biner dari dasar 1100 ke integer, dan menafsirkan daftar yang dihasilkan dari 0 's, 1 ' s, 1100 's dan 1101 ' s sebagai dasar non-kanonik 10 jumlah. 1
Untuk jumlah 21112 , ini memberi 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210 .
Kami mengulangi langkah 2 total d + 8 kali, di mana d adalah jumlah digit a + b .
Untuk jumlah awal 21112 , hasilnya adalah
Kami membuang semua kecuali digit d + 8 terakhir dari hasil akhir. Ini dicapai dengan membuang semuanya setelah 2 terakhir . 2
Untuk jumlah awal 21112 , hasil akhirnya adalah 10010 .
Bagaimana itu bekerja
1 Perhatikan bahwa angka-angka dari jumlah ini tidak dapat melebihi 3 (nilai awal 1 ditambah dua 1 dari carry).
2 Ini berfungsi karena digit terakhir yang akan dibatalkan tidak boleh 3 .
sumber
Python 3, 289 byte
Ini melakukan penambahan digit dari paling sedikit ke paling signifikan (dengan kata lain, algoritma yang sama persis dengan yang Anda pelajari di sekolah dasar). Perbedaannya adalah bahwa (a) itu dalam biner, bukan desimal, jadi Anda membawa setiap kali angka 2 atau lebih, dan (b)
1 + 1 = 1100
, tidak10
.Sebenarnya, perlu juga dicatat bahwa
11 + 111 = 0
, jika jumlah yang menjadi nol tidak akan pernah berakhir.Lebih banyak golf tentu saja mungkin.
sumber
Retina,
157151134133124123 byte1 byte off berkat Martin Büttner.
Cobalah online!
Konversi ke unary, lalu ulangi penggantian berikut (ditampilkan di sini dalam desimal):
Pada dasarnya, ketika lebih besar dari dua: ambil dua, tambahkan tidak ada di digit sebelumnya, tambahkan satu ke digit sebelumnya, lalu tambahkan satu ke digit sebelumnya.
Dalam pseudocode:
Implementasi unary:
Setiap digit (misalnya
3
) ditampilkan sebagai jumlahx
s (misalnyaxxx
) dan kemudian diawali dengan0
.Sebagai contoh,
1234
akan dinyatakan sebagai0x0xx0xxx0xxxx
.Ini
0
tidak berubah, seperti yang101
akan diungkapkan oleh0x00x
.Sejak awal dan akhirnya, hanya ada
0
dan1
, konversi dapat dengan mudah dilakukan oleh1->0x
dan0x->1
.Klik di sini untuk melihat setiap langkah .
sumber
JavaScript (ES6),
146126 byteg
mengubah integer Gaussian (bagian nyata dan imajiner) menjadi basisi-1
, sementarar
dani
mengubahi-1
integer basis menjadi integer Gaussian (masing-masing bagian nyata dan imajiner). Setelah konversi di tempat, saya hanya perlu melakukan aritmatika.Sunting: Disimpan 20 byte dengan menghitung bagian nyata dan imajiner secara terpisah.
sumber
C ++ 416 byte, plus
#include <vector>\n#include <algorithm>\n
(40 lainnya)atau, dengan lebih banyak ruang putih:
Nyaris tidak bermain golf. Dibutuhkan input sebagai vektor int, dan mengembalikan vektor int.
Contoh langsung .
sumber