0votos

K-Ceros en Haskell

por josejuan hace 6 años

El código lo resuelve para cualquier M en menos de un segundo... pero en la máquina adecuada :P

Encontrar un numero k tal que su factorial tenga al menos m ceros a la derecha y el facotirla de k-1 tenga menos de m ceros a la derecha... Su dificultad recae en que m puede llegar a valer hasta 20000000000, Y el tiempo de ejecución es de menos de 1 segundo. NOTA: el tiempo de ejecución, se concidera como el tiempo en que se tarda el programa en realizar todas sus operaciones... 1 segundo de ejecución aproximadamente son 100000000 iteraciones de un ciclo.

1
2
3
4
divN d n = if n `mod` d /= 0 then 0 else 1 + divN d (n `div` d) 
sumDivsN d n = sum $ map (divN d) [1..n] 
ceros n = min (sumDivsN 2 n) (sumDivsN 5 n) 
primeroCon m = head $ filter (((==)m).ceros) [m..] 
6 comentarios
0votos

Escrito por jalonso hace 6 años

La definición de primerosCon no calcula el valor para los siguientes valores de m: 5, 11, 17, 23, 29, 30, ...
0votos

Escrito por josejuan hace 6 años

No entiendo bien jalonso. No, sólo calcula el primer "m", al ser el primer "m", el factorial anterior/es fijo que tendrá/n menos ceros (por eso con el primero basta) ¿hace falta calcular algo más?. Ya digo que igual algo se me escapa...
0votos

Escrito por josejuan hace 6 años

¡ah! Ok, ya entiendo, es que "primeroCon m" es el primero con "m" ceros.

Tienes razón, el enunciado pide "tenga al menos m ceros".

Fácil, cambiar "==" por ">=".

¡Gracias!
0votos

Escrito por jalonso hace 6 años

Efectivamente josejuan, ese era el problema ya que no hay ningún número cuyo factorial termine "exactamente" en n ceros (con n = 5, 11, 17, 23, 29, 30, ...).

Era una errata que se corrige fácilmente como indicas.

Una mejora consiste en observar que en la definición de la función ceros no es necesario calcular (sumDivsN 2 n).
0votos

Escrito por josejuan hace 6 años

"Una mejora consiste"

pues no caigo a que te refieres. Para saber los ceros, es necesario saber el número de factores de 2, obviamente hay formas más eficientes de obtenerlos (bits LSB), pero no veo como obtener los ceros sin conocer los factores de 2.
0votos

Escrito por jalonso hace 6 años

Una definición equivalente de la función ceros es

ceros' n = sumDivsN 5 n

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.