/****************************************/
/** EPROG Runde 1: Bsp. 1154 (schwer) **/
/** Programmierer: Michael Zöch **/
/** Matrikelnummer: 0305116 **/
/** E-mail: kongo@gmx.at **/
/** HP: www.8ung.at/kongo/index.html **/
/****************************************/
----------------------------------------------------------------------------------------------------
|====================================== 0) Aufbau der Hilfe =======================================|
----------------------------------------------------------------------------------------------------
0) Aufbau der Hilfe
1) Kurzbeschreibung
2) Spezifikation im txt Format
3) Detailbeschreibung
3.1) Konstanten und Variablen
3.2) Die Funktion main()
3.3) Die Funktion toKV()
4) Quellcode des Programms ohne Kommentare
----------------------------------------------------------------------------------------------------
|======================================= 1) Kurzbeschreibung ======================================|
----------------------------------------------------------------------------------------------------
Das Programm liest Strings ein (zb. "ABCD abcd AbCd aBcd...") die eine disjunktive Normalform
darstellen. Dies tut das Programm bis es das Endzeichen "=" erhält und gibt daraufhin das passende
Karnaugh-Veitch-Diagramm aus. (mehr Infos zu dem KV-Diagramm findest du im Buch von Schildt:
"Grundlagen Informatik", 4. Ausgabe, Seite 177ff)
Beispiel:
Programm starten: $ java Disjnorm
Eingabe: $ ABCD abcd AbCd aBcd =
Ausgabe: 0001 0010 0100 0001
----------------------------------------------------------------------------------------------------
|======================================== 2) Spezifikation ========================================|
----------------------------------------------------------------------------------------------------
(Konvertierung der HTML-Spezifikation)
Kurzbeschreibung:
Eine bool'sche Funktion in disjunktiver Normalform wird eingelesen; das entsprechende Karnaugh -
Veitch - Diagramm wird ausgegeben.
Aufgabenstellung:
Lesen Sie eine bool'sche Funktion in der disjunktiven Normalform ein. Eine disjunktive Normalform
besteht aus Disjunktionen von Vollkunjunktionen.
Dazu wird folgende Notation verwendet: Es gibt genau vier Eingabevariablen, nämlich A, B, C und D.
Diese werden immer in dieser Reihenfolge angegeben; es müssen immer alle vier Variablen vorkommen.
Negierte Variablen werden klein geschrieben; es werden keine Operatoren angegeben.
Jede Vollkunjunktion wird in einem eigenen String eingelesen. Am Ende des Ausdrucks wird ein "="
geschrieben.
Beispiel: _ _ _ _ _ _
(AnBnCnD)v(AnBnCnD)v(AnBnCnD)
wird durch "AbcD aBcD aBCd =" dargestellt.
Für diesen Ausdruck soll Ihr Programm eine Kanraugh-Veitch-Tabelle mit folgender
Variablenanordunung erstellen:
c C C c
a 0 0 0 0 b
A 1 0 0 0 b
A 0 0 0 0 B
a 1 0 1 0 B
D D d d
Verwenden Sie die Zeichen "0" und "1" zum Beschreiben der logischen Zustände "falsch" und "wahr".
Eingabedaten:
Lesen Sie die Strings ein, die zusammen die disjunktive Normalform darstellen. Diese Strings müssen
jeweils 4 Zeichen lang sein und die Buchstaben A, B, C und D in genau dieser Reihenfolge beinhalten
(wobei es wie gesagt bedeutsam ist, ob die Buchstaben groß oder klein geschrieben werden).
Es dürfen keine zwei gleichen Strings eingegeben werden. Das Ende des Datensatzes wird durch das
Zeichen "=" markiert.
Ausgabedaten:
Bei korrekten Eingabedatensätzen soll Ihr Programm die vier Zeilen des Karnaugh-Veitch-Diagramms
ausgeben, also vier Strings zu je vier Zeichen, wobei nur die Zeichen "0" und "1" vorkommen (der
Rahmen der Tabelle 'c C C c' etc. in der oberen Darstellung dient nur zur Erläuterung und soll in
der Ausgabe nicht aufscheinen).
Trennen sie die vier Strings durch jeweils ein Leerzeichen und geben Sie am Ende einen
Zeilenvorschub aus.
Fehlerbehandlung:
Sämtlichce Eingabedatensätze sind immer bis zum definierten Endezeichen einzulesen. Generell wird
bei fehlerhaften Eingabedatensätzen nur eine einzige Fehlermeldung erzeugt, weitere Berechnungen
werden nicht mehr durchgeführt.
Sind die Datentypen bei allen Eingaben richtig, die eingegebenen Daten aber inhaltlich nicht
korrekt oder erfüllen nicht die Bedingungen, so soll Ihr Programm "FALSCHE EINGABE", gefolgt von
einem Zeilenvorschub ausgeben.
Beispiele:
Eingabedaten:
AbCD ABCD aBCD AbCd =
abCD abCd AbcD AbCD Abcd ABCD aBCD aBcd =
Ausgabedaten:
0000 0110 0100 0100
0110 1101 0110 0101
----------------------------------------------------------------------------------------------------
|====================================== 3) Detailbeschreibung =====================================|
----------------------------------------------------------------------------------------------------
____________________________________________________________________________________________________
___________________________________ 3.1) Konstanten und Variablen __________________________________
Das Programm definiert alle (Eingabe- und Ausgabe-) Strings als Konstanten, um so das Ändern von
Ausdrücken zu vereinfachen und somit das Programm flexibler zu gestalten.
Insgesamt gibt es nur eine Klassenvariable:
static boolean kvdiag[][] = new boolean[4][4];
In dieser speichern wird das Karnaugh-Veitch-Diagramm. Dieses Diagramm ist eine grafische
Darstellung von einem Algorithmus, um Funktionen zu vereinfachen.
Das KV-Diagramm:
c C C c
a 0 0 0 0 b
A 0 0 0 0 b
A 0 0 0 0 B
a 0 0 0 0 B
D D d d
Das KV-Diagramm ist eine Darstellung einer Funktion in disjunktiver Normalform mit vier Variablen.
Jeder Eintrag entspricht dabei einer Vollkunjunktion.
disjunktive Normalform: ABCD abcd AbCd aBcd ...
Vollkunjunktion: 1. ABCD, 2. abcd, 3. AbCd, 4. aBcd, ...
Das Programm liest wortweise diese Vollkunjunktionen ein und berechnet den dazugehörigen Eintrag in
dem KV-Diagramm. Als Beispiel nehmen wir "abcd". Das Programm berechnet dabei aus "ab" die Zeile und
aus "cd" die Spalte. "ab" wäre in unserem Fall die 0. Reihe und "cd" die 3. Spalte. Also setzen wir
in unserem KV-Diagramm diesen Wert auf true.
kvdiag[0][3] = true;
Wenn das Programm das Zeichen "=" einliest bricht es ab und gibt, wenn kein Fehler aufgetreten ist,
das KV-Diagramm aus. Die Reihen werden dabei nur durch ein Leerzeichen voneinander getrennt.
Ausgabe (zu obigen Beispiel): 0001 0010 0100 0001
____________________________________________________________________________________________________
_____________________________________ 3.2) Die Funktion main() _____________________________________
Die Funktion main() verwendet zwei Variablen. Erstens einen String für die Eingabe (input) und
zweitens einen Boolean für die Fehlerbehandlung (err). Es liest solange Worte ein, bis das
Endzeichen "=" eingegeben wird, auch wenn ein Fehler bereits aufgetreten ist. Dann prüft es ob der
eingegebene String gleich "ABCD" ist. Dies prüft es aber ohne Unterscheidung der
Groß/Kleinschreibung. Ist dies nicht der Fall, so wird err auf true gesetzt.
Somit haben wir bis jetzt gewährleistet das die Eingabe richtig "formatiert" ist und können sie der
Funktion toKV() übergeben. Diese berechnet das KV-Diagramm. Sollte diese Funktion false als Rückgabe
liefern, ist ein Fehler aufgetreten und wir setzen err auf true.
Gibt der Benutzer nach der Eingabe der Vollkunjunktionen ("ABCD") "=" ein, so bricht das Programm
mit dem Einlesen ab und begibt sich zur Ausgabe.
Sollte ein Fehler aufgetreten sein, gibt es "FALSCHE EINGABE" aus, waren alle Eingaben aber richtig,
so gibt es das KV-Diagramm aus. Eine Reihe wird dabei als "0" und "1" ausgegeben. Zwischen den
Reihen wird als Trennzeichen ein Leerzeichen eingefügt. Eine "1" steht dafür, dass die zu diesem
Eintrag passende Vollkunjunktionen eingegeben wurde, eine "0", dass diese nicht eingegeben wurde.
____________________________________________________________________________________________________
_____________________________________ 3.3) Die Funktion toKV() _____________________________________
Wie schon gesagt, übergeben wir dieser Funktion die Eingabe, wenn kein Fehler aufgetreten ist.
Als erstes berechnet die Funktion die für diesen Eintrag zugehörige Reihe und speichert diese in der
Variable row. Dann berechnet es die Spalte und speichert diese in der Variable col.
c C C c
a 0 0 0 0 b
A 0 0 0 0 b
A 0 0 0 0 B
a 0 0 0 0 B
D D d d
Die Berechnung der Reihe erfolgt mit Hilfe der ersten beiden Buchstaben "AB". Wie wir aus diesem
Diagramm herauslesen können gibt es immer zwei mögliche Reihen für den Buchstaben "a" und zwei für
"A". Kombiniert mit dem zweiten Buchstaben "b" oder "B" ergibt sich daraus nur eine mögliche Reihe.
Ist zb. die Eingabe "aBcd" müssen wir die Reihe suchen wo "aB" vorkommt und die Spalte wo "cd"
vorkommt. "ab" kommt dabei nur in der letzten Reihe vor (a 0 0 0 0 B) und "cd" ebenfalls nur in der
letzten Spalte (c 0 0 0 0 d). Wo sich die beiden treffen, ist der zugehörige Eintrag und den setzen
wir jetzt auf true:
c C C c
a 0 0 0 0 b
A 0 0 0 0 b
A 0 0 0 0 B
a 0 0 0 1 B
D D d d
Sollte der Eintrag aber schon auf true gesetzt sein, so wurde diese Vollkunjunktion schon einmal
eingegeben und wir liefern als Rückgabewert false. Damit signalisieren wir der Funktion main() das
ein Fehler aufgetreten ist.
----------------------------------------------------------------------------------------------------
|========================================== 4) Quellcode ==========================================|
----------------------------------------------------------------------------------------------------
Für alle die keine Kommentare möchten, hier der Quellcode einmal ohne:
import eprog.*;
public class Disjnorm extends EprogIO
{
static final String IN_ENDZEICHEN = "=";
static final String IN_UPPERCASE = "ABCD";
static final String OUT_1 = "1";
static final String OUT_0 = "0";
static final String OUT_TRENNZEICHEN = " ";
static final String OUT_ERROR_MESSAGE = "FALSCHE EINGABE";
static boolean kvdiag[][] = new boolean[4][4];
static boolean toKV(String in)
{
int row=-1, col=-1;
if (in.charAt(0) == IN_UPPERCASE.charAt(0)) {
if (in.charAt(1) == IN_UPPERCASE.charAt(1))
row = 2;
else
row = 1;
} else {
if (in.charAt(1) == IN_UPPERCASE.charAt(1))
row = 3;
else
row = 0;
}
if (in.charAt(2) == IN_UPPERCASE.charAt(2)) {
if (in.charAt(3) == IN_UPPERCASE.charAt(3))
col = 1;
else
col = 2;
} else {
if (in.charAt(3) == IN_UPPERCASE.charAt(3))
col = 0;
else
col = 3;
}
if (kvdiag[row][col] == true)
return false;
kvdiag[row][col] = true;
return true;
}
public static void main(String[] args)
{
String input = "";
boolean err = false;
do {
input = readWord();
if (input.equals(IN_ENDZEICHEN))
break;
if (err) continue;
if (!input.equalsIgnoreCase(IN_UPPERCASE)) {
err = true;
continue;
}
if (toKV(input) == false)
err = true;
} while(true);
if (err) {
println(OUT_ERROR_MESSAGE);
} else {
for (int i = 0; i < 16; i++) {
if (i != 0 && i%4 == 0) print(OUT_TRENNZEICHEN);
print(kvdiag[i/4][i%4]==true ? OUT_1 : OUT_0);
}
println();
}
}
}
----------------------------------------------------------------------------------------------------
------------------------------------------- END OF FILE --------------------------------------------
----------------------------------------------------------------------------------------------------