資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
