Рубрики

Найти длину периода в десятичном значении 1 / n

Учитывая положительное целое число n, найдите период в десятичном значении 1 / n. Период в десятичном значении — это количество цифр (где-то после десятичной точки), которые продолжают повторяться.

Примеры :

Input:  n = 3
Output: 1
The value of 1/3 is 0.333333...

Input: n = 7
Output: 6
The value of 1/7 is 0.142857142857142857.....

Input: n = 210
Output: 6
The value of 1/210 is 0.0047619047619048.....

Давайте сначала обсудим более простую проблему нахождения отдельных цифр в значении 1 / n.

Как найти отдельные цифры в значении 1 / n?
Давайте возьмем пример, чтобы понять процесс. Например, для n = 7. Первую цифру можно получить, выполнив 10/7. Вторая цифра может быть получена к 30/7 (3 — остаток в предыдущем делении). Третья цифра может быть получена к 20/7 (2 — остаток от предыдущего деления). Таким образом, идея заключается в том, чтобы получить первую цифру, а затем продолжайте принимать значение (остаточной * 10) / п в качестве следующей цифры и постоянно обновлять остаток в виде (остаток * 10)% 10. Полной программа обсуждается здесь .

Как найти период?
Период 1 / n равен периоду в последовательности остатков, используемых в вышеупомянутом процессе. Это может быть легко доказано тем фактом, что цифры непосредственно получены из остатков.
Один интересный факт о последовательности остатков состоит в том, что все крачки в периоде этой последовательности остатков различны. Причина этого проста: если остаток повторяется, то это начало нового периода.

Ниже приводится реализация вышеуказанной идеи.

// C ++ программа для поиска длины периода 1 / n
#include <iostream>
#include <map>

using namespace std;

  
// Функция для определения длины периода в 1 / n

int getPeriod(int n)

{

   // Создать карту для хранения картографирования от остатка

   // его позиция

   map<int, int> mymap;

   map<int, int>::iterator it;

  

   // Инициализируем остаток и позицию остатка

   int rem = 1, i = 1;

  

   // Продолжаем находить остатки до повторяющегося остатка

   // находится

   while (true)

   {

        // Найти следующий остаток

        rem = (10*rem) % n;

  

        // Если в mymap есть остаток, тогда разница

        // между текущей и предыдущей позицией есть длина

        // период

        it = mymap.find(rem);

        if (it != mymap.end())

            return (i - it->second);

  

        // Если не существует, то добавьте «i» в mymap

        mymap[rem] = i;

        i++;

   }

  

   // Этот код никогда не должен быть достигнут

   return INT_MAX;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    cout <<  getPeriod(3) << endl;

    cout <<  getPeriod(7) << endl;

    return 0;

}

Выход:

1
6

Мы можем избежать использования карты или хэша, используя следующий факт. Для числа n может быть не более n различных остатков. Кроме того, период может не начинаться с первого остатка, поскольку некоторые начальные остатки могут быть неповторяющимися (не являться частью какого-либо периода). Поэтому, чтобы убедиться, что остаток от периода выбран, начните с (n + 1) -ого остатка и продолжайте искать его следующее вхождение. Расстояние между (n + 1) -ым остатком и его следующим вхождением — это длина периода.

C ++

// C ++ программа для поиска длины периода 1 / n без
// используя карту или хеш
#include <iostream>

using namespace std;

  
// Функция для определения длины периода в 1 / n

int getPeriod(int n)

{

   // Находим (n + 1) -й остаток после десятичной точки

   // в значении 1 / n

   int rem = 1; // Инициализировать остаток

   for (int i = 1; i <= n+1; i++)

         rem = (10*rem) % n;

  

   // Сохраняем (n + 1) -й остаток

   int d = rem;

  

   // Подсчитать количество остатков до следующего

   // вхождение (n + 1) 'остатка' d '

   int count = 0;

   do {

      rem = (10*rem) % n;

      count++;

   } while(rem != d);

  

   return count;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    cout <<  getPeriod(3) << endl;

    cout <<  getPeriod(7) << endl;

    return 0;

}

Джава

// Java-программа для определения длины
// периода 1 / n без использования
// карта или хеш

  

class GFG {

      
// Функция для определения длины периода в 1 / n

static int getPeriod(int n)

{

    // Находим (n + 1) -й остаток после

    // десятичная точка в значении 1 / n

      

    int rem = 1; // Инициализировать остаток

    for (int i = 1; i <= n + 1; i++)

            rem = (10 * rem) % n;

      

    // Сохраняем (n + 1) -й остаток

    int d = rem;

      

    // Подсчитать количество остатков до следующего

    // вхождение (n + 1) 'остатка' d '

    int count = 0;

    do {

        rem = (10 * rem) % n;

        count++;

    } while(rem != d);

      

    return count;

}

  
// Код драйвера

public static void main(String[] args)

{

    System.out.println(getPeriod(3) );

    System.out.println(getPeriod(7));

}
}

  
// Этот код предоставлен Smitha Dinesh Semwal

python3

# Python3 программа для определения длины
# период 1 / n без использования карты или хэша

  
# Функция для определения длины
№ периода в 1 / н

def getPeriod( n) :

  

    # Найти (n + 1) -й остаток после

    # десятичная точка в значении 1 / n

    rem = 1 # Инициализировать остаток

    for i in range(1, n + 2): 

        rem = (10 * rem) % n

  

    # Хранить (n + 1) -й остаток

    d = rem

      

    # Подсчитать количество остатков

    # до следующего появления

    # (n + 1) 'остаток' d '

    count = 0

    rem = (10 * rem) % n

    count += 1

    while rem != d :

        rem = (10 * rem) % n

        count += 1

      

    return count

  
Код водителя

if __name__ == "__main__":

  

    print (getPeriod(3))

    print (getPeriod(7))

  
# Этот код добавлен
# by ChitraNayal

C #

// C # программа для определения длины
// период 1 / n без использования
// карта или хеш

using System;

  

class GFG {

      
// Функция для определения длины периода в 1 / n

static int getPeriod(int n)

{

    // Находим (n + 1) -й остаток после

    // десятичная точка в значении 1 / n

      

    int rem = 1; // Инициализировать остаток

    for (int i = 1; i <= n + 1; i++)

            rem = (10 * rem) % n;

      

    // Сохраняем (n + 1) -й остаток

    int d = rem;

      

    // Подсчитать количество остатков до следующего

    // вхождение (n + 1) 'остатка' d '

    int count = 0;

    do {

        rem = (10 * rem) % n;

        count++;

    } while(rem != d);

      

    return count;

}

  
// Код драйвера

public static void Main()

{

    Console.Write(getPeriod(3) + "\n");

    Console.Write(getPeriod(7));

}
}

  
// Этот код предоставлен Smitha Dinesh Semwal

PHP

<?php
// PHP программа для определения длины
// периода 1 / n без
// используя карту или хеш

  
// Функция для определения длины
// периода в 1 / n

function getPeriod($n)

{

    // Находим (n + 1) -й остаток

    // после десятичной точки

    // в значении 1 / n

      

    // Инициализировать остаток

    $rem = 1; 

    for ($i = 1; $i <= $n + 1; $i++)

        $rem = (10 * $rem) % $n;

  

    // Store (n + 1) th

    // остаток

    $d = $rem;

  

    // Подсчитать количество

    // остатки до следующего

    // вхождение (n + 1) 'th

    // остаток 'd'

    $count = 0;

    do 

    {

        $rem = (10 * $rem) % $n;

        $count++;

    } while($rem != $d);

      

    return $count;

}

  

    // Код драйвера

    echo getPeriod(3), "\n";

    echo getPeriod(7), "\n";

      
// Этот код предоставлен ajit.
?>


Выход:

1
6

Ссылка:
Алгоритмы и программирование: проблемы и решения Александр Шен

Эта статья предоставлена Sachin . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти длину периода в десятичном значении 1 / n

0.00 (0%) 0 votes