Comment calculer les chiffres récurrents?

Question

Étant donné deux entiers a et b , comment puis-je calculer le nombre décimal répété de a / b ? Cela peut être dans n'importe quelle langue. quel que soit le plus facile pour vous de l'exprimer.

Answer 1

Vous pouvez le faire avec une longue division. Calculez un chiffre à la fois et soustrayez-vous pour obtenir le reste que vous multipliez par 10 pour obtenir le numérateur de l'étape suivante. Lorsque ce nouveau numérateur correspond à l'un des numérateurs précédents, vous savez que vous allez répéter à partir de ce moment. Il vous suffit de conserver une pile de numérateurs précédents et de la parcourir à chaque itération.

Answer 2

Vous pouvez calculer la représentation décimale de a / b en utilisant l'algorithme de division longue que vous avez appris à l'école, comme l'a dit Mark Ransom. Pour calculer chaque chiffre successif, divisez le dividende actuel (numérateur ou reste) par b et recherchez le prochain dividende, le reste étant multiplié par 10 ("faisant baisser le 0"). Lorsqu'un reste est identique à un précédent, cela signifie que les chiffres à partir de ce moment-là se répèteront également. Vous pouvez donc noter ce fait et vous arrêter.

Notez le potentiel d'optimisation ici: les restes que vous obtenez en divisant par b sont compris entre 0 et b-1, de sorte que vous ne gardez que des restes non nuls distincts, vous n'avez pas à parcourir votre liste de reste pour voir si quelque chose se répète. On peut donc faire en sorte que l'algorithme prenne un temps constant par pas de division, et l'espace O (b) est suffisant. Gardez simplement une trace de la position du chiffre dans laquelle chaque reste est apparu pour la première fois.

(Cet argument, BTW, est également une preuve mathématique que la partie récurrente peut comporter au plus b-1 chiffres: par exemple, 1/7 = 0. (142857) a une partie récurrente de 6 chiffres et 1/17 = 0. (0588235294117647) a une partie récurrente de 16 chiffres. La longueur est toujours divise b-1, en fait.)

Voici le code Python utilisé à cette fin, qui s'exécute dans le O (b) time.

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)

Vous pouvez également utiliser un tableau (une liste en Python) de taille b au lieu d'un dictionnaire, ce qui sera légèrement plus rapide (pas en termes d'asymptotique, mais en facteur constant). / p>

Answer 3

Je pense que c'est ce que vous recherchez.

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

Je ne suis pas un expert et je pense que cette solution n'est peut-être pas efficace, mais au moins, c'est facile à faire:

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

Les commentaires sont bien acceptés