Рубрики

Отдел DFA

Детерминированный конечный автомат (DFA) можно использовать для проверки, делится ли число «num» на «k» или нет. Если число не делится, остаток также можно получить с помощью DFA.

Мы рассматриваем двоичное представление 'num' и строим DFA с k состояниями. DFA имеет функцию перехода для 0 и 1. После создания DFA мы обрабатываем 'num' над DFA, чтобы получить остаток.

Давайте пройдемся по примеру. Предположим, мы хотим проверить, делится ли данное число num на 3 или нет. Любое число может быть записано в виде: num = 3 * a + b, где «a» — это частное, а «b» — это остаток.
Для 3 в DFA может быть 3 состояния, каждое из которых соответствует остаткам 0, 1 и 2. И каждое состояние может иметь два перехода, соответствующих 0 и 1 (учитывая двоичное представление заданного 'num').
Функция перехода F (p, x) = q говорит о том, что при чтении алфавита x мы переходим из состояния p в состояние q. Давайте назовем состояния 0, 1 и 2. Начальное состояние всегда будет 0. Окончательное состояние указывает остаток. Если конечное состояние равно 0, число делится.

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

1. Когда мы находимся в состоянии 0 и читаем 0, мы остаемся в состоянии 0.
2. Когда мы находимся в состоянии 0 и читаем 1, мы переходим в состояние 1, почему? Сформированное таким образом число (1) в десятичном виде дает остаток 1.
3. Когда мы находимся в состоянии 1 и читаем 0, мы переходим в состояние 2, почему? Сформированное таким образом число (10) в десятичном виде дает остаток 2.
4. Когда мы находимся в состоянии 1 и читаем 1, мы переходим в состояние 0, почему? Сформированное таким образом число (11) в десятичном виде дает остаток 0.
5. Когда мы находимся в состоянии 2 и читаем 0, мы переходим в состояние 1, почему? Сформированное таким образом число (100) в десятичном виде дает остаток 1.
6. Когда мы находимся в состоянии 2 и читаем 1, мы остаемся в состоянии 2, почему? Число, образованное таким образом (101) в десятичных дробях, остаток 2.

Таблица перехода выглядит следующим образом:

state   0   1
_____________
 0      0   1
 1      2   0
 2      1   2

Давайте проверим, делится ли 6 на 3?
Двоичное представление 6 — 110
состояние = 0
1. состояние = 0, мы читаем 1, новое состояние = 1
2. состояние = 1, мы читаем 1, новое состояние = 0
3. состояние = 0, мы читаем 0, новое состояние = 0
Поскольку конечное состояние равно 0, число делится на 3.

Давайте возьмем другой пример номер 4
состояние = 0
1. состояние = 0, мы читаем 1, новое состояние = 1
2. состояние = 1, мы читаем 0, новое состояние = 2
3. состояние = 2, мы читаем 0, новое состояние = 1
Поскольку конечное состояние не равно 0, число не делится на 3. Остаток равен 1.

Обратите внимание, что конечное состояние дает остаток.

Мы можем расширить указанное решение для любого значения k. Для значения k состояния будут 0, 1,…. , к-1. Как рассчитать переход, если десятичный эквивалент двоичных битов, замеченных до сих пор, пересекает диапазон k? Если мы находимся в состоянии p, мы прочитали p (в десятичной форме). Теперь мы читаем 0, новый номер чтения становится 2 * р. Если мы читаем 1, новое число чтения становится 2 * p + 1. Новое состояние может быть получено путем вычитания k из этих значений (2p или 2p + 1), где 0 <= p <k.
Основываясь на вышеуказанном подходе, следующий рабочий код:

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Функция для построения DFA для делителя k

void preprocess(int k, int Table[][2]) 

    int trans0, trans1; 

  

    // Следующий цикл вычисляет

    // два перехода для каждого состояния,

    // начиная с состояния 0

    for (int state = 0; state < k; ++state) 

    

        // Рассчитать следующее состояние для бита 0

        trans0 = state << 1; 

        Table[state][0] = (trans0 < k) ? 

                                trans0 : trans0 - k; 

  

        // Рассчитать следующее состояние для бита 1

        trans1 = (state << 1) + 1; 

        Table[state][1] = (trans1 < k) ? 

                                trans1 : trans1 - k; 

    

  
// Рекурсивная функция полезности, которая
// принимает 'num' и DFA (переход
// таблица) как входные данные и процесс 'num'
// постепенно по DFA

void isDivisibleUtil(int num, int* state,

                     int Table[][2]) 

    // обрабатываем "num" по крупицам

    // из MSB в LSB

    if (num != 0) 

    

        isDivisibleUtil(num >> 1, state, Table); 

        *state = Table[*state][num & 1]; 

    

  
// Основная функция, которая делит 'num'
// по k и возвращает остаток

int isDivisible (int num, int k) 

    // Выделить память для таблицы переходов.

    // В таблице будет k * 2 записей

    int (*Table)[2] = (int (*)[2])malloc(k*sizeof(*Table)); 

  

    // Заполняем таблицу переходов

    preprocess(k, Table); 

  

    // Обработка 'num' над DFA и

    // получить остаток

    int state = 0; 

    isDivisibleUtil(num, &state, Table); 

  

    // Обратите внимание, что окончательное значение

    // состояние - это остаток

    return state; 

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

int main() 

    int num = 47; // Число для деления

    int k = 5; // Делитель

  

    int remainder = isDivisible (num, k); 

  

    if (remainder == 0) 

        cout << "Divisible\n"

    else

        cout << "Not Divisible: Remainder is " 

             << remainder; 

  

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

#include <stdio.h>
#include <stdlib.h>

  
// Функция для построения DFA для делителя k

void preprocess(int k, int Table[][2])

{

    int trans0, trans1;

  

    // Следующий цикл вычисляет два перехода для каждого состояния,

    // начиная с состояния 0

    for (int state=0; state<k; ++state)

    {

        // Рассчитать следующее состояние для бита 0

        trans0 = state<<1;

        Table[state][0] = (trans0 < k)? trans0: trans0-k;

  

        // Рассчитать следующее состояние для бита 1

        trans1 = (state<<1) + 1;

        Table[state][1] = (trans1 < k)? trans1: trans1-k;

    }

}

  
// Рекурсивная служебная функция, которая принимает 'num' и DFA (переход
// таблица) в качестве входных данных и обрабатывать 'num' по битам над DFA

void isDivisibleUtil(int num, int* state, int Table[][2])

{

    // обрабатываем "num" по битам из MSB в LSB

    if (num != 0)

    {

        isDivisibleUtil(num>>1, state, Table);

        *state = Table[*state][num&1];

    }

}

  
// Основная функция, которая делит num на k и возвращает остаток

int isDivisible (int num, int k)

{

    // Выделить память для таблицы переходов. Таблица будет иметь k * 2 записей

    int (*Table)[2] = (int (*)[2])malloc(k*sizeof(*Table));

  

    // Заполняем таблицу переходов

    preprocess(k, Table);

  

    // Обрабатываем 'num' над DFA и получаем остаток

    int state = 0;

    isDivisibleUtil(num, &state, Table);

  

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

    return state;

}

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

int main()

{

    int num = 47; // Число для деления

    int k = 5; // Делитель

  

    int remainder = isDivisible (num, k);

  

    if (remainder == 0)

        printf("Divisible\n");

    else

        printf("Not Divisible: Remainder is %d\n", remainder);

  

    return 0;

}

Выход:

Not Divisible: Remainder is 2

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

Статьи по Теме:
Проверьте делимость в двоичном потоке
Проверьте, является ли поток кратным 3

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

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

Отдел DFA

0.00 (0%) 0 votes