Как найти период числа python - Исправление недочетов и поиск решений вместе с Examum.ru

Для поиска периода рационального числа существует отдельный алгоритм. Перебираем одну за другой степени числа 10: 10, 100, 1000, 10000 и т.д. Смотрим на остаток от деления этого числа на знаменатель. Если остаток от деления равняется 1, значит степень числа 10, это длина периода. Например, если в знаменателе стоит 13, то:

10 % 13 = 10
100 % 13 = 9
1000 % 13 = 12
10000 % 13 = 3
100000 % 13 = 4
1000000 % 13 = 1

Получается, период равен 6. Этот период не зависит от того, что стоит в числителе (если дробь сокращена).

Метод не работает, если знаменатель делится на 5 или 2. В таком случае его нужно делить на 2, или 5, пока получится число, которое не делится на 2, 5.

В общем случае (как для вашего примера 1/117), придется использовать длинную арифметику.

Алгоритм ищет только длину периода, что бы получить сам период, нужно делить самому.

Источник

Doing print ("repeated numbers:", t) prints the representation of the t function itself, not its output.

Here’s a repaired version of your code. I use a Python 3.6+ f-string to convert the repeating digits to a string, and add zeros to the front to make it the correct length.

def find_period(n, d):
    z = x = n * 9
    k = 1
    while z % d:
        z = z * 10 + x
        k += 1

    digits = f"{z // d:0{k}}"
    return k, digits

# Test

num, den = 1, 7
period, digits = find_period(num, den)
print('num:', num, 'den:', den, 'period:', period, 'digits:', digits)

num, den = 1, 17
period, digits = find_period(num, den)
print('num:', num, 'den:', den, 'period:', period, 'digits:', digits)

output

num: 1 den: 7 period: 6 digits: 142857
num: 1 den: 17 period: 16 digits: 0588235294117647

This line may be a bit mysterious:

f"{z // d:0{k}}"

It says: Find the largest integer less than or equal to z divided by d, convert it to a string, and pad it on the left with zeroes (if necessary) to give it a length of k.

As Goyo points out in the comments, this algorithm is not perfect. It gets stuck in a loop if the decimal contains any non-repeating part, that is, if the denominator has any factors of 2 or 5. See if you can figure out a way to deal with that.

Источник

0 / 0 / 0

Регистрация: 03.11.2019

Сообщений: 36

Период у дроби

14.11.2019, 18:02. Показов 14229. Ответов 7

Найти период бесконечной периодической дроби. Если десятичная дробь конечна, её период — цифра 0.
Период должен начинаться с той цифры, которая является первой повторяющейся при выписывании бесконечной десятичной дроби.

Пример 1
Ввод
11
Вывод
09
Пример 2
Ввод
15
Вывод
6

grizlik78

2378 / 1662 / 279

Регистрация: 29.05.2011

Сообщений: 3,395

14.11.2019, 18:54

Возможно есть хитрые, красивые и эффективные алгоритмы, я же просто реализовал деление «уголком».

Python

n = int(input())
 
first_pos = {}
position = 0
period = ""
remainder = 1
 
while not (remainder in first_pos):
    first_pos[remainder] = position
    period += str(remainder // n)
    remainder = (remainder % n) * 10
    position += 1
    
period = period[first_pos[remainder]:]
 
print(period)

0 / 0 / 0

Регистрация: 03.11.2019

Сообщений: 36

14.11.2019, 20:31

[ТС]

grizlik78, тут нужно списки использовать, можете сказать что означает first_pos = {}?

grizlik78

2378 / 1662 / 279

Регистрация: 29.05.2011

Сообщений: 3,395

14.11.2019, 20:38

Это словарь. dict. В принципе, заменить списком не сложно, хотя эффективность ещё снизится.

Добавлено через 3 минуты

Python

n = int(input())
 
remainders = []
period = ""
remainder = 1
 
while not (remainder in remainders):
    remainders.append(remainder)
    period += str(remainder // n)
    remainder = (remainder % n) * 10
    
period = period[remainders.index(remainder):]
 
print(period)

0 / 0 / 0

Регистрация: 03.11.2019

Сообщений: 36

14.11.2019, 21:02

[ТС]

grizlik78, period = period[remainders.index(remainder):] как эту строчку без индекса переписать?

2378 / 1662 / 279

Регистрация: 29.05.2011

Сообщений: 3,395

14.11.2019, 21:05

Реализовать циклом. index() возвращает индекс первого вхождения заданного элемента в список. То есть в цикле надо перебирать элементы списка, пока не встретится заданный. Его номер в списке и есть искомый индекс.

Snaces

0 / 0 / 0

Регистрация: 03.11.2019

Сообщений: 36

14.11.2019, 21:14

[ТС]

grizlik78,
переписал вот так вроде: Но выводит 006 вместо 6 и 009 вместо 09. Как исправить?

Python

n = int(input())
 
remainders = []
period = ""
remainder = 1
 
while not (remainder in remainders):
    remainders.append(remainder)
    period += str(remainder // n)
    remainder = (remainder % n) * 10
 
for i in remainders:
    if i == remainder:
        break
 
print(period)

grizlik78

2378 / 1662 / 279

Регистрация: 29.05.2011

Сообщений: 3,395

14.11.2019, 21:29

Это потому, что надо найти номер элемента, а не там элемент. А потом ещё и использовать его.

Python

n = int(input())
 
remainders = []
period = ""
remainder = 1
 
while not (remainder in remainders):
    remainders.append(remainder)
    period += str(remainder // n)
    remainder = (remainder % n) * 10
 
start_pos = 0
for i in remainders:
    if i == remainder:
        break
    start_pos += 1
 
print(period[start_pos:])

Источник

10 % 13 = 10
100 % 13 = 9
1000 % 13 = 12
10000 % 13 = 3
100000 % 13 = 4
1000000 % 13 = 1

Получается, период равен 6. Этот период не зависит от того, что стоит в числителе (если дробь сокращена).

В общем случае (как для вашего примера 1/117), придется использовать длинную арифметику.

Алгоритм ищет только длину периода, что бы получить сам период, нужно делить самому.

Источник

Это очень просто

Время на прочтение
2 мин

Количество просмотров 19K

Рассмотрим следующую задачу. Найти период дроби 1/81. Уверяю, что для решения не потребуется ни калькулятор, ни деление столбиком. Для начала вспомним чему равно 81*(Период). Пусть длина периода n, тогда исходная дробь запишется как:

$frac{1}p=frac{Период}{10^n}+frac{Период}{10^{2n}}+frac{Период}{10^{3n}}+...$

Перепишем данное представление в следующем виде:

$frac{1}p=frac{Период}{10^n}+frac{1}{10^n} cdotleft(frac{Период}{10^{n}}+frac{Период}{10^{2n}}+..right)$

Последнее выражение можно представить так:

$frac{1}p=frac{Период}{10^n}+frac{1}{10^n} cdotfrac{1}p$

Ну а теперь то соотношение, которое мы искали:

Для нашего случая это тождество будет следующим:

Разделим левую и правую часть на 9, получим:

Первое число, составленное из одних единиц, которое делится на 9 равно 111111111, это следует из признака делимости на 9. Делить будем через сумму цифр исходного числа. Двигаемся слева направо, складываем цифры делимого и на каждом шаге записываем полученную сумму. Результат работы данного алгоритма — число 12345678,9999… Здесь надо пояснить, что когда мы достигаем крайней правой цифры, то ставим запятую и полученную сумму цифр исходного числа дублируем как бесконечную десятичную дробь. Вспоминаем, что 0,999…=1 и получаем ответ, который мы искали 12345679. Если рассмотреть более общую задачу нахождения периода дроби $frac{1}{9^n}$ , то окажется, что период такой дроби имеет длину ${9^{n-1}}$ и если известен период для случая n-1, то следующий равен произведению данного периода на число вида 11111… (повторяется ${9^{n-1}}$ раз)22222… (повторяется ${9^{n-1}}$ раз)33333… (повторяется ${9^{n-1}}$ раз). Самая правая секция будет иметь вид 8888..889. Последняя цифра девятка.
И еще одно наблюдение, теперь для дробей вида $frac{1}{11^{n}}$ . В этом случае длина периода равна $2cdot{11^{n-1}}$ . И если известен период для случая n-1, то следующий период равен произведению данного периода на число, составленное из 10 блоков, где длина каждого блока $2cdot{11^{n-2}}$ . Блоки имеют следующую структуру:
09090909…
18181818…
27272727…
36363636…
…
последний блок 90909091. Для $frac{1}{11}$ период 09, для $frac{1}{11^{2}}$ период будет 09182736455463728191*9=0082644628099173553719.
Проверил формулу для $frac{1}{11^{3}}$ . Получил

75131480090157776108189331329827197595792637114951164537941397445529676934635612
32156273478587528174305033809166040570999248685199098422238918106686701728024042
0736288504883546205860255447032306536438767843726521412471825694966190833959429,

что совпадает с периодом без ведущих нулей.

Приведу код процедур, которые я использовал для проверки своих выводов.

Function GreatestCommonDivisor(x,y)

    if x=y then
        return x;
    endif;  

    a=min(x,y);
    if a=1 then
        return 1;
    endif;  
    b=x+y-a;

    while TRUE do
     c=b%a; 
     if c=0 then
         return a;
     endif;  
     b=a;
     a=c;
    enddo;

EndFunction

Function NumeratorFractionPeriod(numerator,denumerator)

    // дробь a/b

    a=numerator;
    b=denumerator;

    while b%2=0 do
        b=b/2;
        a=a*5;
    enddo;  

    while b%5=0 do
        b=b/5;
        a=a*2;
    enddo;  
    //наибольший общий делитель
    c=GreatestCommonDivisor(a,b);
    a=a/c;
    b=b/c;

    if b=1 then
        Period=string(a);
        return Period;
    endif;

    if a>b then
        Period=string((a-a%b)/b);
        a=a%b;
        if a=0 then
            return Period;
        endif;  
        Period=Period+"(";
    else
        Period="(";
    endif;      

    while a%10=0 do
        a=a/10;
    enddo;  

    i=a;
    while TRUE do
        j=0;
        while i<b do
            i=i*10;
            j=j+1;
            if j>1 then
             Period=Period+"0";
            endif; 
        enddo;  

        check=i-a;
        if (check%b)=0 then
            Period=Period+(check)/b;
            break;
        else
            j=i%b;
            Period=Period+(i-j)/b;
            i=j;
        endif;    
    enddo;

    return Period+")";
EndFunction

Источник