Найти период дроби

Есть задача: дано число k не делящееся на 2 и 5. Вывести (в виде списка) период дроби 1/k.
В первую очередь меня даже не сама реализация волнует (хотя может на очень понятном примере было бы и лучше), а наиболее понятная интерпретация алгоритма нахождения периода. Сколько не ищу, понятного не попадалось.

0

Сообщение от Moonissia Сколько не ищу, понятного не попадалось.

1, 2, 3

0

Сообщение от Moonissia Есть задача: дано число k не делящееся на 2 и 5. Вывести (в виде списка) период дроби 1/k.

Решить можно несколькими способами.
1) Самый простой, но не всегда верный. Получить double num = 1/(double)k;. Преобразовать в строку и откинуть ведущие нули string str = string.Concat(num.ToString().SkipWhile(c => c == '0' || c = '.'));. И искать в полученной строке период как показал nedel.
Проблема такого способа: не для всех K будет получена верное значение. Для некоторых К период может быть больше мантиссы double. Не проверял, но скорее всего такое будет для int.MaxValue.

2) Программёрский точный способ. Реализуете целочисленное деление со сдвигом на разряд и получением по одному разряду. На каждом шаге получаете очередную цифру частного и остаток для последующего деления. Запоминаете их. Продолжаете до тех пор пока эта пара не повторится. Количество шагов между повтором и есть искомый период.

3) Математический, но не знаю насколько реализуем и не ошибся ли я. Используется то, что периодическая дробь приводится к обыкновенной через дробь вида (цифры периода)|999...99 - где количество девяток равно количеству цифр периода.
Получаем:

Из этого выражения, наш период равен минимальному n при котором (10ⁿ-1)/k - будет целым числом.
Ответ можно искать алгоритмически - это в раздел математики.
Или программёрски: берём n с инкриментом на каждом шаге и проверяем остаток от деления (10ⁿ-1) на k.
Скорее всего придётся использовать BigInteger.

Добавлено через 7 минут
Пример.
Для к=7 минимальное n = 6: 999'999/7 = 142'857.0
Значит период - шесть.

0