Как рассчитать повторяющиеся цифры?
-
05-07-2019 - |
Вопрос
Учитывая два целых числа a
и b
, как мне рассчитать повторяющийся десятичный код a / b
? Это может быть на любом языке; все, что вам легче выразить.
Решение
Вы можете сделать это с длинным делением. Вычисляйте одну цифру за раз и вычитайте, чтобы получить остаток, который вы умножаете на 10, чтобы получить числитель для следующего шага. Когда этот новый числитель совпадает с одним из предыдущих числителей, вы знаете, что будете повторять с этого момента. Вам просто нужно сохранить стек предыдущих числителей и просматривать его на каждой итерации.
Другие советы
Вы можете вычислить десятичное представление 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
, который будет немного быстрее (не с точки зрения асимптотики, а с помощью постоянного фактора). р>
Я думаю, это то, что вы ищете ..
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;
}
Я не эксперт, и я думаю, что это решение может быть неэффективным, но, по крайней мере, это легко сделать:
#you want to get a/b
from fractions import Fraction:
print float(Fraction(a,b))
Комментарии хорошо принимаются