数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物学
数学
英语
经济
心理学
社会学
时尚研究
法律研究基于 DFA 的除法\n
确定性有限自动机 (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
更新于： 17-6 月 2020 日
267 次浏览
广告