Признаки переодичности дроби в произвольной системе счисления?

Question

[unit23]

Суть вопроса в том, что нужно программно определить период периодической дроби и вывести в формате a,(per).
Сложность состоит в том, что система счисления произвольная и выбирается случайно.
И как это можно применить в случае смешанной периодической дроби.

Answer 1

[Mrrl]

Когда вы строите дробь a/b, у вас есть последовательность остатков:
a_0=a%b, a_1=(a_0*p)%b, a_2=(a_1*p)%b,... где p - основание системы счисления. Как только два остатка a_x и a_y совпали - все цифры между ними ((a_x*p)/b, (a_{x+1}*p)/b,...,(a_{y-1}*p)/b) образуют период. Как эффективно найти период такой последовательности - ищите. При небольших b достаточно взять массив M с индексами от 0 до b-1, и для каждого вычисленного остатка проверять ячейку M[a_y]. Если в неё ещё ничего не записали, записать M[a_y]=y. Если там лежит какой-то x, то период найден.
Есть и другие способы, без использования массивов.

Answer 2

[Максим Мосейчук]

Периодическая дробь в одной системе счисления может быть числом с конечным количеством значащих цифр в другой системе счисления.

Дробь дана обыкновенная? Т.е. отношение двух чисел? Тогда всё легко. Возьмём к примеру 4/3 в десятичной системе счисления.
Находим остаток от деления числителя на знаменатель - 4 % 3 = 1. Это число у нас будет выступать в качестве начального значения.
1) Сохраняем остаток в массиве. Умножаем остаток (массив не трогаем) на основание системы счисления (у нас десятичная) - 1*10 = 10
2) Находим остаток от деления числа с шага [1] на знаменатель - 10 % 3 = 1
3) Если он равен нулю, то дробь конечная. Иначе ищем остаток в массиве. Если нашли, то мы нашли период. Иначе берём текущий остаток и переходим к шагу [1].

Comments

[Mrrl]

Не пройдёт. В случае 1/12 в десятичной системе остатки будут 1,10,4,4,4... и никогда не будет остатка, равного первому.

[Максим Мосейчук]

Mrrl: вы правы. Я не учёл, что период не обязательно начинается сразу после запятой. Тогда нужно просто хранить все промежуточные остатки и искать в них очередной.

[Олег Цилюрик]

fshp: почему такой упор на остатки? точно также можно сравнивать на совпадения частные от деления - если есть повтор с некоторым предыдущим, то это - период.

[Олег Цилюрик]

Mrrl: непонятно как это в десятичной системе остаток может быть 10? (2-й в вашем ряду)

[Mrrl]

Олег Цилюрик: Остаток идёт от деления на знаменатель, т.е. на 12. Если мы будем делить 1 на 997 в столбик, то в какой-то момент увидим слева 996 (которое тут же превратится в 9960).

[Максим Мосейчук]

Олег Цилюрик: Эмм. 4/5 и 3/5 имеют одинаковые частные, но разные остатки.