Difference between revisions of "Finite State Machine"

From Progzoo
Jump to: navigation, search
(Even Binary Numbers)
 
(8 intermediate revisions by the same user not shown)
Line 2: Line 2:
 
==Even Binary Numbers==
 
==Even Binary Numbers==
  
<question class='P'>
+
<question className='EvenBinary'>
 
<prog><![CDATA[
 
<prog><![CDATA[
public class EvenBinary {
+
public class EvenBinary{
  
public static void main(String[] args) {
+
  public static void main(String[] args) {
String [] ls = {"10", "111", "01"};  
+
    String [] ls = {"10", "111", "01"};  
for (String s : ls)
+
    for (String s : ls)
System.out.printf("%10s, %s\n", s,sm(s));
+
      System.out.printf("%10s, %s\n", s,sm(s));
}
+
}
 
 
public enum States {START,FAIL,A,B};
+
  public enum States {START,FAIL,A,B};
public static boolean sm(String s)
+
  public static boolean sm(String s)
{
+
States state = States.START;
+
int i=0;
+
while (i<s.length() && state!=States.FAIL)
+
{
+
char c = s.charAt(i);
+
switch (state){
+
case START:
+
if (c=='1')
+
state = States.B;
+
else
+
state = States.FAIL;
+
break;
+
case A:
+
if (c=='0')
+
state = States.A;
+
else if (c=='1')
+
state = States.B;
+
state = States.FAIL;
+
break;
+
case B:
+
if (c=='0')
+
state = States.A;
+
else if (c=='1')
+
state = States.B;
+
else
+
state = States.FAIL;
+
break;
+
}
+
i++;
+
}
+
return state==States.A;
+
}
+
}
+
]]></prog>
+
The function '''fact''' takes a single integer input. The result is that number times by each of the numbers smaller - down to one.
+
fact(1) =  1        =  1
+
fact(2) =  1*2      =  2
+
fact(3) =  1*2*3    =  6
+
fact(4) =  1*2*3*4  =  24
+
fact(5) =  1*2*3*4*5 = 120
+
</question>
+
 
+
==What is the function==
+
 
+
<question class='P'>
+
<prog><![CDATA[
+
public class P{
+
  public static void main(String argv[])
+
 
   {
 
   {
    for (int i=0;i<5;i++)
+
    States state = States.START;
      System.out.printf("%d%8d\n",i,f(i));
+
    int i=0;
  }
+
    while (i<s.length() && state!=States.FAIL)
 
+
    {
  static int f(int i){
+
      char c = s.charAt(i);
    if (i==0)
+
      switch (state){
      return 0;
+
        case START:
    else
+
          if (c=='1')
      return 2+f(i-1);
+
            state = States.B;
 +
          else
 +
            state = States.FAIL;
 +
          break;
 +
        case A:
 +
          if (c=='0')
 +
            state = States.A;
 +
          else if (c=='1')
 +
            state = States.B;
 +
          else
 +
            state = States.FAIL;
 +
          break;
 +
        case B:
 +
          if (c=='0')
 +
            state = States.A;
 +
          else if (c=='1')
 +
            state = States.B;
 +
          else
 +
            state = States.FAIL;
 +
          break;
 +
      }
 +
      i++;
 +
    }
 +
    return state==States.A;
 
   }
 
   }
 
}
 
}
Line 79: Line 53:
  
  
==What is the function==
+
==Even Binary Numbers - Abstracted==
  
<question class='P'>
+
<question className='EvenBinary'>
 
<prog><![CDATA[
 
<prog><![CDATA[
public class P{
+
import java.util.HashMap;
   public static void main(String argv[])
+
public class EvenBinary{
 +
 
 +
   public static void main(String[] args) {
 +
    String [] ls = {"10", "111", "01"};
 +
    for (String s : ls)
 +
      System.out.printf("%10s, %s\n", s,sm(s));
 +
}
 +
 +
  public enum States {S,A,B};
 +
  public static boolean sm(String s)
 
   {
 
   {
    for (int i=0;i<5;i++)
+
    HashMap<States,HashMap<String,States>> d =  
      System.out.printf("%d%8d\n",i,f(i));
+
      new HashMap<States,HashMap<String,States>>();
  }
+
    d.put(States.S,new HashMap<String,States>());
 
+
    d.put(States.A,new HashMap<String,States>());
  static int f(int i){
+
    d.put(States.B,new HashMap<String,States>());
     if (i==0)
+
    d.get(States.S).put("1",States.B);
       return 1;
+
    d.get(States.A).put("0",States.A);
     else
+
    d.get(States.A).put("1",States.B);
      return 2*f(i-1);
+
    d.get(States.B).put("0",States.A);
 +
    d.get(States.B).put("1",States.B);
 +
   
 +
    States state = States.S;
 +
    int i=0;
 +
    while (i<s.length() && state!=null)
 +
     {
 +
      String c = s.substring(i,i+1);
 +
      state = d.get(state).get(c);
 +
       i++;
 +
     }
 +
    return state==States.A;
 
   }
 
   }
 
}
 
}
 
]]></prog>
 
]]></prog>
 
</question>
 
</question>
==What is the function==
 
  
<question class='P'>
+
==Divisible by Three (decimal)==
 +
 
 +
<question className='Div3'>
 
<prog><![CDATA[
 
<prog><![CDATA[
public class P{
+
 
   public static void main(String argv[])
+
public class Div3 {
 +
 
 +
   public static void main(String[] args) {
 +
    String [] ls = {"10", "111", "01","123"};
 +
    for (String s : ls)
 +
      System.out.printf("%10s, %s\n", s,sm(s));
 +
  }
 +
  public enum States {FAIL,A,B,C};
 +
  public static boolean sm(String s)
 
   {
 
   {
    for (int i:new int[]{2, 42, 111, 2753})
+
    States state = States.A;
      System.out.printf("%5d%8d\n",i,f(i));
+
    int i=0;
  }
+
    while (i<s.length() &&
 
+
        state!=States.FAIL)
  static int f(int i){
+
    {
    if (i==0)
+
      char c = s.charAt(i);
      return 0;
+
      switch (state){
    else
+
      case A:
       return (i%10)+f(i/10);
+
        if (c=='0' || c=='3' || c=='6' || c=='9')
 +
          state = States.A;
 +
        else if (c=='1'||c=='4'||c=='7')
 +
          state = States.B;
 +
        else if (c=='2'||c=='5'||c=='8')
 +
          state = States.C;
 +
        break;
 +
      case B:
 +
        if (c=='0' || c=='3' || c=='6' || c=='9')
 +
          state = States.B;
 +
        else if (c=='1'||c=='4'||c=='7')
 +
          state = States.C;
 +
        else if (c=='2'||c=='5'||c=='8')
 +
          state = States.A;
 +
        break;
 +
       case C:
 +
        if (c=='0' || c=='3' || c=='6' || c=='9')
 +
          state = States.C;
 +
        else if (c=='1'||c=='4'||c=='7')
 +
          state = States.A;
 +
        else if (c=='2'||c=='5'||c=='8')
 +
          state = States.B;
 +
        break;
 +
      }
 +
      i++;
 +
    }
 +
    return state==States.A;
 
   }
 
   }
 
}
 
}
 
 
 
]]></prog>
 
]]></prog>
 
</question>
 
</question>

Latest revision as of 16:03, 1 March 2012

Finite State Machines

Even Binary Numbers


[Font] [Default] [Show] [Resize] [History] [Profile]


Even Binary Numbers - Abstracted


[Font] [Default] [Show] [Resize] [History] [Profile]

Divisible by Three (decimal)


[Font] [Default] [Show] [Resize] [History] [Profile]