資料結構
網路
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 次瀏覽
廣告