Como calcular Recorrente dígitos?

Question

Dado dois inteiros a e b, como eu iria sobre como calcular o decimal de repetição de a / b? Isso pode ser em qualquer idioma; o que for mais fácil para você expressar-lo.

Answer 1

Você pode fazê-lo com a divisão longa. Calcule um único dígito de cada vez e subtrair para obter um resto, que você multiplicar por 10 para obter o numerador para a próxima etapa. Quando este novo numerador corresponde a um dos numeradores anteriores, você sabe que está indo para repetir a partir desse ponto em diante. Você só precisa manter uma pilha de numeradores anteriores e procurar por ela a cada iteração.

Answer 2

Você pode calcular a representação decimal de a / b usando o algoritmo de divisão longa que você aprendeu na escola, como disse Mark Ransom. Para calcular cada dígito sucessiva, dividir o dividendo corrente (numerador ou restante) por b, e encontrar a próxima dividendos como o restante multiplicado por 10 ( "derrubar um 0"). Quando um resto é o mesmo que alguns restante anterior, isso significa que os dígitos a partir de então se repetirá, bem como, para que você possa observar este fato e stop.

Observe o potencial para uma otimização aqui: os restos que você começa quando dividindo por b estão na faixa de 0 a b-1, de modo que você mantenha restos diferentes de zero única distintas, você não tem que procurar através de sua lista de anterior remanescentes para ver se algo se repete. Assim, o algoritmo pode ser feito para tomar constante de tempo por passo divisão, e espaço O(b) é suficiente. Basta manter a par do que posição do dígito cada restante ocorreu pela primeira vez em.

(Este argumento, Aliás, é também uma prova matemática que a parte recorrente pode ser na maioria dos dígitos b-1 de comprimento:. Por exemplo, 7/1 = 0 (142,857) tem uma parte recorrentes de 6 dígitos, e 1/17 = 0. (0588235294117647) tem uma parte recorrente de 16 dígitos. O comprimento sempre divide b-1, na verdade.)

Aqui está o código Python para fazer isso, que é executado em tempo 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)

Você também pode usar um array (uma lista em Python) de tamanho b em vez de um dicionário, que será um pouco mais rápido (não em termos de asymptotics, mas no fator constante).

Answer 3

Eu acho que isso é o que você está procurando ..

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

Eu não sou um especialista, e eu acho que esta solução pode não ser eficiente, mas pelo menos é fácil de fazer:

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

Comentários são bem aceitos