Phân chia dựa trên DFA trong C ++?

Tự động hóa hữu hạn xác định (DFA) được sử dụng để kiểm tra xem một số có chia hết cho một số k khác hay không. Thuật toán hữu ích vì nó cũng có thể tìm phần dư nếu số không chia hết.

Trong phân chia dựa trên DFA, chúng tôi xây dựng một bảng DFA với k trạng thái. Chúng tôi coi là đại diện nhị phân của số nên chỉ có 0 và 1 ở mỗi trạng thái trong DFA.

Hàm createTransTable (int k, int transTable [] [2]) được sử dụng để tạo transTable và lưu trữ các trạng thái trong đó. Nó nhận số k là số có thể chia hết và transTable [] [2] là một mảng có 2 cột. Sau đó, chúng tôi khai báo hai biến trans_0 lưu trữ trạng thái tiếp theo của bit 0 và trans_1 lưu trữ trạng thái tiếp theo của bit 1.

void createTransTable(int k, int transTable[][2]){
   int trans_0, trans_1;

Vòng lặp for bên trong chạy cho đến khi trạng thái nhỏ hơn k. Nếu trans_0 nhỏ hơn số k thì transTable [trạng thái] [0] bằng trans_0 khác k được trừ cho trans_0.

Đối với trans_1 Nếu trans_1 nhỏ hơn số k thì transTable [state] [1] bằng trans_1 còn lại k được trừ cho trans_1.

for (int state = 0; state < k; state++){
   trans_0 = state << 1;
   transTable[state][0] = (trans_0 < k) ? trans_0 : trans_0 - k;
   trans_1 = (state << 1) + 1;
   transTable[state][1] = (trans_1 < k) ? trans_1 : trans_1 - k;
}

Hàm checkDivible (int num, int &state, int transTable [] [2]) nhận số sẽ được chia, biến trạng thái theo tham chiếu và mảng transTable [] [2]. Nó kiểm tra nếu số không bằng 0 thì về cơ bản nó sẽ chuyển số từ trái sang phải bằng cách sử dụng dịch chuyển phải theo chiều dọc bit 1 cho đến khi số đó trở thành 0 bằng cách gọi đệ quy chính nó. Bằng cách dịch sang phải, số bị chia cho 2 cho đến khi nó trở thành 0. Sau đó [trạng thái] [num &1] bảng chuyển được gán cho biến trạng thái.

void checkDivisible(int num, int &state, int transTable[][2]){
   if (num != 0){
      checkDivisible(num >> 1, state, transTable);
      state = transTable[state][num&1];
   }
}

Hàm isDivible (int num, int k) nhận số cổ tức và số bị chia k. Bảng chuyển tiếp với 2 cột và k số hàng transTable [k] [2] được khai báo. CreateTransTable (k, transTable) và checkDivible (num, state, transTable) được gọi để sửa đổi biến trạng thái. Sau đó, biến trạng thái được trả về, đại diện cho phần còn lại của chúng tôi đã phân chia.

int isDivisible (int num, int k){
   int transTable[k][2];
   createTransTable(k, transTable);
   int state = 0;
   checkDivisible(num, state, transTable);
   return state;
}

Ví dụ

Chúng ta hãy xem cách triển khai sau cho bộ phận dựa trên DFA.

#include <bits/stdc++.h>
using namespace std;
void createTransTable(int k, int transTable[][2]){
   int trans_0, trans_1;
   for (int state = 0; state < k; state++){
      trans_0 = state << 1;
      transTable[state][0] = (trans_0 < k) ? trans_0 : trans_0 - k;
      trans_1 = (state << 1) + 1;
      transTable[state][1] = (trans_1 < k) ? trans_1 : trans_1 - k;
   }
}
void checkDivisible(int num, int &state, int transTable[][2]){
   if (num != 0){
      checkDivisible(num >> 1, state, transTable);
      state = transTable[state][num&1];
   }
}
int isDivisible (int num, int k){
   int transTable[k][2];
   createTransTable(k, transTable);
   int state = 0;
   checkDivisible(num, state, transTable);
   return state;
}
int main(){
   int num = 67;
   int k = 5;
   int remainder = isDivisible (num, k);
   if (remainder == 0)
      cout <<num<< " is divisible by "<<k;
   else
      cout <<num<< " is not divisible by "<<k<<" and lefts remainder "<<remainder;
   return 0;
}

Đầu ra

Đoạn mã trên sẽ tạo ra kết quả sau.

67 is not divisible by 5 and lefts remainder 2