Как узнать повторяющуюся десятичную дробь?

Ответ 1

Очень простой алгоритм: реализовать длинное деление. Запишите каждое промежуточное подразделение, которое вы делаете. Как только вы увидите разделение, идентичное тому, которое вы делали раньше, у вас есть то, что повторяется.

Пример: 7/13.

1. 13 goes into   7 0 times with remainder  7; bring down a 0.
2. 13 goes into  70 5 times with remainder  5; bring down a 0.
3. 13 goes into  50 3 times with remainder 11; bring down a 0.
4. 13 goes into 110 8 times with remainder  6; bring down a 0.
5. 13 goes into  60 4 times with remainder  8; bring down a 0.
6. 13 goes into  80 6 times with remainder  2; bring down a 0.
7. 13 goes into  20 1 time  with remainder  7; bring down a 0.
8. We have already seen 13/70 on line 2; so lines 2-7 have the repeating part

Алгоритм дает нам 538461 как повторяющуюся часть. Мой калькулятор говорит, 7/13 - 0.538461538. Смотрит прямо на меня! Все, что осталось, это детали реализации или найти лучший алгоритм!

Ответ 2

Если у вас есть (положительная) сокращенная дробь numerator / denominator, десятичное разложение фракции заканчивается тогда и только тогда, когда denominator не имеет простого множителя, отличного от 2 или 5. Если у него есть любой другой простой коэффициент, десятичная расширение будет периодическим. Тем не менее, случаи, когда знаменатель делится хотя бы на один из 2 и 5, и где он не приводит к слегка отличающемуся поведению. У нас есть три случая:

• denominator = 2^a * 5^b, то десятичное расширение завершает цифру max {a, b} после десятичной точки.
• denominator = 2^a * 5^b * m, где m > 1 не делится на 2 или на 5, то дробная часть десятичных разложений состоит из двух частей: предпериода длины max {a, b} и периода, длина которого определяется m и не зависит от числителя.
• denominator > 1 не делится на 2 или на 5, то десятичное разложение является чисто периодическим, т.е. период начинается сразу после десятичной точки.

Обработка случаев 1 и 2. имеет общую часть, пусть c = max {a, b}, то

numerator / denominator = (numerator * 2^(c-a) * 5^(c-b)) / (10^c * m)

где m = 1 для случая 1. Заметим, что один из факторов 2^(c-a) и 5^(c-b) с которым мы умножаем числитель равен 1. Затем вы получаете десятичное расширение, расширяя

(numerator * 2^(c-a) * 5^(c-b)) / m

и сдвигая десятичную точку c влево. В первом случае (m = 1) эта часть тривиальна.

Обработка случаев 2. и 3. также имеет общую часть, вычисление доли

n / m

где n и m не имеют общего простого множителя (и m > 1). Мы можем написать n = q*m + r с 0 <= r < m (деление с остатком, r = n % m), q - неотъемлемая часть фракции и довольно неинтересная.

Поскольку фракция считалась приведенной, имеем r > 0, поэтому мы хотим найти разложение доли r / m, где 0 < r < m и m не делится на 2 или на 5. Как упоминалось выше, такое разложение чисто периодическое, поэтому найти период означает найти полное разложение.

Давайте продолжим поиск эвристического периода. Итак, пусть k - длина (кратчайший) период и p = d_1d1_2...d_k период. Так

r / m = 0.d_1d_2...d_kd_1d_2...d_kd_1...
      = (d_1d_2...d_k)/(10^k) + (d_1d_2...d_k)/(10^(2k)) + (d_1d_2...d_k)/(10^(3k)) + ...
      = p/(10^k) * (1 + 1/(10^k) + 1/(10^(2k)) + 1/(10^(3k)) + ...)

Последний член представляет собой геометрический ряд, 1 + q + q^2 + q^3 + ..., который для |q| < 1 имеет сумму 1/(1-q). В нашем случае 0 < q = 1/(10^k) < 1, поэтому сумма равна 1 / (1 - 1/(10^k)) = 10^k / (10^k-1). Таким образом, мы видели, что

r / m = p / (10^k-1)

Так как r и m не имеют общего коэффициента, это означает, что существует s с 10^k - 1 = s*m и p = s*r. Если мы знаем k, длину периода, мы можем просто найти цифры периода, вычислив

p = ((10^k - 1)/m) * r

и заполнение с ведущими нулями, пока мы не получим цифры k. (Примечание: это просто, только если k достаточно мало или имеется большой целочисленный тип. Чтобы вычислить период, например 17/983, со стандартными целыми типами фиксированной ширины, используйте длинное деление, как объясняется @Patrick87. )

Таким образом, остается найти длину периода. Мы можем отменить рассуждения выше и найти, что если m делит 10^u - 1, тогда мы можем написать

r / m = t/(10^u - 1) = t/(10^u) + t/(10^(2u)) + t/(10^(3u)) + ...
      = 0.t_1t_2...t_ut_1t_2...t_ut_1...

и r/m имеет период длины u. Таким образом, длина самого короткого периода является минимальной положительной u такой, что m делит 10^u - 1 или, другими словами, наименьший положительный u такой, что 10^u % m == 1.

Мы можем найти его в O (m) времени с

u = 0;
a = 1;
do {
    ++u;
    a = (10*a) % m;
while(a != 1);

Теперь поиск длины периода таким образом не эффективнее, чем поиск цифр и длины периода вместе с длинным делением, а для достаточно малого m - наиболее эффективный метод.

int[] long_division(int numerator, int denominator) {
    if (numerator < 1 || numerator >= denominator) throw new IllegalArgumentException("Bad call");
    // now we know 0 < numerator < denominator
    if (denominator % 2 == 0 || denominator % 5 == 0) throw new IllegalArgumentException("Bad denominator");
    // now we know we get a purely periodic expansion
    int[] digits = new int[denominator];
    int k = 0, n = numerator;
    do {
        n *= 10;
        digits[k++] = n / denominator;
        n = n % denominator;
    }while(n != numerator);
    int[] period = new int[k];
    for(n = 0; n < k; ++n) {
        period[n] = digits[n];
    }
    return period;
}

Это работает до тех пор, пока 10*(denominator - 1) не переполняется, конечно int может быть 32-разрядным или 64-разрядным целым по мере необходимости.

Но для больших знаменателей это неэффективно, можно найти длину периода, а также период быстрее, рассматривая простую факторизацию знаменателя. Что касается длины периода,

• Если знаменатель является главной степенью, m = p^k, длина периода r/m является делителем (p-1) * p^(k-1)
• Если a и b являются взаимно простыми и m = a * b, длина периода r/m является наименьшим общим кратным длин периода 1/a и 1/b.

Взятый вместе, длина периода r/m является делителем λ(m), где λ - функция Кармайчеля.

Итак, чтобы найти длину периода r/m, найдите простую факторизацию m и для всех простых степенных коэффициентов p^k, найдите период 1/(p^k) - эквивалентно, мультипликативный порядок 10 по модулю p^k, который, как известно, является делителем (p-1) * p^(k-1). Поскольку у таких чисел не так много делителей, это быстро делается. Затем найдите наименьшее общее кратное из всех этих.

В течение самого периода (цифр), если имеется большой целочисленный тип, и период не слишком длинный, формула

p = (10^k - 1)/m * r

- это быстрый способ его вычисления. Если период слишком длинный или не существует большого целочисленного типа, эффективное вычисление цифр более беспорядочно, и я не знаю, как именно это делается. Я не помню, как именно это делается.

Ответ 3

Одним из способов было бы повторить то, как вы делаете длинное разделение вручную, и обратите внимание на остаток на каждом этапе. Когда остаток повторяется, остальная часть процесса также должна повториться. Например. цифры 1,0/7 составляют 0,1 остатка 3, а затем 0,14 остатка 2, затем 0,142 остатка 6, а затем 0,1428 остатка 4, затем 0,1485 остатка 5, а затем 0,148585 остатка 1, который является 1, который снова запускает его снова, поэтому вы получаете 0,1428571 остаток 3 и снова повторяется оттуда.

Ответ 4

Алгоритм длинного разделения довольно хорош, поэтому мне нечего туда добавлять.

Но обратите внимание, что ваш алгоритм IsRepeatingDecimal может не работать и неэффективен.

Это не сработает, если ваша фракция не является нерушимой, то есть если существует целое число больше единицы, которое делит как ваш числитель, так и ваш знаменатель. Например, если вы подаете 7/14, тогда ваш алгоритм вернет true, когда он вернет false.

Чтобы уменьшить свою долю, найдите gcd между числителем и знаменателем и разделите оба на этот gcd.

Если вы считаете, что фракция неприводима, то ваш тест

if (Numerator % Denominator == 0)

можно просто заменить на

if (Denominator == 1)

Но это по-прежнему не нужно, поскольку если знаменатель равен 1, то ваш список "простых чисел" будет пустым, и ваш алгоритм все равно вернет false.

Наконец, вызов MathAlgorithms.Primes(знаменатель) будет дорогостоящим для больших чисел и его можно избежать. Действительно, все, что вам нужно сделать, это разделить ваш знаменатель на 5 (соответственно 2), пока он больше не делится на 5 (соответственно 2). Если конечный результат равен 1, верните значение false, в противном случае верните true.