Chia dựa trên DFA (DFA based division)

Giới thiệu

Automat hữu hạn xác định (DFA - Deterministic Finite Automaton) được dùng để kiểm tra xem một số có chia hết cho số k khác hay không. Nếu không chia hết, thuật toán này cũng sẽ tìm phần dư.

Đối với phép chia dựa trên DFA, trước tiên ta phải tìm bảng chuyển trạng thái của DFA, dùng bảng đó ta có thể dễ dàng tìm 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

Đầu vào: Số: 50 và số chia 3
Đầu ra: 50 không chia hết cho 3 và phần dư là: 2

Thuật toán

dfaDivision(num, k)
Đầu vào: Một số num, và số chia k.
Đầu ra: Kiểm tra tính chia hết và phần dư.

Begin
    tạo bảng chuyển trạng thái kích thước k * 2 // 2 cho chuyển tiếp 0 và 1
    state = 0
    checkState(num, state, table)
    return state
End

checkState(num, state, table)

Đầu vào: Một số num, state, và bảng chuyển trạng thái.

Đầu ra: Cập nhật state sau khi thực hiện phép chia.

Begin
    if num ≠ 0, then
        tempNum := dịch phải số cho i bit
        checkState(tempNum, state, table)
        index := number AND 1 // phép AND logic với số và 1
        state := table[state][index]
End

Ví dụ (C++)

#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;  // trạng thái tiếp theo cho bit 0
        transTable[state][0] = (zeroTrans < n) ? zeroTrans : zeroTrans-n;
        oneTrans = (state<<1) + 1;  // trạng thái tiếp theo cho bit 1
        transTable[state][1] = (oneTrans < n) ? oneTrans : oneTrans-n;
    }
}

void checkState(int num, int &state, int Table[][2]) {
    if (num != 0) {
        // dịch số từ phải sang trái cho đến khi 0
        checkState(num>>1, state, Table);
        state = Table[state][num&1];
    }
}

int isDivisible(int num, int k) {
    int table[k][2];  // tạo bảng chuyển trạng thái
    makeTransTable(k, table);  // điền bảng
    int state = 0;  // ban đầu điều khiển ở trạng thái 0
    checkState(num, state, table);
    return state;  // trạng thái cuối và trạng thái đầu phải giống nhau
}

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;
}

Kết quả

Enter Number, and Divisor: 50 3
50 is not divisible by 3 and remainder is: 2