Cómo encontrar los primeros dígitos de K de la representación decimal de 1/N

Question

Esta es una pregunta de la entrevista que encontré: encuentre K primeros dígitos de la representación decimal de 1/N. Parece que solo necesitamos calcular 10^K/N para resolver el problema. Tiene sentido ? Parece que me falta algo porque la solución es demasiado fácil.

Answer 1

Sólo implementar el algoritmo de división de escuela primaria:

int value = 1; 
bool outputDecimalSeparator = false; 
int digitsOutput = 1; 
while(digitsOutput <= k) { 
    if (value == 0) { 
     Console.Write(0); 
    } 
    else { 
     if (value < n) { 
      Console.Write(0); 
      value *= 10; 
     } 
     else { 
      Console.Write(value/n); 
      value %= n; 
     } 
    } 
    if (outputDecimalSeparator == false) { 
     outputDecimalSeparator = true; 
     Console.Write('.'); 
    } 
    digitsOutput++; 
} 
Console.WriteLine(); 

La rama de value == 0 es detectar cuando 1/n tiene una representación de terminación de menos de k dígitos.

Aquí, n es el denominador en 1/n y k es el número de dígitos para imprimir en la representación decimal de 1/n.

Tenga en cuenta que cambiando value *= 10 a value *= b puede imprimir la representación b-aria de 1/n también.

Answer 2

Si son los primeros k dígitos, ¿no es muy sencillo multiplicar el numerador por 10^k y entonces es más fácil dividir por N? Y si necesitamos la respuesta, es decir, la representación decimal, entonces terminaremos dividiendo el resultado por 10^K nuevamente para que la multiplicación previa anule.

Answer 3

Calcular 10^K/N puede ser extremadamente costoso con K's grandes y N's pequeñas.

Esto es probablemente más cercano a una buena solución: long division. Es como solíamos dividir los números antes que las calculadoras. :)

Obviamente, solo debe ejecutar este algoritmo hasta que arroje K dígitos.