Как рассчитать повторяющиеся цифры?

Question

Учитывая два целых числа a и b, как мне рассчитать повторяющийся десятичный знак a / b? Это может быть на любом языке; все, что вам легче выразить.

Answer 1

Вы можете вычислить десятичное представление a / b, используя алгоритм длинного деления, который вы изучили в школе, как сказал Марк Рэнсом. Чтобы вычислить каждую последующую цифру, разделите текущий дивиденд (числитель или остаток) на b и найдите следующий дивиденд как остаток, умноженный на 10 («понижая 0»). Если остаток такой же, как у предыдущего остатка, это означает, что цифры с этого момента будут повторяться, так что вы можете отметить этот факт и остановиться.

Обратите внимание на потенциальную возможность оптимизации: остатки, которые вы получаете при делении на b, находятся в диапазоне от 0 до b-1, поэтому, поскольку вы сохраняете только отличные ненулевые остатки, вам не нужно искать в списке предыдущих Осталось посмотреть, повторяется ли что-нибудь. Таким образом, алгоритм может принимать постоянное время на шаг деления, и достаточно O(b) места. Просто следите за тем, в какой позиции цифр каждый остаток был первым.

(Этот аргумент, кстати, также является математическим доказательством того, что повторяющаяся часть может иметь длину не более b-1 цифр: например, 1/7 = 0. (142857) имеет повторяющуюся часть из 6 цифр и 1/17 = 0. (0588235294117647) имеет повторяющуюся часть из 16 цифр. Длина всегда делит b-1, на самом деле.)

Вот код Python для этого, который выполняется за 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)

Вы также можете использовать массив (список в Python) размером b вместо словаря, который будет немного быстрее (не с точки зрения асимптотики, а с постоянным множителем).

Answer 2

Вы можете сделать это с длинным делением. Вычисляйте одну цифру за раз и вычитайте, чтобы получить остаток, который вы умножаете на 10, чтобы получить числитель для следующего шага. Когда этот новый числитель совпадает с одним из предыдущих числителей, вы знаете, что будете повторять с этого момента. Вам просто нужно сохранить стопку предыдущих числителей и просматривать ее на каждой итерации.

Answer 3

Я думаю, это то, что вы ищете ..

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

Я не эксперт, и я думаю, что это решение может быть неэффективным, но, по крайней мере, это легко сделать:

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

Комментарии хорошо приняты