//by bell, ammended after seeing Oma Falks solution /* [Challenge] by Oma Falk Create a FSM(d) that accepts a binary representation of a number b and decides whether or not b is divisible by d. The FSM has a Start state Accepted state Finite number of states Rules how input changes state.....here input is the iteration of b. Example for Input 3: Startstate: s0 Accepted state: s0 States: S0,S1,S2 Rules: S0: 0 to S0,1 to S1 S1: 0 to S2, 1 to S0 S2: 0 to S1, 1 to S2 Test for 9=1001 State S0 input 1 S1 input 0 S2 input 0 S1 input 1 S0 accepted state, 9 is divisible by 3. */ #include #include #include using namespace std; #define M 10 bool fsm3(bitset b){ string start="A"; int m=0; string states="BAACCB"; //string represents true/false states for (int i = int(b.size())-1;i >= 0; i--) { cout << b.test(i); start=((b.test(i))? states[m]:states[m+1] ); m=2*(int(start[0])-65); cout << start << " "; } return start=="A"; //accepted state? } bool fsm(bitset b,int idiv,string states){ string start="A"; int m=0; // vector s; // vector s={"BABA","BAACCB","BADCBABC","BADCAECBED","BACDEAFBCDFE"}; // BABA BAACCB BADCBADC BADCAECBED BADCFEBADCFE BADCFEAGCBEDGF // string states=s[idiv-2]; //FSM for each divisor for (int i = int(b.size())-1;i >= 0; i--) { cout << b.test(i); start=((b.test(i))? states[m]:states[m+1] ); m=2*(int(start[0])-65); } return start=="A"; //accepted state? } int main() { string so; int n=27,l=100; //cin>>idiv; bitset bi(n); cout<<"Is "<bi(i); cout<<" "<<((fsm(bi,idiv,so))?" True":" False"); cout<

divide2to6fsmOmaFalk