Оптимальная реализация таблицы истинности

Я определил таблицу истинности, такую ​​как приведенная ниже

prev_state| input1         | input2 |next_state| Action
(def/new) |(Disable/Enable)|(Off/On)|          |
def       | D              | Off    | def      | Nothing
def       | D              | On     | def      | Nothing
def       | E              | Off    | def      | Nothing
def       | E              | On     | new      | call function1
new       | D              | Off    | def      | call function2
new       | D              | On     | def      | call function2
new       | E              | Off    | def      | call function2
new       | E              | On     | new      | Nothing

Мне было интересно, какое минимальное количество проверок вам нужно для этого.

Я думаю использовать карту Karnaugh, например следующую:

    00| 01| 11| 10 
  -----------------
0 | A | A | B | A |  
  -----------------
1 | C | C | A | C |  
  -----------------

Где A ничего не соответствует, B для вызова функции1 и C для вызова функции2

Судя по тому, что я вижу, у вас есть 2 комбинации из 2 А и одна А, всего 3 для А, 1 для В и 2 комбинации из 2 С.

Означает ли это, что минимальное количество сравнений 3+1+2=6? Но поскольку A ничего не делает, для минимальной реализации потребуются только 3 комбинации для B и C?

Тестовая реализация

if (prev_state == new && input1 == disable) {
    function2();
}
else if (prev_state == new && input2 == Off) {
    function2();
}
else if (input1 == enable && input2 == On) {
    function1();
}

Также теперь, когда я вижу, что лучше выше или это:

if ((prev_state == new && input1 == disable) || (prev_state == new && input2 == Off)) {
    function2();
}
else if (input1 == enable && input2 == On) {
    function1();
}

Спасибо тем, кто предложил таблицу поиска, которая является O (1), но занимает место в памяти. Теперь я понимаю, что предпочел бы решение, не использующее дополнительную память. Согласны ли вы с тем, что использование карт Карно является допустимым методом для получения минимального количества сравнений?


c algorithm truthtable karnaugh-map
person Satrapes    schedule 08.01.2019    source источник

Ответы (4)


arrow_upward
7
arrow_downward

Мне было интересно, какое минимальное количество проверок нужно для достижения...

Нуль. Используйте справочную таблицу

void f_Nothing(void) {
  ; // do nothing
}

void f_function1(void) {
  ;  // something interesting
}

void f_function2(void) {
  ;  // something interesting
}

int main(void) {

  typedef void (*fun_type)(void);

  fun_type f[2][2][2] = { //
      {{f_Nothing, f_Nothing}, {f_Nothing, f_function1}}, 
      {{f_function2, f_function2}, {f_function2, f_Nothing}}};
  bool prev_state, input1, input2;
  //...
  f[prev_state][input1][input2]();

Позже OP прокомментировал поиск решения, которое... не использовать дополнительную дополнительную память.

if ( (input1 == E && input2 == ON) && (prev_state == def)) function1();
if (!(input1 == E && input2 == ON) && (prev_state == new)) function2();

// or

if (input1 == E && input2 == ON) {
  if (prev_state == def) function1();
} else {
  if (prev_state == new) function2();
}
person chux - Reinstate Monica    schedule 08.01.2019
comment
Просто любопытно: почему `\`? - person alk; 08.01.2019
comment
@alk Комментарий // или ` at the end of fun_type f[2][2][2] = { //` предназначен для поощрения автоматического форматирования, чтобы инициализаторы оставались на следующей строке - мне кажется, это лучше. - person chux - Reinstate Monica; 08.01.2019
comment
@bruno Написание компилируемого решения заняло время - я начал это после улучшения вопроса OP. - person chux - Reinstate Monica; 08.01.2019
comment
Спасибо за ответ. Теперь я понимаю, что забыл указать, что искал решение, которое в идеале не использует дополнительную дополнительную память. Я сосредоточился на том, является ли идея использования карт Карно для систематического сокращения сравнений правильной. - person Satrapes; 08.01.2019
comment
@Satrapes Совет: заявленная цель - минимальное количество проверок. Теперь с решением, которое... не использует дополнительную дополнительную память, если это дополнительное ограничение сейчас через час? Если вам нужно изменить цель, так тому и быть. Тем не менее движущаяся цель может привести к неясному вопросу. - person chux - Reinstate Monica; 08.01.2019
comment
Я знаю, мне жаль, что я понял это только после твоего ответа. - person Satrapes; 09.01.2019

arrow_upward
2
arrow_downward

Если поведение статично, тестировать бесполезно, можно

  • используйте трехмерный массив, где каждое значение представляет собой пару следующего состояния и действия, первое измерение - prev_state 0/1, второй вход 1 D/E -> 0/1, третий вход 2 выкл/вкл -> 0/1

  • но поскольку ваш ввод очень ограничен, вы также можете закодировать 3 индекса только в одном = prev_state * 4 + input1 * 2 + input2 и использовать простой вектор размера 8. Как предлагает Шверн в примечании, вы также можете выполнить переключатель/регистр для результата prev_state * 4 + input1 * 2 + input2

person bruno    schedule 08.01.2019
comment
Будет ли вместо вектора работать переключатель/кейс? - person Schwern; 08.01.2019
comment
да во втором решении тоже можно сделать переключатель/кейс - person bruno; 08.01.2019
comment
@Schwern Просто мне нравится программирование на основе данных ;-) - person bruno; 08.01.2019

arrow_upward
1
arrow_downward

Вы можете удалить некоторые повторяющиеся тесты, но будет ли это иметь большое значение на практике, зависит от оптимизации компилятора.

if (prev_state == new) {
    if (input1 == disable || input2 == Off) {
        function2();
    }
} else {
    if (input1 == enable && input2 == On) {
        function1();
    }
}

Or:

if (input1 == disable || input2 == Off) {
    if (prev_state == new) {
        function2();
    }
} else {
    if (prev_state == def) {
        function1();
    }
}
person Ian Abbott    schedule 08.01.2019

arrow_upward
0
arrow_downward

Я бы сделал что-то вроде ниже.

int check = (int)((prev_state == new) << 2 | (input1 == E)<<1 | (input2 == on));

/*def       | E              | On     | new      | call function1 == 3
  new       | D              | Off    | def      | call function2 == 4
  new       | D              | On     | def      | call function2 == 5
  new       | E              | Off    | def      | call function2 == 6 */

if (check == 4 || check == 5 || check == 6)
  function2();
else if (check == 3)
  function1();
person kiran Biradar    schedule 08.01.2019