@unit23

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

Суть вопроса в том, что нужно программно определить период периодической дроби и вывести в формате a,(per).
Сложность состоит в том, что система счисления произвольная и выбирается случайно.
И как это можно применить в случае смешанной периодической дроби.
  • Вопрос задан
  • 1200 просмотров
Решения вопроса 1
Mrrl
@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, то период найден.
Есть и другие способы, без использования массивов.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Периодическая дробь в одной системе счисления может быть числом с конечным количеством значащих цифр в другой системе счисления.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы