การหารแบบ DFA (DFA-based Division)

บทนำ

Deterministic Finite Automaton (DFA) ใช้ตรวจสอบว่าตัวเลขหารด้วยอีกตัวเลข k ลงตัวหรือไม่ ถ้าไม่ลงตัว อัลกอริทึมนี้ยังหาเศษได้ด้วย

สำหรับการหารแบบ DFA ขั้นแรกต้องหาตารางสถานะการเปลี่ยน (Transition Table) ของ DFA โดยใช้ตารางนั้น สามารถหาคำตอบได้ง่าย ใน DFA แต่ละสถานะมีการเปลี่ยนแปลง (Transition) เพียงสองอย่างคือ 0 และ 1

อินพุตและเอาต์พุต

Input: ตัวเลข: 50 และตัวหาร 3
Output: 50 ไม่หารด้วย 3 ลงตัว และเศษคือ: 2

อัลกอริทึม

dfaDivision(num, k)
Input: ตัวเลข num, และตัวหาร k
Output: ตรวจสอบการหารลงตัวและเศษ

Begin
    สร้าง transition table ขนาด k * 2  // 2 สำหรับ transition 0 และ 1
    state = 0
    checkState(num, state, table)
    return state
End

checkState(num, state, table)

Input: ตัวเลข num, state, และ transition table

Output: อัปเดต state หลังจากการหาร

Begin
    if num ≠ 0, then
        tempNum := right shift number สำหรับ i bit
        checkState(tempNum, state, table)
        index := number AND 1  // logical and กับ number และ 1
        state := table[state][index]
End

ตัวอย่างโค้ด (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;  // next state สำหรับ bit 0
        transTable[state][0] = (zeroTrans < n) ? zeroTrans : zeroTrans - n;
        oneTrans = (state << 1) + 1;  // next state สำหรับ bit 1
        transTable[state][1] = (oneTrans < n) ? oneTrans : oneTrans - n;
    }
}

void checkState(int num, int &state, int Table[][2]) {
    if (num != 0) {
        // เลื่อนตัวเลขจากขวาไปซ้ายจนถึง 0
        checkState(num >> 1, state, Table);
        state = Table[state][num & 1];
    }
}

int isDivisible(int num, int k) {
    int table[k][2];  // สร้าง transition table
    makeTransTable(k, table);  // เติมตาราง
    int state = 0;  // เริ่มต้น control อยู่ที่ state 0
    checkState(num, state, table);
    return state;  // final และ initial state ต้องเหมือนกัน
}

int main() {
    int num, 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;
}

ผลลัพธ์

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