Jak obliczyć powtarzające się cyfry?

Question

Biorąc pod uwagę dwie liczby całkowite a i b, w jaki sposób powinienem obliczać powtarzający się dziesiętny z a/b? Może to być w dowolnym języku; cokolwiek jest najłatwiejsze do wyrażenia.

Answer 1

Możesz to zrobić z długim podziałem. Oblicz pojedynczą cyfrę na raz i odejmij, aby uzyskać pozostałą liczbę, którą pomnożysz przez 10, aby uzyskać licznik do następnego kroku. Kiedy ten nowy licznik pasuje do jednego z poprzednich liczników, wiesz, że będziesz powtarzać od tego momentu. Trzeba tylko zachować stos poprzednich liczników i przeszukiwać go w każdej iteracji.

Answer 2

Możesz obliczyć dziesiętną reprezentację a/b używając algorytmu długiego dzielenia, którego nauczyłeś się w szkole, jak powiedział Mark Ransom. Aby obliczyć każdą kolejną cyfrę, podziel bieżącą dywidendę (licznik lub pozostałą część) przez b i znajdź następną dywidendę jako pozostałą pomnożoną przez 10 ("obniżenie 0"). Kiedy reszta jest taka sama, jak poprzednia, oznacza to, że cyfry od tej pory również będą się powtarzać, więc możesz zauważyć ten fakt i przestać.

Zwróć uwagę na potencjał optymalizacji: pozostałe, otrzymywane podczas dzielenia przez b, są w zakresie od 0 do b-1, więc zachowujesz tylko różne niezerowe pozostałości, nie musisz przeszukiwać listy poprzednie resztki, aby zobaczyć, czy coś się powtarza. Tak więc algorytm może być ustawiony na ciągły czas na podział, a przestrzeń jest wystarczająca. Po prostu śledź pozycję cyfry, w której pojawiła się pierwsza reszta.

(Ten argument, BTW, jest również dowodem matematycznym, że część cykliczna może mieć co najwyżej b-1 cyfry: np. 1/7 = 0. (142857) ma powtarzającą się część składającą się z 6 cyfr i 1/17 = 0. (0588235294117647) ma powtarzające część 16 cyfr. długość zawsze dzieli B-1, faktycznie.)

Oto kod Pythona dla tej operacji, która biegnie w O(b) czasie.

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) 

Można również używać tablicy (lista w Pythonie) w rozmiarze b zamiast słownika, który będzie nieco szybciej (nie w kategoriach asymptotyka, ale w stały współczynnik).

Answer 3

myślę, że to jest to, czego szukasz ..

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

Nie jestem ekspertem, i myślę, że to rozwiązanie nie może być skuteczny, ale przynajmniej jest to łatwe do zrobienia:

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

Komentarze są dobrze akceptowane