O desafio
Para esse desafio, você deve determinar se um determinado número está no conjunto Cantor. Então, primeiro, vamos definir o conjunto Cantor.
Primeiro, comece com os números entre 0 e 1. Quaisquer números fora desse intervalo não estão no conjunto Cantor. Agora, vamos dividir os números em três partes iguais: [0,1 / 3], [1 / 3,2 / 3], [2/3, 1]. Quaisquer números fora dos intervalos da primeira e da última parte não estão no conjunto Cantor. Agora, repita esse processo para os segmentos [0,1 / 3] e [2/3, 1]. Então você repete o que resta. Você continua fazendo isso para sempre. No final, todos os números restantes estão no conjunto Cantor. Aqui está um diagrama das seis primeiras iterações:
Entrada
Dois inteiros x
e y
.
0 < y < 2^15
0 <= x <= y
O maior denominador comum de x
e y
é 1, a menos que x == 0
.
Saída
Verdadeiramente se x/y
estiver no conjunto Cantor.
Falsy se x/y
não estiver no conjunto Cantor.
Exemplos
Agora, vamos ver alguns exemplos de números que estão no conjunto Cantor.
1/3 -> true
Está em um limite, e os limites nunca são removidos.
1/4 -> true
1/4
nunca está no terço médio de um segmento, embora também nunca esteja no limite. Se você seguir o caminho, descobrirá que ele alterna entre estar no primeiro e no último terço de uma seção.
1/13 -> true
1/13
alterna entre a primeira, a primeira e a última seção.
1/5 -> false
1/5
cai no primeiro bloco vazio da terceira linha no diagrama acima, entre 1/9 e 2/9.
Outros casos de teste:
0/4 -> true
3/10 -> true
3/4 -> true
10/13 -> true
1/1 -> true
12/19 -> false
5/17 -> false
3/5 -> false
1/7 -> false
1/2 -> false
Você pode tentar outros números com este trecho:
Objetivo
A pessoa com menos bytes vence.
fonte
x == 0
Respostas:
Mathematica, 54 bytes
Função sem nome, tendo uma fração
x/y
como entrada, ondey > 0
e0 ≤ x ≤ y
, e retornandoTrue
ouFalse
.Um número real entre 0 e 1 está no conjunto Cantor precisamente quando nenhum dos dígitos em sua expansão base-3 é igual a 1; a exceção é que uma fração cujo denominador é uma potência de 3 (cuja expansão da base 3 termina portanto) pode terminar em 1.
RealDigits[#,3][[1]]
fornece todos os dígitos na expansão base-3 da entrada fracionária#
, de uma forma como{1, 0, 2, {0, 1, 0, 2}}
: a última lista é a parte periódica da expansão, enquanto os números inteiros anteriormente são os dígitos antes do início da periodicidade. Se a expansão da base 3 for periódica imediatamente, a saída será semelhante{{0, 1, 0, 2}}
; se a expansão da base 3 terminar, o formulário será semelhante{1, 0, 2}
.Então, queremos verificar, usando
~FreeQ~1
, se a lista está livre de1
s ou não. No entanto, devido à expansão da expansão, queremos excluir o último elemento da lista, se for igual1
; é isso queIf[Last@#===1,Most@#,#]
realiza. (O===
necessário para comparar uma lista potencial com1
:==
sozinho permanece sem avaliação nessa situação.)fonte
IsCantorNumber
mas tenha uma função para determinar se algo é uma cabra .FreeQ[RealDigits[#,3][[1]]/.{{x___,1}}:>{x},1]&
1
s na parte periódica, o que leva a respostas incorretas. Por exemplo, a expansão base-3 de 7/8 é .21212121 ...., ou{{2,1}}
; mas a regra sugerida mudaria isso para{{2}}
, que é livre de1
s, mas não deveria ser.#==0||FreeQ[RealDigits[#,3]/.{{x___,1},_}:>{x},1]&
? Se estiver terminando e diferente de zeroRealDigits[#,3]
for do formato{{__Integer},-1}
e se estiver repetindo, será do formato{{___Integer,{__Integer}},-1}
, certo? Estou no celular, por isso é difícil testar agora. Se isso funcionar, o uso da notação infix tambémRealDigits
pode funcionar.C (gcc) ,
615958 bytesExplora a simetria do conjunto Cantor. Interrompe após
y
iterações para evitar um loop infinito.Experimente online!
fonte
Geléia ,
22171615 bytesImprime 3 por verdade, nada por falsidade.
Experimente online!
fundo
Uma propriedade bem conhecida do conjunto Cantor é que ele contém precisamente aqueles números entre 0 e 1 que podem ser escritos sem 1 na expansão ternária.
Observe que alguns números - precisamente as bordas direitas dos intervalos fechados envolvidos na construção do aparelho - podem ser escritos com um único (final) 1 ou com uma quantidade infinita de 2 finais . Por exemplo, 1 = 1 3 = 0,22222… 3 e 1/3 = 0,1 3 = 0,022222… 3 , assim como 0,5 10 = 0,499999… 10 .
Para evitar especial de carcaça as bordas direitas, podemos verificar a existência de um 'S é a expansão mais curto decimal em ambos x / y e 1 - X / Y = (y - x) / y , onde x / y é um sse borda direita (y - x) / y é uma aresta esquerda. Se pelo menos um deles não contém 1 , x / y pertence ao conjunto Cantor.
Como funciona
fonte
3
é o verdadeirotrue
+1.JavaScript (ES6), 65
67Editar 2 bytes salvos thx @Luke
Menos golfe
Teste
fonte
n=n%d*3
porq=n/d|0
e, em seguida, substituirz[n]
porz[n=n%d*3]
JavaScript (ES6), 55 bytes
Use currying no denominador primeiro e no numerador segundo. O formulário padrão é um byte mais longo:
Explicação
Se uma fração não estiver no conjunto Cantor, ela deverá cair em uma das seções do meio em algum momento; portanto, sua representação na base 3 deve conter um 1 seguido em algum momento por um dígito diferente de zero. É assim que isso funciona:
z
controla se encontramos 1.q
é o dígito atual na base 3.!z|!q
é verdadeiro sez
for falso (não encontramos 1) ouq
for falso (o dígito atual é 0).Se
n
descer para zero antes de encontrarmos um dígito diferente de zero em algum lugar após 1, a fração estará no conjunto Cantor e retornaremos1
.fonte
Utilitários Bash + GNU, 62 bytes
Experimente online!
Passe dois argumentos inteiros com arg1 <= arg2 e 0 <arg2.
A saída é retornada no código de saída (0 para falsy, 1 para truthy), conforme permitido pelos métodos de E / S do PPCG .
Eu suspeito que o regex pode ser jogado ainda mais, talvez até mesmo eliminando o comando tr em favor do grep -z, mas esse é o menor tempo que eu consegui. (Infelizmente, grep -z é incompatível com grep -P, e a opção -P para obter expressões regulares no estilo perl é necessária para a sintaxe?!).
Programa e saída do teste:
Explicação
parte dc (os argumentos são xey):
parte tr e grep:
Um problema menor é que, embora o dc lide com números inteiros arbitrariamente grandes, quando o dc imprime um número grande, ele o divide em linhas de 69 caracteres, com cada linha exceto a última que termina com uma barra invertida e com uma nova linha após cada linha.
O comando tr exclui barras invertidas e novas linhas. Isso deixa apenas uma única linha.
O comando grep usa um regex no estilo perl (opção -P, que é uma extensão GNU). A regex corresponde se a linha contiver 1 não seguido por pelo menos y 0 ou pelo menos y 2, que terminam a sequência.
É exatamente isso que é necessário para identificar x / y como não estando no conjunto Cantor, porque a parte repetitiva da representação base-3 do número racional x / y pode ser vista como começando no dígito # y + 1 após o ponto ternário , e tem no máximo y dígitos.
fonte
CJam (19 bytes)
Conjunto de testes online
Este é um bloco anônimo (função) que recebe dois argumentos na pilha e sai
0
ou1
na pilha. Ele funciona convertendo a fraçãox/y
em dígitosy
base3
e retornando true se eles não contêm1
ou a única1
parte de um sufixo1 0 0 0 ...
.fonte
Pitão , 14 bytes
Com base na minha solução C.
y
na primeira linha de entrada,x
na segunda.Se
x/y
estiver dentro do conjunto Cantor,x
permanece entre0
ey
. Caso contrário,x
torna-se maior quey
em um ponto e diverge para o infinito negativo nas iterações restantes.Experimente online!
fonte
Lote, 91 bytes
Testa os primeiros
y-1
3 dígitos da basex/y
.i
é a contagem de dígitos testados.n
é o próximo valor dex
.j
é verdadeiro sen
atingir zero (porque a expansão termina) ou testamosy-1
dígitos sem encontrar a1
.f
é verdadeiro sej
for verdadeiro ou se o próximo dígito for a1
; nesse ponto, paramos o loop e a saídaj
.fonte