การแบ่งตาม DFA ใน C ++?

Deterministic Finite Automaton (DFA) ใช้สำหรับตรวจสอบว่าตัวเลขนั้นหารด้วยตัวเลขอื่น k ลงตัวหรือไม่ อัลกอริทึมนี้มีประโยชน์เพราะสามารถค้นหาส่วนที่เหลือได้หากจำนวนนั้นหารไม่ได้

ในการแบ่งตาม DFA เราสร้างตาราง DFA ที่มีสถานะ k เราพิจารณาการแสดงเลขฐานสองของตัวเลข ดังนั้นจึงมีเพียง 0 และ 1 ในแต่ละสถานะใน DFA

ฟังก์ชัน 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 loop inside ทำงานจนถึง state น้อยกว่า 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 หรือไม่ จากนั้นโดยทั่วไปจะเลื่อนตัวเลขจากซ้ายไปขวาโดยใช้การเลื่อนขวาระดับบิตทีละ 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