El reto
Para este desafío, se supone que debes determinar si un número dado está en el conjunto de Cantor. Primero, definamos el conjunto de Cantor.
Primero, comience con los números entre 0 y 1. Cualquier número fuera de este rango no está en el conjunto de Cantor. Ahora, dividamos los números en tres partes iguales: [0,1 / 3], [1 / 3,2 / 3], [2/3, 1]. Cualquier número que no esté dentro de los rangos de la primera y última parte no está en el conjunto de Cantor. Ahora, repite este proceso para los segmentos [0,1 / 3] y [2/3, 1]. Luego repites lo que sobra. Sigues haciendo esto para siempre. Al final, todos los números restantes están en el conjunto de Cantor. Aquí hay un diagrama de las primeras seis iteraciones:
Entrada
Dos enteros x
y y
.
0 < y < 2^15
0 <= x <= y
El máximo común denominador de x
y y
es 1, a menos que x == 0
.
Salida
Verdad si x/y
está en el conjunto de Cantor.
Falsy si x/y
no está en el conjunto de Cantor.
Ejemplos
Ahora, veamos algunos ejemplos de números que están en el conjunto de Cantor.
1/3 -> true
Está en un límite, y los límites nunca se eliminan.
1/4 -> true
1/4
nunca está en el tercio medio de un segmento, aunque tampoco está en el límite tampoco. Si sigues su camino, en realidad encontrarás que alterna entre estar en el primer y último tercio de una sección.
1/13 -> true
1/13
alterna entre la primera, primera y última sección.
1/5 -> false
1/5
cae en el primer bloque vacío de la tercera fila en el diagrama anterior, entre 1/9 y 2/9.
Otros casos de prueba:
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
Puedes probar otros números con este fragmento:
Objetivo
La persona con menos bytes gana.
fuente
x == 0
Respuestas:
Mathematica, 54 bytes
Función sin nombre que toma una fracción
x/y
como entrada, dondey > 0
y0 ≤ x ≤ y
, y regresaTrue
oFalse
.Un número real entre 0 y 1 está en el conjunto de Cantor precisamente cuando ninguno de los dígitos en su expansión de base 3 es igual a 1; la excepción es que una fracción cuyo denominador es una potencia de 3 (cuya expansión de base-3 por lo tanto termina) puede terminar en 1.
RealDigits[#,3][[1]]
da todos los dígitos en la expansión de base 3 de la entrada fraccional#
, en una forma como{1, 0, 2, {0, 1, 0, 2}}
: la última lista es la parte periódica de la expansión, mientras que los enteros de antemano son los dígitos antes de que comience la periodicidad. Si la expansión de base-3 es periódica de inmediato, la salida es como{{0, 1, 0, 2}}
; si la expansión de base 3 termina, la forma es como{1, 0, 2}
.Por lo tanto, queremos verificar, utilizando
~FreeQ~1
, si la lista está libre de1
s o no. Sin embargo, debido a la expansión final, queremos eliminar el último elemento de la lista si es igual1
; eso es lo queIf[Last@#===1,Most@#,#]
logra. (Se===
necesita para comparar una lista potencial con1
:==
solo permanece sin evaluar en esa situación).fuente
IsCantorNumber
pero tiene una función para determinar si algo es una cabra .FreeQ[RealDigits[#,3][[1]]/.{{x___,1}}:>{x},1]&
1
s finales en la parte periódica, lo que lleva a respuestas incorrectas. Por ejemplo, la expansión de base 3 de 7/8 es .21212121 ...., o{{2,1}}
; pero la regla sugerida cambiaría eso a{{2}}
, que está libre de1
s pero no debería serlo.#==0||FreeQ[RealDigits[#,3]/.{{x___,1},_}:>{x},1]&
? Si está terminando y noRealDigits[#,3]
será cero de la forma{{__Integer},-1}
y si está repitiendo, será de la forma{{___Integer,{__Integer}},-1}
, ¿verdad? Estoy en el móvil, así que es difícil de probar en este momento. Si esto funciona, utilizar la notación infija para tambiénRealDigits
podría funcionar.C (gcc) ,
615958 bytesExplota la simetría del conjunto de Cantor. Se rompe después de las
y
iteraciones para evitar un bucle infinito.Pruébalo en línea!
fuente
Gelatina ,
22171615 bytesHuellas dactilares 3 para la verdad, nada para la falsedad.
Pruébalo en línea!
Antecedentes
Una propiedad bien conocida del conjunto de Cantor es que contiene precisamente aquellos números entre 0 y 1 que se pueden escribir sin 1 en su expansión ternaria.
Tenga en cuenta que algunos números, precisamente los bordes derechos de los intervalos cerrados involucrados en la construcción del conjunto, se pueden escribir con un solo (final) 1 o con una cantidad infinita de 2 finales . Por ejemplo, 1 = 1 3 = 0.22222 ... 3 y 1/3 = 0.1 3 = 0.022222 ... 3 , igual que 0.5 10 = 0.499999 ... 10 .
Para evitar el revestimiento especial de los bordes derechos, podemos verificar si 1 es la expansión decimal más corta tanto en x / y como en 1 - x / y = (y - x) / y , donde x / y es un borde derecho si (y - x) / y es un borde izquierdo. Si al menos uno de ellos no contiene 1 , x / y pertenece al conjunto de Cantor.
Cómo funciona
fuente
3
es el verdaderotrue
+1.JavaScript (ES6), 65
67Editar 2 bytes guardados gracias a @Luke
Menos golf
Prueba
fuente
n=n%d*3
conq=n/d|0
y luego reemplazarz[n]
conz[n=n%d*3]
JavaScript (ES6), 55 bytes
Úselo al curry primero en el denominador y luego en el numerador. La forma estándar es un byte más largo:
Explicación
Si una fracción no está en el conjunto de Cantor, debe caer en una de las secciones centrales en algún momento; por lo tanto, su representación en la base 3 debe contener un 1 seguido en algún punto por un dígito distinto de cero. Así es como funciona esto:
z
realiza un seguimiento de si hemos encontrado un 1.q
es el dígito actual en la base 3.!z|!q
es verdadero siz
es falso (no hemos encontrado un 1) oq
es falso (el dígito actual es 0).Si
n
se reduce a cero antes de encontrar un dígito distinto de cero en algún lugar después de un 1, la fracción está en el conjunto de Cantor y regresamos1
.fuente
Bash + utilidades GNU, 62 bytes
Pruébalo en línea!
Pásalo dos argumentos enteros con arg1 <= arg2 y 0 <arg2.
La salida se devuelve en el código de salida (0 para falso, 1 para verdadero), según lo permitido por los métodos de E / S PPCG .
Sospecho que la expresión regular se puede jugar más, incluso eliminando el comando tr a favor de usar grep -z, pero este es el más corto que he podido encontrar. (Desafortunadamente, grep -z es incompatible con grep -P, y la opción -P para obtener expresiones regulares de estilo perl es necesaria para la sintaxis?!).
Programa de prueba y salida:
Explicación
parte dc (los argumentos son x e y):
parte tr y grep:
Un problema menor es que, aunque dc maneja enteros arbitrariamente grandes, cuando dc imprime un número grande, lo dividirá en líneas de 69 caracteres, con cada línea excepto la última que termina con una barra diagonal inversa, y con una nueva línea después de cada línea.
El comando tr elimina cualquier barra diagonal inversa y nueva línea. Esto deja solo una línea.
El comando grep luego usa una expresión regular de estilo perl (opción -P, que es una extensión GNU). La expresión regular coincide si la línea contiene un 1 no seguido de al menos y 0 o al menos y 2, que luego finalizan la cadena.
Esto es exactamente lo que se necesita para identificar que x / y no está en el conjunto de Cantor, porque la parte repetida de la representación de base 3 del número racional x / y puede verse como comenzando en el dígito # y + 1 después del punto ternario , y tiene como máximo y dígitos de largo.
fuente
CJam (19 bytes)
Conjunto de pruebas en línea
Este es un bloque anónimo (función) que toma dos argumentos en la pila y se va
0
o1
en la pila. Funciona convirtiendo la fracciónx/y
en dígitos dey
base3
y devolviendo verdadero si no contienen1
o el único1
es parte de un sufijo1 0 0 0 ...
.fuente
Pyth , 14 bytes
Basado en mi solución C.
y
en la primera línea de entrada,x
en la segunda.Si
x/y
está dentro del conjunto de Cantor,x
permanece entre0
yy
. De lo contrario, sex
vuelve mayor quey
en un punto, luego diverge al infinito negativo en las iteraciones restantes.Pruébalo en línea!
fuente
Lote, 91 bytes
Prueba la primera
y-1
base de 3 dígitos dex/y
.i
es el recuento de dígitos probados.n
es el siguiente valor dex
.j
es cierto sin
llega a cero (porque la expansión termina) o hemos probadoy-1
dígitos sin encontrar a1
.f
es verdadero sij
es verdadero o si el siguiente dígito es a1
, en cuyo punto dejamos de hacer bucles y de salidaj
.fuente