Übungsaufgabe - Easyshop
Aufgabe C
a)
Aufgabenkontext
Im Supermarkt EasyShop soll ein digital unterstützter Einkaufswagen eingesetzt werden. Dieser verfügt über ein Display, einen Strichcodeleser und eine Waage. Letztere erfasst laufend das Gesamtgewicht aller Artikel im Einkaufswagen. Mit dem Strichcodeleser werden die Artikel vor dem Hineinlegen und nach dem Entnehmen aus dem Einkaufswagen vom Kunden gescannt. Beim Entnehmen eines Artikels aus dem Einkaufswagen verringert sich das gemessene Gewicht bereits vor dem Scannen. Beim Hineinlegen ist das Gewicht zum Zeitpunkt des Scannens noch unverändert.
Der Einkaufswagen wird im Folgenden mithilfe der Klassen Einkaufswagen und Artikel modelliert. Die im Einkaufswagen liegenden Artikel werden in einem Stapel warenkorb vom Inhaltstyp Artikel verwaltet. In Abbildung 1 im Material ist ein Klassendiagramm für diese Modellierung dokumentiert.
Frage
Die Operation verarbeiteScan (siehe Struktogramm in Abbildung 2) aktualisiert die Belegung des Einkaufswagens unmittelbar nach jedem erfolgten Scan. Diese Operation wird mehrfach nacheinander mit den in der Abbildung 3 aufgelisteten Parametern aufgerufen. Der Einkaufswagen ist zu Beginn schon mit einigen Artikeln gefüllt.
Stellen Sie in der Abbildung 3 jeweils den Zustand des Stapels warenkorb nach Ablauf der Operation verarbeiteScan dar.
Frage
Aufgrund eines Fehlers kommt es während der Operation verarbeiteScan zu einem Programmabbruch. Zuvor wurde diese mit den Parametern artnr=120 und gewichtsaenderung=-50 im Zustand wk0 des Stapels warenkorb (s. Abb. 3) aufgerufen.
Analysieren Sie das Verhalten der Operation verarbeiteScan für diesen Aufruf
Die Operation verabeiteScan entfernt die obersten Elemente des Stapels solange bis sie das Element mit der Artikelnummer 120 entfernt hat. In diesem Fall ist die 120 nicht im Stapel enthalten, das heißt das Programm wird versuchen das oberste Element des Stapels zu entfernen, obwohl der Stapel bereits leer ist.
Frage
Entwickeln Sie ein verändertes Struktogramm für die Operation verarbeiteScan, sodass diese Situation durch Ausgabe einer entsprechenden Fehlermeldung berücksichtigt wird. Der Stapel warenkorb soll nach Beendigung der Operation wieder in seinem Ursprungszustand vorliegen.
Hinweis: Sie dürfen für die Dokumentation Ihrer Lösung Blöcke des zu verändernden Struktogramms markieren/nummerieren und in verkürzter Form verwenden.
b)
Aufgabenkontext
Beim Bezahlen des Einkaufs werden die Artikel in warenkorb nach ihren Artikelnummern sortiert und im Anschluss in einen globalen Stapel verkaufteArtikel vom Inhaltstyp Artikel des Supermarkts übertragen. Am Ende eines Tages ist der Stapel verkaufteArtikel folglich mit vielen vorsortierten Teilfolgen von Artikelobjekten gefüllt. Eine Teilfolge entspricht dabei einem Einkauf. Zur weiteren Verarbeitung soll der Stapel verkaufteArtikel vollständig sortiert werden.
In den beiden folgenden Aufgabenteilen werden nun verschiedene Aspekte zum Sortieren des Stapels verkaufteArtikel betrachtet. Zunächst wird die folgende Hilfsoperation verwendet: Die Operation zusammen(s1, s2: Stapel): Stapel erzeugt aus zwei absteigend sortierten Stapeln mit Artikeln einen neuen Stapel, der alle in den Stapeln s1 und s2 enthaltenen Artikel absteigend sortiert enthält.
Frage
In Abbildung 4 im Material ist die Arbeitsweise der Operation zusammen anhand eines Beispiels dokumentiert.
Entwickeln Sie ein Struktogramm für die Operation zusammen. Die der Operation übergebenen Stapel werden nach dem Aufruf der Operation nicht weiterverwendet und dürfen daher beliebig verändert werden.
Stack<int> zusammen(Stack<int> s1, Stack<int> s2){
Stack<int> s3 = new Stack<int>();
while (s1.Count > 0){
if (s2.Count > 0){
if(s1.Peek() < s2.Peek()){
s3.Push(s2.Pop());
}else{
s3.Push(s1.Pop());
}
}
else
s3.Push(s1.Pop());
}
while (s2.Count > 0){
s3.Push(s2.Pop());
}
while(s3.Count > 0){
s1.Push(s3.Pop());
}
return s1;
}Frage
Erläutern Sie, wie der Algorithmus von zusammen zu verändern ist, wenn die Ausgabe in Form einer Schlange statt eines Stapels erfolgen soll. Auch die zurückgegebene Schlange soll absteigend, mit dem größten Element am Kopf, sortiert sein.
Wenn eine Schlange verwendet werden soll, kann man das Umschichten von s3 nach s1 um die Reihenfolge der Elemente umzukehren entfernen, da bei einer Schlage das first-in-first-out Prinzip greift. Das heißt, dass das größte Element, welches auch als erstes in die Schlange eingereiht wird, auch das Element an der ersten Stelle ist.
Frage
Häufig werden der Operation zusammen sehr unterschiedlich stark gefüllte Stapel übergeben, nur selten sind beide Stapel gleichgroß.
Beurteilen Sie die beiden folgenden Aussagen:
- Wenn in einem der beiden Stapel nur ein Artikel enthalten ist, dann benötigt die Operation zusammen für die vollständige Verarbeitung stets nur eine geringe Anzahl von Vergleichen.
- Sind in beiden Stapeln zu Beginn jeweils k Elemente enthalten, so werden bei der vollständigen Verarbeitung der Operation zusammen im günstigsten Fall nur k Vergleiche benötigt.
- Ja in meiner Implementierung wird nicht verglichen, ob die Elemente größer als einander sind.
- nein
c)
Aufgabenkontext
Zusätzlich zur Operation zusammen wird im Folgenden die Hilfsoperation trennen(s: Stapel): Schlange verwendet. Diese erzeugt eine Schlange, in der die Elemente des übergebenen Stapels in Form von absteigend sortierten Teilstapeln enthalten sind.
d)
Aufgabenkontext
Alle Artikel im Supermarkt verfügen über eine Artikelnummer, die jeweils in Form eines Strichcodes aus einer Abfolge von schwarzen und weißen Balken aufgedruckt ist. In Abbildung 6 ist hierzu eine wenig geeignete Codierung A angegeben, die jede Ziffer von 0 bis 9 mit einer eigenen Balkenfolge codiert. Für jedes Codewort aus dieser Codierung soll grundsätzlich gelten, dass maximal drei gleichfarbige Balken aufeinander folgen.
Frage
Bestimmen Sie für den Strichcode in Abbildung 7a die zugehörige Artikelnummer.
- 48146
- 578