¿Cómo calcular los dígitos recurrentes?

Question

Dados dos enteros a y b , ¿cómo puedo 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 el resto, que multiplica por 10 para obtener el numerador para el siguiente paso. Cuando este nuevo numerador coincide con uno de los numeradores anteriores, sabe que va a repetir desde ese punto en adelante. Solo necesita mantener una pila de numeradores anteriores y buscar en cada iteración.

Answer 2

Puedes calcular la representación decimal de a / b usando el algoritmo de división larga que aprendiste 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 un resto anterior, significa que los dígitos a partir de ese momento también se repetirán, por lo que puede anotar este hecho y detenerse.

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

(Este argumento, por cierto, también es 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).

Aquí está el código de Python para hacer esto, que se ejecuta en el tiempo O (b) .

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 usar 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óticos, sino en el factor constante).

Answer 3

Creo que esto es lo que estás buscando ...

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 puede no 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