DFAベースの除算アルゴリズム｜決定性有限オートマトンで割り切り判定と余りを求める

決定性有限オートマトン（DFA）は、ある整数が別の整数kで割り切れるかどうかを判定するために利用できる強力な手法です。さらに、割り切れない場合には余りの値まで同時に求めることができます。

DFAによる除算の基本的な仕組み

DFAベースの除算では、まずDFAの遷移表を作成します。この表さえ用意できれば、あとは対象となる数値の各ビットを順に読み込んでいくだけで答えを導き出せます。DFAにおいて、各状態が持つ遷移は「0」と「1」の2種類だけです。

遷移のルールは非常にシンプルです。現在の状態をsとすると、
・入力ビットが0のとき：次の状態は (2×s) をkで割った余り
・入力ビットが1のとき：次の状態は (2×s＋1) をkで割った余り
となります。数値の最上位ビットから順にこの遷移を適用し、最後に到達した状態が0であれば「割り切れた」ことを意味します。それ以外の場合は、その状態の番号がそのまま余りに対応します。

遷移表の例（k = 3 の場合）

例えば、50（2進数で110010）を3で割る場合、ビットを先頭から順に読み込むと状態は「1 → 0 → 0 → 0 → 1 → 2」と遷移し、最終的な状態は2になります。これは実際の余り「2」と一致します。

入力と出力

入力:
数値: 50、除数: 3
出力:
50は3で割り切れず、余りは 2 です

アルゴリズム

dfaDivision(num, k)

入力: 判定対象の数値numと、除数k。

出力: 割り切り判定の結果と余り。

開始
    k × 2 のサイズで遷移表を作成　//「0」と「1」の2つの遷移に対応
    state := 0
    checkState(num, state, table) を呼び出す
    state を返す
終了

checkState(num, state, table)

入力: 数値num、現在の状態state、遷移表table。

出力: ビット列を処理した後の状態を更新する。

開始
    もし num ≠ 0 ならば
        checkState(num >> 1, state, table)　// 数値を1ビット右シフトして再帰呼び出し
        index := num AND 1　// 数値と1の論理積（AND）で最下位ビットを取り出す
        state := table[state][index]
終了

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; // ビット0に対する次の状態
        transTable[state][0] = (zeroTrans < n) ? zeroTrans : zeroTrans - n;

        oneTrans = (state << 1) + 1; // ビット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]; // 遷移表を作成
    makeTransTable(k, table); // 表の全要素を埋める
    int state = 0; // 制御は初期状態0からスタート
    checkState(num, state, table);
    return state; // 最終状態が0なら割り切れている
}

int main() {
    int num;
    int k;
    cout << "数値と除数を入力してください: ";
    cin >> num >> k;
    int rem = isDivisible(num, k);
    if (rem == 0)
        cout << num << " は " << k << " で割り切れます";
    else
        cout << num << " は " << k << " で割り切れず、余りは " << rem << " です";
}

※上記のコードでは可変長配列（VLA）を使用しているため、GCCなど一部のコンパイラでしかコンパイルできない場合があります。その際は、std::vector や動的確保に置き換えると安全です。

実行結果

数値と除数を入力してください: 50 3
50 は 3 で割り切れず、余りは 2 です