pengantar
Setiap bilangan rasional antara 0 dan 1 dapat direpresentasikan sebagai urutan bit yang akhirnya periodik. Sebagai contoh, representasi biner 11/40 adalah
0.010 0011 0011 0011 ...
di mana 0011
bagian berulang tanpa batas. Salah satu cara untuk menemukan representasi ini adalah sebagai berikut. Mulailah dengan r = 11/40 , lalu berulang kali gandakan dan ambil bagian fraksional, catat ketika berada di atas 1. Ketika nilai r berulang, Anda tahu Anda telah memasukkan satu lingkaran.
1. r = 11/40
2. 2*r = 11/20 < 1 -> next bit is 0, r = 11/20
3. 2*r = 11/10 >= 1 -> next bit is 1, r = 2*r - 1 = 1/10
4. 2*r = 1/5 < 1 -> next bit is 0, r = 1/5
5. 2*r = 2/5 < 1 -> next bit is 0, r = 2/5
6. 2*r = 4/5 < 1 -> next bit is 0, r = 4/5
7. 2*r = 8/5 >= 1 -> next bit is 1, r = 2*r - 1 = 3/5
8. 2*r = 6/5 >= 1 -> next bit is 1, r = 2*r - 1 = 1/5, same as in 4.
The loop 5. -> 6. -> 7. -> 8. now repeats.
Untuk mendapatkan dari string biner kembali ke 11/40, Anda bisa menggunakan rumus
(int(prefix) + int(suffix)/(2^len(suffix) - 1)) / 2^len(prefix)
di mana prefix
bagian awal 010
, suffix
adalah bagian berulang 0011
, dan int
mengubah string biner ke integer.
Diberikan dua representasi seperti itu, kita dapat melakukan operasi XOR bitwise pada mereka. Urutan yang dihasilkan juga akan berkala, sehingga mewakili bilangan rasional.
Untuk beberapa bilangan rasional, ada dua representasi biner.
1/4 = 0.010000000...
= 0.001111111...
Pilihan di antara mereka dapat mempengaruhi hasil XOR bitwise. Dalam kasus ini, kami menggunakan representasi sebelumnya, yang memiliki 0s tak terhingga banyaknya.
Tugas
Input Anda adalah dua angka rasional dalam interval setengah terbuka [0,1). Output Anda akan menjadi hasil operasi XOR bitwise yang diterapkan pada input, dinyatakan sebagai angka rasional. Perhatikan bahwa outputnya bisa 1, meskipun tidak ada inputnya.
Format input dan output yang tepat fleksibel, tetapi setiap bilangan rasional harus diwakili oleh dua bilangan bulat, pembilang dan penyebut (dengan pengecualian 0 dan 1, yang dapat direpresentasikan sebagai 0
dan 1
jika diinginkan). Anda dapat mengasumsikan bahwa input dinyatakan dalam istilah terendah. Output harus dinyatakan dalam istilah terendah. Tipe bilangan rasional bawaan adalah format yang dapat diterima, asalkan memenuhi batasan ini. Anda dapat mengabaikan batasan apa pun pada bilangan bulat yang dipaksakan oleh bahasa Anda, tetapi algoritme Anda harus secara teoritis bekerja untuk semua bilangan rasional.
Hitungan byte terendah menang. Aturan standar kode-golf berlaku.
Contoh
Pertimbangkan input 11/40 dan 3/7. Kami menulis representasi mereka satu di atas yang lain, membatasi bagian yang berulang dengan pipa |
. Kemudian kami mengekstrak bagian berulang dengan panjang yang sama, dan menerapkan bitor XOR padanya dan bagian sebelumnya.
11/40 = 0. 0 1 0|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 1|0 0 1 ...
3/7 = 0.|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|0 1 1|...
-> 0. 0 0 1|0 1 0 1 1 1 1 0 1 0 0 0|0 1 0 1 1 1 1 0 1 0 0 0|0 1 0 ...
Angka rasional yang dihasilkan adalah 89/520.
Uji kasus
0 0 -> 0
1/2 1/2 -> 0
1/2 1/4 -> 3/4
1/3 2/3 -> 1
1/2 3/4 -> 1/4
5/8 1/3 -> 23/24
1/3 1/5 -> 2/5
15/16 3/19 -> 257/304
15/16 257/304 -> 3/19
3/7 11/40 -> 89/520
5/32 17/24 -> 59/96
16/29 16/39 -> 621001733121535520/696556744961512799
000...
kasus ini (yang juga kita dapatkan jika menggunakan algoritme denganr
). Misalnya, dalam hal ini5/8, 1/3
kita dapatkan23/24
karena kita memilih ekspansi0.101000...
untuk5/8
. Jika kita memilih0.10011111...
sebagai5/8
, hasil setelah XOR menjadi19/24
, jadi ini salah. Terkait dengan Wikipedia: 0,999 ...(a ^ b) ^ b == a
tidak berlaku. Misalnya(19/24 ^ 1/3) ^ 1/3 != 19/24
. Itu membuat saya kehilangan sedikit kegembiraan tentang hal ini :(Jawaban:
Python 3,
193164 byteMengambil input sebagai
fractions.Fraction
tipe Python 3 , dan mengeluarkannya juga.Fakta menyenangkan (Anda dapat dengan mudah menunjukkan ini menggunakan fungsi-fungsi pembangkit), jika Anda mengubah
(a<.5)^(b<.5)
ke((a>=.5)and(b>=.5))
atas Anda mendapatkan biner DAN antara dua bilangan rasional. Sebut inind(a, b)
. Lalu kita milikia + b - 2*nd(a, b) = x(a, b)
!sumber
JavaScript, 141 byte
Tidak akan berfungsi untuk test case terakhir (integer overflow). Input 4 angka untuk
p/q xor r/s
, output array dengan dua angka. Untuk testcase0, 0
, Anda harus memasukkan0, 1, 0, 1
.Bagaimana:
(Semua angka yang dijelaskan di sini adalah dalam bentuk biner.)
b
, yangb = 10 ^ p - 10 ^ q (p, q are integers, p > q); and b = 0 (mod q); and b = 0 (mod s)
;x = p * b / q
,y = r * b / q
; Konversip / q
,r / s
kex / b
dany / b
;o = 10 ^ (p - q) - 1
; perpecahanx
,y
untuk[x % o, x / o]
,[y % o, y / o]
; dapatkan xor untuk setiap bagian[x % o xor y % o, x / o xor y / o]
, dan gabung kembali ke(x % o xor y % o) + (x / o xor y / o) * o
; Donasi sebagaia
;a = 0
, jawabannya adalah0
(atau0 / 1
); Kalau tidak, biarkanu = gcd(a, b)
; jawabannya adalah(a/u)
dan(b/u)
.Tampilkan cuplikan kode
sumber