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. Nếu nó không chia hết, thì thuật toán này cũng sẽ tìm phần còn lại.
Đối với phân chia dựa trên DFA, đầu tiên, chúng ta phải tìm bảng chuyển tiếp của DFA, sử dụng bảng đó, chúng ta có thể dễ dàng tìm ra câu trả lời. Trong DFA, mỗi trạng thái chỉ có hai chuyển tiếp 0 và 1.
Đầu vào và Đầu ra
Input: The number: 50 and the divisor 3 Output: 50 is not divisible by 3 and remainder is: 2
Thuật toán
dfaDivision(num, k)
Đầu vào: Một số num và ước số k.
Đầu ra: Kiểm tra phần chia hết và phần còn lại.
Begin create transition table of size k * 2 //2 for transition 0 and 1 state = 0 checkState(num, state, table) return state End
checkState (num, trạng thái, bảng)
Đầu vào: Một số, trạng thái và bảng chuyển tiếp.
Đầu ra: Cập nhật trạng thái sau khi thực hiện phân chia.
Begin if num ≠ 0, then tempNum := right shift number for i bit checkState(tempNum, state, table) index := number AND 1 //perform logical and with number and 1 state := table[state][index] End
Ví dụ
#include <iostream> using namespace std; void makeTransTable(int n, int transTable[][2]) { int zeroTrans, oneTrans; for (int state=0; state<n; ++state) { zeroTrans = state<<1; //next state for bit 0 transTable[state][0] = (zeroTrans < n)? zeroTrans: zeroTrans-n; oneTrans = (state<<1) + 1; //next state for bit 1 transTable[state][1] = (oneTrans < n)? oneTrans: oneTrans-n; } } void checkState(int num, int &state, int Table[][2]) { if (num != 0) { //shift number from right to left until 0 checkState(num>>1, state, Table); state = Table[state][num&1]; } } int isDivisible (int num, int k) { int table[k][2]; //create transition table makeTransTable(k, table); //fill the table int state = 0; //initially control in 0 state checkState(num, state, table); return state; //final and initial state must be same } int main() { int num; int k; cout << "Enter Number, and Divisor: "; cin >> num>> k; int rem = isDivisible (num, k); if (rem == 0) cout<<num<<" is divisible by "<<k; else cout<<num<<" is not divisible by "<<k<<" and remainder is: " << rem; }
Đầu ra
Enter Number, and Divisor: 50 3 50 is not divisible by 3 and remainder is: 2