Come trovare le prime cifre K della rappresentazione decimale di 1/N

Question

Questa è una domanda di intervista che ho trovato: trovare K prime cifre della rappresentazione decimale di 1/N. Sembra che abbiamo bisogno solo di calcolare 10^K/N per risolvere il problema. Ha senso ? Sembra che mi manchi qualcosa perché la soluzione è troppo facile.

Answer 1

Basta implementare grado-scuola lungo divisione:

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(); 

il ramo su value == 0 è quello di rilevare quando 1/n ha una rappresentazione di terminazione inferiore a k cifre.

Qui, n è il denominatore in 1/n e k è il numero di cifre da stampare nella rappresentazione decimale di 1/n.

Si noti che modificando value *= 10 a value *= b è possibile stampare anche la rappresentazione b-ary di 1/n.

Answer 2

Se sono le prime k cifre, non è molto semplice moltiplicare il numeratore per 10^k e quindi diventa più facile dividere per N? E se abbiamo bisogno della risposta, la rappresentazione decimale che è, allora finiremo per dividere il risultato per 10^K di nuovo in modo che la moltiplicazione precedente nullifica.

Answer 3

Calcolare 10^K/N può essere estremamente costoso con grandi K e N piccole.

Questo è probabilmente più vicino a una buona soluzione: long division. È il modo in cui dividevamo i numeri prima dei calcolatori. :)

Ovviamente, si dovrebbe eseguire questo algoritmo solo fino a quando non produce cifre K.