Jak zamienić tabelę prawdy w najmniejszy możliwy blok jeśli / else

20

Jak mogę wziąć tabelę prawdy i zmienić ją w kompaktowy blok if?

Załóżmy na przykład, że mam tabelę prawdy, w której A i B są warunkami, a x, y i z są możliwymi akcjami:

A B | x y z
-------------
0 0 | 0 0 1
0 1 | 0 0 1
1 0 | 0 1 0
1 1 | 1 0 0

To może przekształcić się w poniżej, jeśli blok:

if(A)
{
    if(B)
    {
        do(x)
    }
    else
    {
        do(y)
    }
}
else
{
    do(z)
}

Jest to łatwa próbka, ale często mam kilka warunków, które łączone na różne sposoby powinny dawać różne wyniki i trudno jest znaleźć najbardziej kompaktowy i elegancki sposób przedstawienia ich logiki w bloku if.

Juan
źródło
10
masz na myśli przekształcenie mapy Karnaugh w kaskadę ifelse?
maniak zapadkowy
@ratchet: Wydaje się, że to robię, prawda? Nie wiedziałem o nich wcześniej. Będę musiał trochę poczytać, ale aplikacja, która by to zrobiła, byłaby miła, jeśli nic innego, by zweryfikować moje ręcznie wykonane wyniki.
Juan
1
@jalayn większość narzędzi karnaugh służy do obwodów cyfrowych; te mają inną heurystykę niż to, o co chodzi
maniak zapadkowy
1
@jsoldi: Otrzymane odpowiedzi będą zależeć od wybranej witryny. Jeśli szukasz komentarza do określonego fragmentu kodu zawierającego pewne bloki „jeśli-to-jeszcze”, z pewnością należy on do przeglądu kodu (beta) . Stackoverflow nauczy Cię narzędzi i technik. Na programmers.SE ludzie powiedzą ci, czy powinieneś / powinnaś nie przejmować się przepisywaniem instrukcji logicznych dla ludzkiego zrozumienia, czy szybszym wykonywaniem.
rwong
2
Zalecenia narzędzia są nie na temat, ale po zmianie na pytanie „Jak mam to zrobić?” będzie na temat. Jeśli potrzebujesz rekomendacji oprogramowania, powinieneś przejść do softwarerecs.stackexchange.com.
Kilian Foth,

Odpowiedzi:

14

Jeśli projektujesz z mapy Karnaugh, kod może równie dobrze wyglądać w ten sposób:

//                   a      b
def actionMap = [ false: [false: { z() },
                          true:  { z() }],
                  true:  [false: { x() },
                          true:  { y() }]]

actionMap[a][b]()
Kevin Cline
źródło
Jaki to język? JavaScript? Pyton?
TheLQ
TheLQ, to nie jest Python, może być javascript. Ale byłoby bardzo podobnie, gdyby napisane w python
grizwako
@TheLQ: to Groovy, ponieważ to właśnie robię w tych dniach i prawdopodobnie także Ruby. Kod dla Javascript, Python, LUA lub Perl byłby bardzo podobny.
kevin cline
2
To oczywiście skutkuje oceną b, nawet gdy ocena nie jest potrzebna. Może to problem, a może nie.
pseudonim
@kevincline, proszę, bardzo proszę, „Lua”, a nie „LUA”. :)
Machado,
4

W języku C # .NET można użyć klasy Dictionary, aby uzyskać wynik bez IF IFSE w następujący sposób - miłą rzeczą jest to:

  1. To jest czytelne
  2. Nowe klucze będą unikalne (w przeciwnym razie pojawi się błąd)
  3. Sekwencja nie ma znaczenia
  4. Łatwe dodawanie lub usuwanie wpisów

Jeśli nie masz odpowiednika klasy Dictionary, możesz zrobić to samo w funkcji binarnego wyszukiwania / wyszukiwania.

//A B | x y z
//-------------
//0 0 | 0 0 1
//0 1 | 0 0 1
//1 0 | 0 1 0
//1 1 | 1 0 0
// Create a Dictionary object and populate it
Dictionary<string, string> _decisionTable = new Dictionary<string, string>() { 
    { "0,0", "0,0,1" }, 
    { "0,1", "0,0,1" }, 
    { "1,0", "0,1,0" }, 
    { "1,1", "1,0,0"} 
};

//usage example: Find the values of X,Y,Z for A=1,B=0
Console.WriteLine(_decisionTable["1,0"]);
Console.Read();
Bez szans
źródło
1
Podoba mi się to rozwiązanie, jedyną zmianą, którą wprowadziłbym, byłoby użycie Dictionary <Tuple <bool, bool>, Tuple <bool, bool, bool> zamiast Dictionary <string, string>. Wtedy nie musisz budować łańcucha do wyszukiwania i później dekonstruować wynik, ponieważ Tuples zrobi to za Ciebie.
Lyise,
@Lyise, dziękuję za uwagę. Masz absolutną rację. Powinienem uwzględnić twoją dobrą rację, kiedy mam szansę.
NoChance,
2

Co chcesz to algorytm Rete . To automatycznie przeczesuje zestaw reguł i nadaje im priorytety w drzewie, tak jak to opisujesz.

Istnieje wiele komercyjnych systemów „silnika reguł”, które robią to na bardzo dużą skalę (miliony reguł), w których niezbędna jest szybkość wykonywania.

Alex Feinman
źródło
2

Oto twoja biblioteka :) I nie musisz przekazywać pełnej tabeli K, tylko pola, którymi jesteś zainteresowany :) Zakłada, że ​​jej operator AND w tabeli prawdy. Jeśli chcesz użyć większej liczby operatorów, powinieneś mieć możliwość przepisania go. Możesz mieć dowolną liczbę argumentów. Napisane pythoni przetestowane.

def x():
    print "xxxx"

def y():
    print "yyyyy"

def z(): #this is default function
    print "zzzzz"

def A():
    return 3 == 1

def B():
    return 2 == 2


def insert(statements,function):
    rows.append({ "statements":statements, "function":function })

def execute():
    for row in rows:
        print "==============="
        flag = 1

        for index, val in enumerate(row["statements"]):
            #for first pass of lopp, index is 0, for second its 1....
            #if any function returns result different than one in our row, 
            # we wont execute funtion of that row (mark row as not executable)
            if funcs[index]() != val:
                flag = 0

        if flag == 1:
            #we execute function 
            row["function"]()
        else: z() #we call default function


funcs = [A,B]  #so we can access functions by index key
rows = []

insert( (0,0), y)
insert( (0,1), y)
insert( (1,0), x)
insert( (1,1), x)
insert( (0,1), x)

execute()
grizwako
źródło
1

Zamapuj dane wejściowe na jedną wartość, a następnie włącz ją:

#define X(a, b) (!!(a) * 2 + !!(b))
switch(X(A, B)) {
case X(0, 0):
    ...
    break;
case X(0, 1):
    ...
    break;
case X(1, 0):
    ...
    break;
case X(1, 1):
    ...
    break;
}
#undef X
Deduplikator
źródło
1

Tabela przeglądowa zawierająca wskaźniki funkcji może działać dobrze w niektórych sytuacjach. Na przykład w C możesz zrobić coś takiego:

typedef void(*VoidFunc)(void);

void do(int a, int b)
{
    static VoidFunc myFunctions[4] = {z, z, y, x}; // the lookup table

    VoidFunc theFunction = myFunctions[ a * 2 + b ];
    theFunction();
}

Jest to dobre rozwiązanie, gdy liczba danych wejściowych jest względnie mała, ponieważ liczba pozycji w tabeli musi wynosić 2 ^ ^ n, gdzie n jest liczbą danych wejściowych. 7 lub 8 wejściami może być zarządzalnych, 10 lub 12 zaczyna być brzydkich. Jeśli masz tak wiele danych wejściowych, spróbuj najpierw uprościć w inny sposób (np. Mapy Karnaugh).

Caleb
źródło
0

Spójrz na oprogramowanie „Gorgeous Karnaugh” - może przyjmować tabele prawdy całkiem dokładnie jak twoja próbka, akceptuje definicję analitycznych formuł boolowskich, akceptuje skrypty Lua, aby budować tabele prawdy. Następnie oprogramowanie „Gorgeous Karnaugh” rysuje mapy K dla pobranych danych, które można zminimalizować ręcznie lub przy użyciu minimalizatora logiki „Espresso”, i wytwarza dane wyjściowe dla C / C ++ i niektórych języków sprzętowych. Zajrzyj na stronę z podsumowaniem funkcji „Gorgeous Karnaugh” - http://purefractalsolutions.com/show.php?a=xgk/gkm

Petruchio
źródło
Wygląda to bardzo podobnie do tego, czego potrzebuję, ale ifpo wejściu do tabeli prawdy nie udało mi się uzyskać kodu C / C ++ do pokazywania niczego poza pustymi literami.
Juan
Tak, to narzędzie zaprojektowane do minimalizacji funkcji logicznych - po wejściu do tabeli prawdy należy zminimalizować funkcję logiczną (PoS / SoP - 0/1). Kod C ++ można znaleźć w oknie „Wyniki minimalizacji” po minimalizacji.
Petruchio