Как найти период чисел

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

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

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

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

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

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

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

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

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 

Периодические десятичные дроби

10 февраля 2012

Помните, как в самом первом уроке про десятичные дроби я говорил, что существуют числовые дроби, не представимые в виде десятичных (см. урок «Десятичные дроби»)? Мы еще учились раскладывать знаменатели дробей на множители, чтобы проверить, нет ли там чисел, отличных от 2 и 5.

Так вот: я наврал. И сегодня мы научимся переводить абсолютно любую числовую дробь в десятичную. Заодно познакомимся с целым классом дробей с бесконечной значащей частью.

Периодическая десятичная дробь — это любая десятичная дробь, у которой:

1. Значащая часть состоит из бесконечного количества цифр;
2. Через определенные интервалы цифры в значащей части повторяются.

Набор повторяющихся цифр, из которых состоит значащая часть, называется периодической частью дроби, а количество цифр в этом наборе — периодом дроби. Остальной отрезок значащей части, который не повторяется, называется непериодической частью.

Поскольку определений много, стоит подробно рассмотреть несколько таких дробей:

Эта дробь встречается в задачах чаще всего. Непериодическая часть: 0; периодическая часть: 3; длина периода: 1.

Непериодическая часть: 0,58; периодическая часть: 3; длина периода: снова 1.

Непериодическая часть: 1; периодическая часть: 54; длина периода: 2.

Непериодическая часть: 0; периодическая часть: 641025; длина периода: 6. Для удобства повторяющиеся части отделены друг от друга пробелом — в настоящем решении так делать не обязательно.

Непериодическая часть: 3066; периодическая часть: 6; длина периода: 1.

Как видите, определение периодической дроби основано на понятии значащей части числа. Поэтому если вы забыли что это такое, рекомендую повторить — см. урок «Умножение и деление десятичных дробей».

Переход к периодической десятичной дроби

Рассмотрим обыкновенную дробь вида a/b. Разложим ее знаменатель на простые множители. Возможны два варианта:

1. В разложении присутствуют только множители 2 и 5. Эти дроби легко приводятся к десятичным — см. урок «Десятичные дроби». Такие нас не интересуют;
2. В разложении присутствует что-то еще, кроме 2 и 5. В этом случае дробь непредставима в виде десятичной, зато из нее можно сделать периодическую десятичную дробь.

Чтобы задать периодическую десятичную дробь, надо найти ее периодическую и непериодическую часть. Как? Переведите дробь в неправильную, а затем разделите числитель на знаменатель «уголком».

При этом будет происходить следующее:

1. Сначала разделится целая часть, если она есть;
2. Возможно, будет несколько чисел после десятичной точки;
3. Через некоторое время цифры начнут повторяться.

Вот и все! Повторяющиеся цифры после десятичной точки обозначаем периодической частью, а то, что стоит спереди — непериодической.

Задача. Переведите обыкновенные дроби в периодические десятичные:

Все дроби без целой части, поэтому просто делим числитель на знаменатель «уголком»:

Как видим, остатки повторяются. Запишем дробь в «правильном» виде: 1,733 … = 1,7(3).

В итоге получается дробь: 0,5833 … = 0,58(3).

Записываем в нормальном виде: 4,0909 … = 4,(09).

Получаем дробь: 0,4141 … = 0,(41).

Переход от периодической десятичной дроби к обыкновенной

Рассмотрим периодическую десятичную дробь X = abc(a₁b₁c₁). Требуется перевести ее в классическую «двухэтажную». Для этого выполним четыре простых шага:

1. Найдите период дроби, т.е. подсчитайте, сколько цифр находится в периодической части. Пусть это будет число k;
2. Найдите значение выражения X · 10^k. Это равносильно сдвигу десятичной точки на полный период вправо — см. урок «Умножение и деление десятичных дробей»;
3. Из полученного числа надо вычесть исходное выражение. При этом периодическая часть «сжигается», и остается обычная дробь;
4. В полученном уравнении найти X. Все десятичные дроби переводим в обыкновенные.

Задача. Приведите к обыкновенной неправильной дроби числа:

• 9,(6);
• 32,(39);
• 0,30(5);
• 0,(2475).

Работаем с первой дробью: X = 9,(6) = 9,666 …

В скобках содержится лишь одна цифра, поэтому период k = 1. Далее умножаем эту дробь на 10^k = 10¹ = 10. Имеем:

10X = 10 · 9,6666 … = 96,666 …

Вычитаем исходную дробь и решаем уравнение:

10X − X = 96,666 … − 9,666 … = 96 − 9 = 87;
9X = 87;
X = 87/9 = 29/3.

Теперь разберемся со второй дробью. Итак, X = 32,(39) = 32,393939 …

Период k = 2, поэтому умножаем все на 10^k = 10² = 100:

100X = 100 · 32,393939 … = 3239,3939 …

Снова вычитаем исходную дробь и решаем уравнение:

100X − X = 3239,3939 … − 32,3939 … = 3239 − 32 = 3207;
99X = 3207;
X = 3207/99 = 1069/33.

Приступаем к третьей дроби: X = 0,30(5) = 0,30555 … Схема та же самая, поэтому я просто приведу выкладки:

Период k = 1 ⇒ умножаем все на 10^k = 10¹ = 10;

10X = 10 · 0,30555 … = 3,05555 …
10X − X = 3,0555 … − 0,305555 … = 2,75 = 11/4;
9X = 11/4;
X = (11/4) : 9 = 11/36.

Наконец, последняя дробь: X = 0,(2475) = 0,2475 2475 … Опять же, для удобства периодические части отделены друг от друга пробелами. Имеем:

k = 4 ⇒ 10^k = 10⁴ = 10 000;
10 000X = 10 000 · 0,2475 2475 = 2475,2475 …
10 000X − X = 2475,2475 … − 0,2475 2475 … = 2475;
9999X = 2475;
X = 2475 : 9999 = 25/101.

Смотрите также:

1. Сравнение дробей
2. Тест к уроку «Десятичные дроби» (2 вариант)
3. Четырехугольная пирамида в задаче C2
4. Как сдать ЕГЭ по математике
5. Задача B5: площадь сектора
6. Задача B4: тарифы на сотовую связь

Период десятичной дроби. Онлайн калькулятор

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

Для записи десятичной дроби используйте точку либо запятую (например, 1.12 или 1,12). Обратите внимание, что калькулятор вычисления периода десятичной дроби находит период в пределах 30000 чисел, так как длина периода может достигать сотен тысяч символов и
вычисления займут большое количество времени.

Задача состоит из двух частей. Сначала нужно найти длину периода, затем вычислить периодическую часть дроби 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] = '';
    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] = '';
        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'

Например. $0,1234444444 ldots ; 12,453737373737 ldots$

Повторяющиеся цифры — период — для сокращения записи пишут в круглых скобках.

Например. $0,12344444444 ldots=0,123(4)$   ;
  $12,453737373737 ldots=12,45(37)$

Например. $2,4949 ldots=2,(49)$

Например. $0,11232323 ldots=0,11(23)$   ;
  $1,54444 . .=1,5(4)$

Чтобы обратить чистую периодическую дробь в обыкновенную, достаточно записать числителем ее период,
а в знаменателе записать столько девяток, сколько цифр в периоде.

Чтобы записать смешанную периодическую дробь в виде обыкновенной, надо из числа, стоящего до второго
периода вычесть число, стоящее до первого периода, результат записать в
числителе; в
знаменатель записать
число, содержащее столько девяток, сколько цифр в периоде, и столько нулей в конце, сколько цифр между
запятой и периодом.

Например. Запишем дробь $2,34(2)$ в виде обыкновенной

Читать первую тему — понятие дроби и виды дробей,
раздела дроби.