Vamos a concatenar los cuadrados de los números que comienzan por 1. Entonces, ¿cuál es el nésimo dígito de esta cadena?cómo encontrar n ° dígito en un número como 1491625 ....?
Por ejemplo, el décimo dígito es 4.
1 4 9 16 25 36 49 64 81
Es simplemente una cuestión ordinaria que vienen a la mente ordinaria mía. ¿Cómo puedo resolver esto para dormir bien esta noche? Algún algoritmo sin bucle?
Puede trabajar enumerar cuántos dígitos 1, 2 dígitos, 3 dígitos, etc. números que hay en esta secuencia mediante la adopción de las raíces cuadradas de los poderes-de-10. Esto le permitirá establecer en qué número se encuentra el n-décimo dígito. A partir de ahí, debería ser bastante trivial.
Esto debería ser O (log n) complejidad.
+1 Otra optimización no es calcular las raíces cuadradas cada vez, porque sqrt (10^n) = sqrt (10^(n-1)) * sqrt (10), eso es una multiplicación por potencia de 10. – biziclop
@biziclop: ¡Es una buena idea! Supongo que las inexactitudes numéricas llevarían este cálculo iterativo a divergir ya que 'n' es * realmente * grande, sin embargo. –
Sí, en la práctica con aritmética de punto flotante lo hará. Pero como algoritmo teórico, funciona. – biziclop
Las listas infinitas perezosas en Haskell hacen que este trivial se exprese ingenuamente.
ghci> concat [show $ i*i | i <- [1..]] !! 9 '4'
¿Por qué no debería repetir el ciclo, tomando cada número, cuadrando e incrementando el conteo desde 1 comprobando en cada paso si ha alcanzado n? No tiene que hacer un seguimiento del número entero. Es un ejercicio de simulación simple. Tengo miedo, no puedo identificar un patrón o fórmula para esto.
Hay formas más efectivas de hacerlo. Digamos que quieres el dígito de dos billonésimas, eso es una gran cuadratura hasta que llegues allí. – biziclop
ceil (log (x + 1)) le dará la cantidad de dígitos en un número. Itere a través de los cuadrados, manteniendo un recuento de la longitud total y una vez que haya alcanzado o excedido la longitud objetivo n, sabrá que necesita el m-ésimo dígito del último número para algunos m (fácil de calcular). Obtener el dígitos Mes de este número de dividir por 10 m-1 de tomar el último dígito con un mod 10.
All-en-todo, constante sobrecarga de espacio y de tiempo de ejecución O (n).
ceil (log10 X + 1) es una mejor estimación (intente, por ejemplo, ceil (log10 10) y cuente los dígitos en 10) .. – Vatine
@Vatine Nice catch, editado. ¡Gracias! – marcog
Después de haber hecho el mismo error yo mismo, fue fácil (ish) detectar. Una alternativa es floor (log10 X) +1. – Vatine
Este es un puerto directo de la respuesta de Haskell ephemient a Scala
Iterator.from(1).flatMap(x=>(x*x).toString.iterator).drop(9).next
vuelve 4
O (n)
Iterator.from(1) crea un iterador infinita que cuenta 1,2,3,4,.....(x*x).toString calcula los cuadrados de cada uno de estos y los convierte en cadenas.flatMap(... .iterator) concatena éstas se conviertan en un iterador infinito de caracteres de la secuencia en cuestióndrop(9) elimina los 9 primeros elementos (índices 0 al 8) desde el repetidor y nos da un nuevo iterador que está esperando en el índice 9next nos da ese solo carácter.No entiendo el código pero me pregunto si es una búsqueda lineal similar solo al ciclo. En) –
Para resolver esto he usado Python Generators.Mi solución en Python:
def _countup(n):
while True:
yield n
n += 1
def get_nth_element(n):
i = 0 # Initialized just to keep track of iterations.
final_string = ''
cu_generator = _countup(0)
while True:
num = cu_generator.next()
final_string += str(num * num)
if len(final_string) > n:
print "Number of iterations %s" % i
return final_string[n]
i += 1
RUN:
>>> get_nth_element(1000)
Number of iterations 229
'2'
>>> get_nth_element(10000)
Number of iterations 1637
'7'
es la función dada la cantidad ya hecho ('' ... 1.491.625) o qué tiene que calcular ella misma? Extraer el enésimo dígito debería ser fácil (independientemente de la base, pero supongo que hablas de la base 10). – delnan
Faltan 64. – ephemient
@ephemient sí gracias. es de noche ahora. perdón por eso –