การหารด้วย DFA (DFA-based Division) ใน C++

แนวคิด

ใช้ DFA ตรวจสอบว่าเลขหารด้วย k ลงตัวหรือไม่ และหาเศษได้ โดยสร้าง Transition Table จากการแทนค่าในฐานสอง

สร้าง Transition Table

มี k states (0 ถึง k-1) แต่ละ state มี transition สำหรับ bit 0 และ 1

trans_0 = (state << 1) % k
trans_1 = ((state << 1) + 1) % k

อัลกอริธึม

1. สร้าง Transition Table ขนาด k×2
2. เริ่ม state = 0
3. ประมวลผลบิตของตัวตั้ง (num) จาก MSB ไป LSB (Recursive right shift)
4. state = table[state][current_bit]
5. state สุดท้าย = เศษ

โปรแกรมตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

void createTransTable(int k, vector<array<int,2>>& table) {
    table.resize(k);
    for (int state = 0; state < k; state++) {
        int trans0 = (state << 1) % k;
        int trans1 = ((state << 1) + 1) % k;
        table[state][0] = trans0;
        table[state][1] = trans1;
    }
}

void checkDivisible(int num, int& state, const vector<array<int,2>>& table) {
    if (num != 0) {
        checkDivisible(num >> 1, state, table);
        state = table[state][num & 1];
    }
}

int dfaDivide(int num, int k) {
    vector<array<int,2>> table;
    createTransTable(k, table);
    int state = 0;
    checkDivisible(num, state, table);
    return state;  // remainder
}

int main() {
    int num = 67, k = 5;
    int rem = dfaDivide(num, k);
    if (rem == 0) cout << num << " divisible by " << k;
    else cout << num << " not divisible by " << k << ", remainder " << rem;
    return 0;
}

ผลลัพธ์

67 not divisible by 5, remainder 2