数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究基于DFA的C++除法？
确定性有限自动机（DFA）用于检查一个数字是否可以被另一个数字k整除。该算法很有用，因为它还可以找到数字不可整除时的余数。
在基于DFA的除法中，我们构建一个具有k个状态的DFA表。我们考虑数字的二进制表示，因此DFA中每个状态中只有0和1。
createTransTable(int k, int transTable[][2])函数用于创建transTable并在其中存储状态。它接收要被整除的数字k以及transTable[][2]，后者是一个具有2列的数组。然后我们声明两个变量trans_0，它存储位0的下一个状态，以及trans_1，它存储位1的下一个状态。
void createTransTable(int k, int transTable[][2]){
int trans_0, trans_1;内部的for循环在状态小于k时运行。如果trans_0小于数字k，则transTable[state][0]等于trans_0，否则从trans_0中减去k。
对于trans_1，如果trans_1小于数字k，则transTable[state][1]等于trans_1，否则从trans_1中减去k。
for (int state = 0; state < k; state++){
trans_0 = state << 1;
transTable[state][0] = (trans_0 < k) ? trans_0 : trans_0 - k;
trans_1 = (state << 1) + 1;
transTable[state][1] = (trans_1 < k) ? trans_1 : trans_1 - k;
}checkDivisible(int num, int &state, int transTable[][2])函数接收要被除的数字、状态变量（通过引用传递）以及transTable[][2]数组。它检查数字是否不等于0，然后通过将数字从左向右按位右移1，直到数字变为0，通过递归调用自身来实现。通过右移，数字除以2，直到它变为0。然后将transtable[state][num&1]赋值给状态变量。
void checkDivisible(int num, int &state, int transTable[][2]){
if (num != 0){
checkDivisible(num >> 1, state, transTable);
state = transTable[state][num&1];
}
}isDivisible (int num, int k)函数接收被除数num和除数k。声明了一个具有2列和k行数的转移表transTable[k][2]。调用createTransTable(k, transTable)和checkDivisible(num, state, transTable)，它们修改状态变量。然后返回状态变量，它表示我们除法后剩下的余数。
int isDivisible (int num, int k){
int transTable[k][2];
createTransTable(k, transTable);
int state = 0;
checkDivisible(num, state, transTable);
return state;
}示例
让我们看一下基于DFA的除法的以下实现。
#include <bits/stdc++.h>
using namespace std;
void createTransTable(int k, int transTable[][2]){
int trans_0, trans_1;
for (int state = 0; state < k; state++){
trans_0 = state << 1;
transTable[state][0] = (trans_0 < k) ? trans_0 : trans_0 - k;
trans_1 = (state << 1) + 1;
transTable[state][1] = (trans_1 < k) ? trans_1 : trans_1 - k;
}
}
void checkDivisible(int num, int &state, int transTable[][2]){
if (num != 0){
checkDivisible(num >> 1, state, transTable);
state = transTable[state][num&1];
}
}
int isDivisible (int num, int k){
int transTable[k][2];
createTransTable(k, transTable);
int state = 0;
checkDivisible(num, state, transTable);
return state;
}
int main(){
int num = 67;
int k = 5;
int remainder = isDivisible (num, k);
if (remainder == 0)
cout <<num<< " is divisible by "<<k;
else
cout <<num<< " is not divisible by "<<k<<" and lefts remainder "<<remainder;
return 0;
}输出
以上代码将产生以下输出。
67 is not divisible by 5 and lefts remainder 2
159 次查看
