Wie berechnen Digits Recurring?

Question

Bei zwei ganzen Zahlen a und b, wie würde ich mich über die sich wiederholende dezimal von a / b Berechnung? Dies kann in jeder Sprache sein; was auch immer es ist am einfachsten für Sie es in auszudrücken.

Answer 1

Sie können es mit langer Teilung tun. Berechnen Sie eine einzelne Ziffer zu einer Zeit und subtrahieren einen Rest zu erhalten, die Sie mit 10 multiplizieren, um den Zähler für den nächsten Schritt zu erhalten. Wenn diese neuen Zähler einer der vorherigen Zähler übereinstimmt, wissen Sie, Sie von diesem Zeitpunkt an wiederholen fahren. Sie müssen nur einen Stapel von vorherigen Numeratoren zu halten und bei jeder Iteration durch sie suchen.

Answer 2

Sie können die Dezimaldarstellung a / b berechnen die Lang Divisions-Algorithmus verwenden Sie in der Schule gelernt, wie Mark Ransom sagte. Um jeden aufeinanderfolgenden Ziffern zu berechnen, die aktuelle Dividende Divide (Zähler oder Rest) durch b und finde die nächste Ausschüttung als Rest, multipliziert mit 10 ( „bringt eine 0 down“). Wenn ein Rest gleich wie ein früherer Rest ist, bedeutet dies, dass die Ziffern von dann auf und wiederholen, so können Sie diese Tatsache beachten und stoppen.

Beachten Sie das Potenzial für eine Optimierung hier: die Reste erhalten Sie, wenn von b im Bereich von 0 bis b-1 unterteilt, so wie Sie nur verschiedene Nicht-Null-Reste halten, die Sie nicht durch die Liste früherer haben suchen Reste zu sehen, ob etwas wiederholt. So kann der Algorithmus vorgenommen werden konstante Zeit pro Teilungsschritt zu nehmen, und O(b) Raum ist genug. Halten Sie einfach den Überblick über welche Stellenposition jeden Rest zuerst bei aufgetreten.

(Dieses Argument, BTW, ist auch ein mathematischer Beweis, daß der sich wiederholende Teil höchstens B-1 Ziffern lang sein kann: zB 1/7 = 0 (142857) einen wiederkehrenden Teil von 6 Ziffern und 1/17. = 0. (0588235294117647) einen wiederkehrenden Teil 16 Ziffern. Die Länge immer dividieren b-1, eigentlich.)

Hier ist Python-Code, dies zu tun, die in O(b) Zeit abläuft.

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)

Sie können auch ein Array (eine Liste in Python) der Größe b anstelle eines Wörterbuchs verwendet werden, die schneller leicht sein wird (nicht in Bezug auf Asymptotiken, aber in der konstanten Faktor).

Answer 3

Ich denke, das ist das, was Sie suchen ..

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

Ich bin kein Experte, und ich denke, diese Lösung kann nicht effizient sein, aber zumindest ist es einfach zu tun:

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

Kommentare sind gut akzeptiert