Introdução
Todo número racional entre 0 e 1 pode ser representado como uma sequência eventualmente periódica de bits. Por exemplo, a representação binária de 11/40 é
0.010 0011 0011 0011 ...
onde a 0011
peça se repete indefinidamente. Uma maneira de encontrar essa representação é a seguinte. Comece com r = 11/40 e , em seguida, duplique -o repetidamente e pegue a parte fracionária, registrando quando estiver acima de 1. Quando o valor de r se repete, você sabe que inseriu um loop.
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.
Para passar da string binária de volta para 11/40, você pode usar a fórmula
(int(prefix) + int(suffix)/(2^len(suffix) - 1)) / 2^len(prefix)
onde prefix
é a parte inicial 010
, suffix
é a parte de repetição 0011
e int
converte uma string binária em número inteiro.
Dadas duas representações, podemos executar a operação XOR bit a bit nelas. A sequência resultante também será periódica, portanto representa um número racional.
Para alguns números racionais, existem duas representações binárias.
1/4 = 0.010000000...
= 0.001111111...
A escolha entre eles pode afetar o resultado do XOR bit a bit. Nesses casos, usamos a representação anterior, que possui infinitos 0s.
A tarefa
Suas entradas são dois números racionais no intervalo semiaberto [0,1). Sua saída deve ser o resultado da operação XOR bit a bit aplicada às entradas, expressa como um número racional. Observe que a saída pode ser 1, mesmo que nenhuma das entradas seja.
Os formatos exatos de entrada e saída são flexíveis, mas cada número racional deve ser representado por dois números inteiros, o numerador e o denominador (com exceção de 0 e 1, que podem ser representados como 0
e 1
se desejado). Você pode assumir que as entradas são expressas nos termos mais baixos. A saída deve ser expressa nos termos mais baixos. Um tipo de número racional interno é um formato aceitável, desde que satisfaça essas restrições. Você pode ignorar quaisquer limites nos números inteiros impostos pelo seu idioma, mas seu algoritmo deve teoricamente funcionar para todos os números racionais.
A menor contagem de bytes vence. Aplicam-se as regras padrão de código de golfe .
Exemplo
Considere as entradas 11/40 e 3/7. Escrevemos suas representações uma acima da outra, delimitando as partes repetidas por tubos |
. Em seguida, extraímos partes repetidas de comprimentos iguais e aplicamos XOR bit a bit a elas e às partes anteriores a elas.
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 ...
O número racional resultante é 89/520.
Casos de teste
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...
casos (que também é o que obtemos se usarmos o algoritmor
). Por exemplo, no caso em5/8, 1/3
que obtemos23/24
porque escolhemos a expansão0.101000...
para5/8
. Se escolhermos0.10011111...
como5/8
, o resultado após o XOR se tornar19/24
, então isso está errado. Relacionado à Wikipedia: 0,999 ...(a ^ b) ^ b == a
não é válido. Por exemplo(19/24 ^ 1/3) ^ 1/3 != 19/24
. Isso me fez perder um pouco de entusiasmo com isso :(Respostas:
Python 3,
193164 bytesRecebe a entrada como o
fractions.Fraction
tipo de Python 3 e a gera também.Curiosidade (você pode mostrar isso facilmente usando funções geradoras), se mudar
(a<.5)^(b<.5)
para((a>=.5)and(b>=.5))
acima, obtém o binário AND entre dois números racionais. Ligue para issond(a, b)
. Então nós temosa + b - 2*nd(a, b) = x(a, b)
!fonte
JavaScript, 141 bytes
Não funcionará no último caso de teste (excesso de número inteiro). Insira 4 números para
p/q xor r/s
, produza uma matriz com dois números. Para testcase0, 0
, você deve inserir0, 1, 0, 1
.Quão:
(Todos os números descritos aqui estão em formato binário.)
b
queb = 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
; Converterp / q
,r / s
parax / b
ey / b
;o = 10 ^ (p - q) - 1
; divisãox
,y
para[x % o, x / o]
,[y % o, y / o]
; obtenha xor para cada parte[x % o xor y % o, x / o xor y / o]
e retorne a(x % o xor y % o) + (x / o xor y / o) * o
; Doe comoa
;a = 0
, a resposta é0
(ou0 / 1
); Caso contrário, deixeu = gcd(a, b)
; a resposta é(a/u)
e(b/u)
.Mostrar snippet de código
fonte