Come calcolare le cifre ricorrenti?

Question

Dati due numeri interi a e b , come farei per calcolare il decimale ripetuto di a / b ? Questo può essere in qualsiasi lingua; qualunque cosa sia più facile per te esprimerlo.

Answer 1

Puoi farlo con una divisione lunga. Calcola una singola cifra alla volta e sottrai per ottenere un resto, che moltiplichi per 10 per ottenere il numeratore per il passaggio successivo. Quando questo nuovo numeratore corrisponde a uno dei numeratori precedenti, sai che ripeterai da quel punto in avanti. Devi solo tenere una pila di numeratori precedenti e cercarla attraverso ogni iterazione.

Answer 2

Puoi calcolare la rappresentazione decimale di a / b usando l'algoritmo a divisione lunga che hai imparato a scuola, come diceva Mark Ransom. Per calcolare ogni cifra successiva, dividi il dividendo corrente (numeratore o resto) per b , e trova il dividendo successivo come il resto moltiplicato per 10 ("portando giù uno 0"). Quando un resto è uguale a un resto precedente, significa che anche le cifre da allora in poi si ripeteranno, quindi puoi notare questo fatto e fermarti.

Nota qui il potenziale per un'ottimizzazione: i resti che ottieni quando dividi per b sono nell'intervallo da 0 a b-1, quindi man mano che resti solo distinti diversi da zero, non devi cercare nell'elenco dei precedenti resti per vedere se qualcosa si ripete. Pertanto, è possibile creare un algoritmo che richiede tempo costante per fase di divisione e lo spazio O (b) è sufficiente. Tieni traccia della posizione della cifra in cui si è verificato per la prima volta ogni resto.

(Questo argomento, a proposito, è anche una prova matematica che la parte ricorrente può essere lunga al massimo da b-1 cifre: ad es. 1/7 = 0. (142857) ha una parte ricorrente di 6 cifre e 1/17 = 0. (0588235294117647) ha una parte ricorrente di 16 cifre. La lunghezza divide sempre b-1, in realtà.

Ecco il codice Python per farlo, che viene eseguito in 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)

Puoi anche usare un array (un elenco in Python) di dimensioni b invece di un dizionario, che sarà leggermente più veloce (non in termini di asintotici, ma nel fattore costante).

/ p>

Answer 3

Penso che questo sia quello che stai cercando ..

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

Non sono un esperto e penso che questa soluzione potrebbe non essere efficiente, ma almeno è facile da fare:

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

I commenti sono ben accetti