Есть ли более простой способ решить эту проблему, не используя так много операторов if?и как? - PullRequest
Новая
       23

Есть ли более простой способ решить эту проблему, не используя так много операторов if?и как?

0 голосов
/ 03 мая 2019

Нам дали задачу, которая просит использовать буквы QDN (Quarter, Dime, Nickel) для создания конечного автомата, который принимает, только если они прибавляют к 40 центам.У меня есть основы для использования концепции оператора IF.Мне было интересно, если есть более простой способ сделать это, который занимает меньше времени?

Я пытался сделать тонны случаев, но есть много шагов для использования этого метода. 

public class FSA2_rpf4961 {

public static void main(String[] args) {
    //The program will read in a sequence of strings and test them against a 
    //FSM. Your strings may not contain blank spaces
    System.out.println("Enter string to test or q to terminate");
    Scanner in = new Scanner (System.in);
    String testString = in.next();

    while (!testString.equals("q"))
    {
        String testOutput = applyFSA2(testString);
        System.out.println("For the test string "+testString+
                                ", the FSM output is "+testOutput);
        System.out.println("Enter next string to test or q to terminate:");
        testString = in.next();

    }
    in.close();

}
public static String applyFSA(String s) {
   String currentOut = "0";                // initial output in s0
   String currentState = "s0";             // initial state

   int i = 0;

   while (i<s.length())
   {
            //quarter first
           if (currentState.equals("s0") && s.charAt(i) == 'q')
           {
                    currentState = "s1";  
                    currentOut += 25;  // collect output on move to s1
           }
           else if (currentState.equals("s1") && s.charAt(i)  == 'd') {
            currentState = "s2";
            currentOut += 10;
           }
           else if (currentState.equals("s2") && s.charAt(i)  == 'n') {
            currentState = "s3";
            currentOut += 5;
           }
           else if (currentState.equals("s1") && s.charAt(i)  == 'n') {
            currentState = "s4";
            currentOut += 5;
           }
           else if (currentState.equals("s4") && s.charAt(i)  == 'd') {
            currentState = "s3";
            currentOut += 10;
           }

           //dime first
           else if (currentState.equals("s0") && s.charAt(i) == 'd')
           {
                    currentState = "s5";
                    currentOut += 10;   // d
            }

Нам нужно только принять, если он добавляет к 40 центам.Это очень запутанно для меня, чтобы понять.

1 Ответ

0 голосов
/ 03 мая 2019

Я собираюсь говорить здесь вообще, потому что ваш текущий код странен до такой степени, что почти наверняка нарушен. Я не совсем понимаю, каким должен быть ваш «результат».

FSM - это определение набора состояний и того, как ввод вызывает переходы состояний. Похоже, вы начали примерно так, но currentOut не работает. Если ваша цель состояла в том, чтобы получить сумму, вы победили весь смысл упражнения. Неважно, что это за сумма. Важно то, в каком состоянии вы находитесь в конце, в частности, в состоянии ли вы «принять», в данном случае это состояние, в котором строка равна ровно 40 центам.

Что касается того, как реализовать FSM без каджиллионов if с, вы часто можете хранить состояния в массиве, и вместо этого ваше имя состояния должно быть номером состояния. На этом этапе вы можете теоретически избавиться от всех ваших if с. (Тем не менее, в реальном мире вы, возможно, захотите игнорировать или отклонять символы, отличные от (q | d | n).)

Рассмотрим что-то вроде этого (псевдокод): 

    // Each array in `graph` represents a state.
    // Each entry is the state number (ie: index into `graph`) to go to
    // when you're in that state and see the corresponding char.
    //
    // BTW, the state graph makes a lot more sense when you consider nickels first.
    // A nickel takes you to the "next" state, and dimes and quarters act like
    // 2 and 5 nickels, respectively. When you do that, a pattern shows up.
    graph = [
      //  n  d  q
      //-----------
        [ 1, 2, 5 ], // s0
        [ 2, 3, 6 ], // s1
        [ 3, 4, 7 ], // s2
        [ 4, 5, 8 ], // s3
        [ 5, 6, 9 ], // s4
        [ 6, 7, 9 ], // s5
        [ 7, 8, 9 ], // s6
        [ 8, 9, 9 ], // s7
        [ 9, 9, 9 ], // s8
        [ 9, 9, 9 ]  // s9 (fail state)
    ]
    start = 0
    accept = 8
    fail = 9

    // at this point, walking the graph is trivial.
    state = start
    for each char c in s:
        index = "ndq".indexOf(c) // n->0, d->1, q->2, others -> -1
        state = graph[state][index]


    // Once the loop's done:
    //   if state == accept, you have exactly 40c.
    //   if state == fail, you have >40c. A FSM won't tell you how much,
    //      because FSMs can't count.
    // any other state represents a known amount that's less than 40c.
...