Рубрики

Найти повторяющуюся последовательность во фракции

Для заданной дроби найдите повторяющуюся последовательность цифр, если она существует, в противном случае выведите «Нет повторяющейся последовательности».

Примеры:

Input  : Numerator = 8, Denominator = 3
Output : Recurring sequence is 6 
Explanation : 8/3 = 2.66666666.......  

Input : Numerator = 50, Denominator = 22
Output : Recurring sequence is 27
Explanation : 50/22 = 2.272727272..... 

Input : Numerator = 11, Denominator = 2
Output : No recurring sequence
Explanation : 11/2 = 5.5 

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Когда повторяется дробная часть?

Давайте смоделируем процесс преобразования дроби в десятичную. Давайте посмотрим на ту часть, где мы уже выяснили целую часть, которая является полом (числитель / знаменатель). Теперь мы остались с (остаток = числитель% знаменатель) / знаменатель.
Если вы помните процесс преобразования в десятичное число, на каждом шаге мы делаем следующее:

  1. Умножьте остаток на 10.
  2. Добавить остаток / знаменатель к результату.
  3. Остаток = остаток% знаменателя.

В любой момент, если остаток становится 0, мы закончили.

Однако, когда есть повторяющаяся последовательность, остаток никогда не становится 0. Например, если вы посмотрите на 1/3, остаток никогда не станет 0.

Ниже приведено одно важное замечание:
Если мы начнем с остатка «rem» и если остаток повторяется в любой момент времени, цифры между двумя вхождениями «rem» будут повторяться.

Таким образом, идея заключается в том, чтобы сохранить остатки на карте. Всякий раз, когда остаток повторяется, мы возвращаем последовательность до следующего вхождения. Ниже приведена реализация вышеуказанной идеи на C ++.

// C ++ программа для поиска повторяющейся последовательности в дроби
#include <bits/stdc++.h>

using namespace std;

  
// Эта функция возвращает повторяющуюся последовательность
// фракция. Если повторяющаяся последовательность не
// выходит, затем возвращает пустую строку

string fractionToDecimal(int numr, int denr)

{

    string res; // Инициализировать результат

  

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

    // остаток используется как ключ и его позиция в

    // результат сохраняется как значение. Обратите внимание, что нам нужно

    // позиция для случаев типа 1/6. В таком случае,

    // повторяющаяся последовательность не начинается сначала

    // остаток.

    map <int, int> mp;

    mp.clear();

  

    // Найти первый остаток

    int rem = numr%denr;

  

    // Продолжаем находить остаток

    // становится 0 или повторяется

    while ( (rem!=0) && (mp.find(rem) == mp.end()) )

    {

        // Сохраняем этот остаток

        mp[rem] = res.length();

  

        // Умножаем остаток на 10

        rem = rem*10;

  

        // Добавляем rem / denr к результату

        int res_part = rem / denr;

        res += to_string(res_part);

  

        // Обновить остаток

        rem = rem % denr;

    }

  

    return (rem == 0)? "" : res.substr(mp[rem]);

}

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

int main()

{

    int numr = 50, denr = 22;

    string res = fractionToDecimal(numr, denr);

    if (res == "")

        cout << "No recurring sequence";

    else

        cout << "Recurring sequence is " << res;

    return 0;

}

Выход :

Recurring sequence is 27

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

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

Найти повторяющуюся последовательность во фракции

0.00 (0%) 0 votes