Tenemos un número de coma flotante r
entre 0 y 1, y un número entero p
.
Encuentre la fracción de enteros con el mínimo denominador, que se aproxima r
con al menos p
precisión de dígitos.
- Entradas:
r
(un número de coma flotante) yp
(entero). - Salidas:
a
yb
enteros, dondea/b
(como flotante) se aproximar
hasta losp
dígitos.b
es el menor entero positivo posible más pequeño.
Por ejemplo:
- si
r=0.14159265358979
yp=9
, - entonces el resultado es
a=4687
yb=33102
, - debido
4687/33102=0.1415926530119026
.
Cualquier solución tiene que funcionar en teoría con tipos de precisión arbitraria, pero las limitaciones causadas por los tipos de precisión fija de las implementaciones no importan.
Precisión significa el número de dígitos después de " 0.
" en r
. Por lo tanto, si r=0.0123
y p=3
, entonces a/b
debería comenzar con 0.012
. Si los primeros p
dígitos de la parte fraccional de r
son 0, el comportamiento indefinido es aceptable.
Criterio de victoria:
- El algoritmo algorítmicamente más rápido gana. La velocidad se mide en O (p).
- Si hay varios algoritmos más rápidos, entonces gana el más corto.
- Mi propia respuesta está excluida del conjunto de posibles ganadores.
PD: la parte de matemáticas es en realidad mucho más fácil de lo que parece, sugiero leer esta publicación.
fuente
padEnd
ymatch
? ¿No puede simplementeslice
cada cadena a la longitud correcta y luego restarlas?padEnd
se usa para testcasef(0.001,2)
yf(0.3,2)
.(r,p)=>{for(a=0,b=1;`${a/b}`.slice(0,p+2)-`${r}`.slice(0,p+2);a/b<r?a++:b++);return[a,b]}
similar a (no totalmente golfizado).Haskell , O (10 p ) en el peor de los casos
121119 bytesPruébalo en línea!
Guardado 2 bytes gracias a Laikoni
Usé el algoritmo de /math/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i .
En cada paso, el nuevo intervalo es la mitad del intervalo anterior. Por lo tanto, el tamaño del intervalo es
2**-n
, donden
está el paso actual. Cuando2**-n < 10**-p
, estamos seguros de tener la aproximación correcta. Sin embargo, sin > 4*p
entonces2**-n < 2**-(4*p) == 16**-p < 10**-p
. La conclusión es que el algoritmo esO(p)
.EDITAR Como lo señaló orlp en un comentario, la afirmación anterior es falsa. En el peor de los casos,
r = 1/10**p
(r= 1-1/10**p
es similar), habrá10**p
etapas:1/2, 1/3, 1/4, ...
. Hay una mejor solución, pero no tengo tiempo en este momento para solucionarlo.fuente
f=
y guardar dos bytes conz<-floor.(*10^p),u<-a+c,v<-b+d
.f=
en TIO en el código Haskell.-cpp
indicador del compilador y escribirf=\
en el encabezado: ¡ Pruébelo en línea!C, 473 bytes (sin contexto), O (p), no competidora
Esta solución utiliza la parte matemática detallada en esta excelente publicación. Calculé solo
calc()
en el tamaño de la respuesta.fuente