Cómo calcular los dígitos recurrentes?

Question

Dados dos enteros a y b, ¿cómo puedo hacer para calcular el decimal periódico de a/b? Esto puede ser en cualquier idioma; lo que sea más fácil para ti expresarlo.

Answer 1

Puedes hacerlo con división larga. Calcule un solo dígito a la vez y reste para obtener un resto, que multiplicará por 10 para obtener el numerador para el próximo paso. Cuando este nuevo numerador coincide con uno de los numeradores anteriores, sabrá que va a repetir a partir de ese momento. Solo necesita mantener una pila de numeradores previos y buscar en cada iteración.

Answer 2

Puede calcular la representación decimal de a/b usando el algoritmo de división larga que aprendió en la escuela, como dijo Mark Ransom. Para calcular cada dígito sucesivo, divida el dividendo actual (numerador o resto) por b, y encuentre el siguiente dividendo como el resto multiplicado por 10 ("bajando un 0"). Cuando un resto es igual a algún resto anterior, significa que los dígitos a partir de ese momento también se repetirán, por lo que puede observar este hecho y detenerse.

Tenga en cuenta la posibilidad de una optimización aquí: los restos que obtiene al dividir por b están en el rango de 0 a b-1, por lo que solo conserva distintos residuos distintos de cero, no tiene que buscar en su lista de restos anteriores para ver si algo se repite. Por lo tanto, se puede hacer que el algoritmo tome un tiempo constante por cada paso de división, y el espacio O(b) es suficiente. Simplemente haga un seguimiento de en qué posición de dígito se encontró cada resto por primera vez.

(Este argumento, por cierto, es también una prueba matemática de que la parte recurrente puede tener como máximo b-1 dígitos de longitud; por ejemplo, 1/7 = 0. (142857) tiene una parte recurrente de 6 dígitos y 1 17 = 0. (0588235294117647) tiene una parte recurrente de 16 dígitos. La longitud siempre divide b-1, en realidad.)

Así es código Python para hacer esto, que se ejecuta en O(b) tiempo.

def divide(a, b): 
    '''Returns the decimal representation of the fraction a/b in three parts: 
    integer part, non-recurring fractional part, and recurring part.''' 
    assert b > 0 
    integer = a // b 
    remainder = a % b 
    seen = {remainder: 0} # Holds position where each remainder was first seen. 
    digits = [] 
    while(True): # Loop executed at most b times (as remainders must be distinct) 
    remainder *= 10 
    digits.append(remainder // b) 
    remainder = remainder % b 
    if remainder in seen: # Digits have begun to recur. 
     where = seen[remainder] 
     return (integer, digits[:where], digits[where:]) 
    else: 
     seen[remainder] = len(digits) 

# Some examples. 
for a, b in [(5,4), (1,6), (17,7), (22,11), (100,17)]: 
    (i, f, r) = divide(a, b) 
    print "%d/%d = %d.%s(%s)" % (a, b, i, ''.join(map(str, f)),''.join(map(str,r))) 
# Output: 
# 5/4 = 1.25(0) 
# 1/6 = 0.1(6) 
# 17/7 = 2.(428571) 
# 22/11 = 2.(0) 
# 100/17 = 5.(8823529411764705) 

También puede utilizar una matriz (una lista en Python) de tamaño b en lugar de un diccionario, que será un poco más rápido (no en términos de asintótica, pero en el factor constante).

Answer 3

Creo que esto es lo que buscas ..

public static String divide(int a,int b,boolean decimalDone,boolean isMultiplied,String result){ 
      if(a<b){ 
       a=a*10; 

       if(!decimalDone) {result+=".";decimalDone=true;} 
       else if(isMultiplied) result+="0"; 
       isMultiplied=true; 
       divide(a,b,decimalDone,isMultiplied,result); 

      } 
      else{ 
       result+=a/b; 
       a=a%b; 
       isMultiplied=false; 
       divide(a,b,decimalDone,isMultiplied,result); 
      } 

      return result; 
    } 

Answer 4

No soy un experto, y creo que esta solución no puede ser eficiente, pero al menos es fácil de hacer:

#you want to get a/b 
from fractions import Fraction: 
print float(Fraction(a,b)) 

los comentarios son bien aceptados