DFA(Deterministic Finite Automaton)는 숫자가 다른 숫자 k로 나누어 떨어지는지 여부를 확인하는 데 사용됩니다. 이 알고리즘은 숫자가 나누어지지 않는 경우 나머지도 찾을 수 있기 때문에 유용합니다.
DFA 기반 부서에서는 k 상태로 DFA 테이블을 작성합니다. DFA의 각 상태에는 0과 1만 있도록 숫자의 이진 표현을 고려합니다.
createTransTable(int k, int transTable[][2]) 함수는 transTable을 생성하고 그 안에 상태를 저장하는 데 사용됩니다. 그 수가 나누어질 수 있는 수 k와 2개의 열이 있는 배열인 transTable[][2]를 취합니다. 그런 다음 비트 0 다음 상태를 저장하는 두 개의 변수 trans_0과 비트 1 다음 상태를 저장하는 trans_1을 선언합니다.
void createTransTable(int k, int transTable[][2]){
int trans_0, trans_1; 내부의 for 루프는 상태가 k보다 작을 때까지 실행됩니다. trans_0이 숫자 k보다 작으면 transTable[state][0]은 trans_0과 같으며 그렇지 않으면 k는 trans_0에서 뺍니다.
trans_1의 경우 trans_1이 k보다 작으면 transTable[state][1]은 trans_1과 같으며 그렇지 않으면 k는 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;
} checkDivisible(int num, int &state, int transTable[][2]) 함수는 나눌 숫자, 참조에 의한 상태 변수 및 transTable[][2] 배열을 취합니다. 숫자가 0과 같지 않은지 확인한 다음 기본적으로 자신을 재귀적으로 호출하여 숫자가 0이 될 때까지 비트 오른쪽 시프트를 사용하여 왼쪽에서 오른쪽으로 숫자를 이동합니다. 오른쪽으로 이동하면 숫자가 0이 될 때까지 2로 나뉩니다. 그런 다음 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) 함수는 피제수 수와 피제수 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