Как найти период дроби 1/N?
Вот примеры ввода и вывода:
input: 3 output: 3
input: 5 output: 0
input: 7 output: 142857
Ответы (5 шт):
Да алгоритм-то не слишком сложный.
Пока N делится на 2, делим на 2
Пока N делится на 5, делим на 5
Если получилось 1, период 0 - дробь непериодична.
Иначе у неё есть период p, и она может быть записана в виде (упрощённо, после точки ещё непериодичная часть может быть, пример для p=6)
0.abcdefabcdefabcdef...
Если это умножить на 10^p, то получится
abcdef.abcdefabcdefabcdef... (точка после p цифр)
Если из второго вычесть первое, то получится целое abcdef
1/N * 10^p - 1/N = 1/N * (10^p-1)
Последнее выражение - целое число, значит (10^p-1) делится на N
Вот и ищем такое p, чтобы ((10^p-1) % N) == 0
function solve(n) {
var used = Array(n)
var res = []
var x = 1
for (var q=0; !used[x]; ++q) {
used[x] = q
res.push(x / n | 0)
x %= n
x *= 10
}
return res.slice(used[x]).join("")
}
console.log(solve(3))
console.log(solve(5))
console.log(solve(7))
console.log(solve(6))
console.log(solve(999999999))Есть интересный алгоритм, я использовал его для поиска циклов. Не использует дополнительную память, скорость O(N). Никаких квадратичных сложностей при больших числах. Как посоветовал Stanislav Volodarskiy можно найти первоначальную точку входа в цикл (если надо).
// gcc -Wall -Wextra period.c -o period && ./period
# include <stdio.h>
int main(){
unsigned int const arr [ ] = {2,3,11,13,14,17,19,23};
for ( unsigned int const * i = arr ;i < * ( ( & arr ) + 1 ) ;++i){
unsigned int n = *i ;
printf ("1/%u = ",n);
unsigned int n10 = 1U ;
unsigned int n100 = 1U ;
// I. ищем факт цикла
do {
n10 = ( n10 * 10U ) % n ;
// ( ( ( n100 * 10U ) % n ) * 10U ) % n == ( n100 * 100U ) % n
n100 = ( n100 * 100U ) % n ;
if ( n100 == 0U ) {
printf("0");
goto cont ; }
} while ( n10 != n100 ) ;
// II. проходим число с начала на дистанцию
// размера цикла ( опционально )
n100 = 1U ;
{ unsigned int nstart = n10 ;
do {
n10 = ( n10 * 10 ) % n ;
n100 = ( n100 * 10 ) % n ;
} while ( n10 != nstart ) ; }
// III. Ищем первоначальную точку входа в цикл
// ( опционально )
n10 = 1U ;
while ( n10 != n100 ) {
n10 = ( n10 * 10 ) % n ;
n100 = ( n100 * 10 ) % n ; }
// IV. Печатаем
{ unsigned int nstart = n10 ;
do {
printf("%u",(n10 * 10) / n);
n10 = ( n10 * 10 ) % n ;
} while ( n10 != nstart ) ; }
cont :
printf("\n");
}
}
результат :
1/2 = 0
1/3 = 3
1/11 = 09
1/13 = 076923
1/14 = 714285
1/17 = 0588235294117647
1/19 = 052631578947368421
1/23 = 0434782608695652173913
Задача состоит из двух частей. Сначала нужно найти длину периода, затем вычислить периодическую часть дроби 2^a / n или 5^a / n.
Вычисление длины периода описал @Mbo. Сначала убираем из n все делители, кратные 2 и 5, затем перебором ищем такое N, что 10^N mod n == 1.
typedef struct {
int n; // Приведённое число
int pwr2; // Степень двойки в исходном числе
int pwr5; // Степень пятёрки в исходном числе
} strip_2_5_res_t;
// Приведение числа.
// Возвращает число, полученное из n делением на число, кратное 2 и 5,
// а также степени 2 5 в исходном числе.
strip_2_5_res_t strip_2_5(int n) {
strip_2_5_res_t result = {0,0,0};
if (n == 0) { return result; }
if (n < 0) { n = -n; }
while (n % 2 == 0) {
n /= 2;
result.pwr2++;
}
while (n % 5 == 0) {
n /= 5;
result.pwr5++;
}
result.n = n;
return result;
}
// Возвращает длину периода.
// "Период дроби" переводится как "repetend", поэтому функция называется repetend_len
// Число n должно быть приведено!
int repetend_len(int n) {
if (n == 0 || n == 1) {
return 0;
}
int l = 0;
int q = 10;
l = 1;
while (q%n != 1) {
l++;
q = (10*q) % n;
}
return l;
}
Вторая часть - вычисление собственно периода.
Если число n не делится ни на 2, ни на 5, то всё просто. Для этого достаточно возвести 10 в степень p (длина периода), вычесть единичку и поделить на n.
Чуть хитрее дело обстоит с числами, которые кратны 2 или 5. Представим их как произведение степени 10, поделённой на степень 2 или 5, и приведённого числа.
Например, 60 = (10^2 / 5^1) * 3, а 350 = (10^2 / 2^1) * 7
Другими словами, n = (10^x / factor) * n_reduced,
где factor или равен единице, или делится либо только на 2, либо только на 5, а n_reduced - это приведённое число.
Тогда периодом дроби 1/n будет период дроби factor/n_reduced - множитель 10^x всего лишь добавит нулей в начало записи дроби.
Например, у дроби 1/60 период совпадает с периодом дроби 5/3, а у дроби 1/350 с периодом дроби 2/7. То есть период равен
factor*(10^p - 1) / n_reduced
Здесь p - длина периода.
Основная хитрость в том, что для вычисления периода целочисленной арифметикой пользоваться нельзя. Даже у сравнительно небольших n период дроби может оказаться гораздо больше 64-х. Первое такое число 97, у него период дроби равен 96. Понятное дело, 10^96-1 не влезет в 64-х битный long long. Даже если вы возьмёте 128-битную арифметику, то легко найти пример, который в неё не влезет. Например, у дроби 1/65537 длина периода равна 65536.
Лирическое замечание. Длина периода является одним из делителей числа fi(n), где fi - функция Эйлера. Если n - простое число, то длина периода может оказаться равной n-1. В первой сотне таких чисел 9: 7, 17, 19, 23, 29, 47, 59, 61, 97.
Поэтому делить нужно столбиком, результат возвращать в виде строки.
// Для malloc
#include <stdlib.h>
// Возвращает дробную часть числа m/n.
// Предполагается, что число n уже приведено, и вычислен период дроби.
// Предполагается, что n > 1, m > 0.
// Возвращается указатель на строку, аллоцированную в куче. Строку необходимо free после использования.
char* m_div_n_frac(int m, int n, int len) {
char * result;
int q0 = m%n;
int q = q0;
int i = 0;
result = malloc(len+1);
while (i < len) {
int digit = (q*10) / n;
result[i++] = digit + '0';
q = (q*10) % n;
if (q == q0) {
break;
}
}
result[i] = '\0';
return result;
}
Теперь, имея на руках функции для вычисления длины периода, и функцию деления столбиком, можно вычислить период.
// Возвращает период дробной части числа 1/n.
// Возвращается указатель на строку, аллоцированную в куче. Строку необходимо free после использования.
char * repetend(int n) {
strip_2_5_res_t r = strip_2_5(n);
int m = r.n;
int l = repetend_len(m);
if (l == 0) {
char * result = malloc(2);
result[0] = '0';
result[1] = '\0';
return result;
}
int maxpwr = (r.pwr2 > r.pwr5) ? r.pwr2 : r.pwr5;
int factor = 1;
for (int i = r.pwr2; i < maxpwr; i++) { factor *= 2; }
for (int i = r.pwr5; i < maxpwr; i++) { factor *= 5; }
return m_div_n_frac(factor, m, l);
}
Для тестирования я использовал вот такой main.
#include <stdio.h>
// Для strlen
#include <string.h>
void report(int n) {
char * result = repetend(n);
int l = strlen(result);
// Если дробь конечная, то для неё возвращается строка "0"
if (l == 1 && result[0] == '0') { l = 0; }
printf("N: %d, repetend length: %d, repetend: '%s'\n", n, l, result);
free(result);
}
int main(int arc, char ** argv) {
report(60);
report(350);
report(2);
report(3);
report(4);
report(5);
report(6);
report(7);
report(8);
report(9);
report(11);
report(13);
report(15);
report(17);
report(19);
report(97);
report(12321);
// Если хотите посмотреть на дробь длиной 65536 знаков, раскомментируйте
// report(65537);
}
Результат таков:
N: 60, repetend length: 1, repetend: '6'
N: 350, repetend length: 6, repetend: '285714'
N: 2, repetend length: 0, repetend: '0'
N: 3, repetend length: 1, repetend: '3'
N: 4, repetend length: 0, repetend: '0'
N: 5, repetend length: 0, repetend: '0'
N: 6, repetend length: 1, repetend: '6'
N: 7, repetend length: 6, repetend: '142857'
N: 8, repetend length: 0, repetend: '0'
N: 9, repetend length: 1, repetend: '1'
N: 11, repetend length: 2, repetend: '09'
N: 13, repetend length: 6, repetend: '076923'
N: 15, repetend length: 1, repetend: '6'
N: 17, repetend length: 16, repetend: '0588235294117647'
N: 19, repetend length: 18, repetend: '052631578947368421'
N: 97, repetend length: 96, repetend: '010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567'
N: 12321, repetend length: 111, repetend: '000081162243324405486567648729810891973054135216297378459540621702783864946027108189270351432513594675756837919'
Так как решение на C, желательно сделать его оптимальным по скорости и по памяти. Ещё нужно принять во внимание ограниченность целого типа. К счастью, задача хорошо соответствует выразительным способностям языка.
Хотя в вопросе просили печатать цикл дроби 1/n, здесь показано как полностью напечатать любую дробь вида m/n. Объём вычислений и сложность решения почти одинаковы для обоих задач.
В дальнейшем знак // обозначает деление нацело.
Целая часть числа равна m // n. Остаток от деления r = m % n образует правильную дробь r/n - дробную часть.
Алгоритм печати дробной части основан на школьном алгоритме деления.
В цикле печатаем цифры дробной части: очередная цифра d = 10 * r // n, очередной остаток r = 10 * r % n.
Дробная часть состоит из префикса и цикла. Префикс может быть любой длины, может быть и пустым. Цикл всегда не пустой.
Цикл отыскивается алгоритмом Флойда: черепаха шагает на одну цифру, заяц скачет на две. Когда остатки у черепахи и зайца совпали, мы в цикле.
Для определения длины цикла стартуем с найденного остатка из цикла, считаем шаги до получения того же остатка.
Чтобы отыскать начало цикла одну черепаху ставим в начало дроби, вторую продвигаем вперед на длину цикла. Черепахи шагают на один шаг синхронно. Первое совпадение остатков означает что первая черепаха в начале цикла.
Зная длину префикса (совпадает с началом цикла) и длину цикла можно напечатать дробь в формате 69/28 = 2.46(428571).
Алгоритм не использует длинную арифметику и работает в константной памяти. Время работы пропорционально размеру результата. Константу можно улучшить, но уже в ущерб простоте решения. Знаменатель должен без переполнения умножаться на 10.
// gcc -Wall -Wextra -std=c99 print_fraction.c
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
// отыскивает какой-нибудь остаток из циклической части правильной дроби m/n
long reminder_in_loop(long m, long n) {
assert(m < n);
// алгоритм Флойда: https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%85%D0%BE%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0#%D0%A7%D0%B5%D1%80%D0%B5%D0%BF%D0%B0%D1%85%D0%B0_%D0%B8_%D0%B7%D0%B0%D1%8F%D1%86
// когда оба остатка попадут на цикл и расстояние станет кратно длине цикла, остатки совпадут
long r1 = m;
long r2 = m;
for (; ; ) {
r1 = 10 * r1 % n;
// тоже самое что и 100 * r2 % n, но реже переполняется
r2 = 10 * (10 * r2 % n) % n;
if (r1 == r2) {
return r1;
}
}
}
// вычисляет длину циклической части правильной дроби m/n
long loop_length(long m, long n) {
// любой остаток из циклической части
long r1 = reminder_in_loop(m, n);
// бежим дальше, считаем шаги до момента когда остаток повторится
long r2 = r1;
for (long i = 1; ; ++i) {
r2 = 10 * r2 % n;
if (r2 == r1) {
return i;
}
}
}
// вычисляет начало циклической части правильной дроби m/n
// ll должно быть равно loop_length(m, n)
long loop_start(long m, long n, long ll) {
long r1 = m;
// отступаем на длину цикла
long r2 = m;
for (long i = 0; i < ll; ++i) {
r2 = 10 * r2 % n;
}
// синхронно сдвигаем остатки, считаем шаги до момента когда они совпадут
for (long i = 0; ; ++i) {
if (r1 == r2) {
return i;
}
r1 = 10 * r1 % n;
r2 = 10 * r2 % n;
}
}
// печатает n_digits цифр правильной дроби m/n
// возвращает остаток для продолжения печати дроби
long print_digits(FILE *f, long m, long n, long n_digits) {
long r = m;
for (long i = 0; i < n_digits; ++i) {
fprintf(f, "%ld", 10 * r / n);
r = 10 * r % n;
}
return r;
}
// печатает дробь m/n
void print_decimal_fraction(FILE *f, long m, long n) {
// печатаем целую часть
fprintf(f, "%ld", m / n);
// получаем правильную дробь r/n
long r = m % n;
// печатаем дробную часть
if (r != 0) {
fputc('.', f);
// параметры цикла - длина и начало
long ll = loop_length(r, n);
long ls = loop_start(r, n, ll);
// печатаем цифры дробной части до начала цикла
r = print_digits(f, r, n, ls);
// печатаем цифры цикла в скобках
if (r != 0) {
fputc('(', f);
print_digits(f, r, n, ll);
fputc(')', f);
}
}
}
int main(int argc, char **argv) {
assert(argc == 3);
long m = strtol(argv[1], NULL, 10);
long n = strtol(argv[2], NULL, 10);
assert(0 <= m);
assert(n <= LONG_MAX / 10 + 1);
print_decimal_fraction(stdout, m, n);
puts("");
}