基于DFA的部门
确定性有限自动机(DFA)用于检查一个数字是否可被另一个数字k整除。如果不能整除，则此算法还将找到余数。
对于基于DFA的部门，首先，我们必须找到DFA的过渡表，使用该表，我们可以轻松找到答案。在DFA中，每个状态只有两个过渡0和1。
输入输出
Input: The number: 50 and the divisor 3 Output: 50 is not divisible by 3 and remainder is: 2
算法
dfaDivision(num, k)
输入： 数字num和除数k。
输出：检查除数和余数。
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,state,table)
输入： 数字num，状态和转换表。
输出： 执行除法后更新状态。
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示例
#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;
}输出结果
Enter Number, and Divisor: 50 3 50 is not divisible by 3 and remainder is: 2