#1 28. April 2014 Abend, komme bei dieser Aufgabe nicht richtig weiter: Code: Algorithmus klausur (Stack s) In: Stack s mit n Elementen Out: ? WHILE (s.size() > 1) DO Integer operand1 = s.pop() Integer operand2 = s.pop() Integer operator = s.pop() // berechne Operation IF (operator == 0) THEN s.push (operand1 + operand2) ELSE IF(operator == 1) THEN s.push(operand1 * operand2) END IF END WHILE RETURN s.pop() -------------------------------------------------------------- [b]Aufgabe a:[/b] Beschreiben Sie kurz die Aufgabe des folgenden Algorithmus. Der Algorithmus soll beispielhaft mit einem Stack s ausgeführt werden, welcher die folgenden Werte in der gegebenen Reihenfolge enthält: s = [0, 7, 1, 5, 0, 4, 3]. Geben Sie nach jedem Schleifendurchlauf den Inhalt des Stacks s an. Hinweis: das zuletzt auf den Stack eingefügte Element ist die 3. [b]Aufgabe b:[/b] Geben Sie die Komplexität des Algorithmus in der O-Notation an. Begründen Sie ihre Antwort. Mit "pop" wird ein Element entfernt, mit "push" draufgelegt. Die Bedingung läuft so lange bis im Stack nur noch eine Zahl enthalten ist. Aber mit dem Mittelteil komm ich nicht weiter. Kann mir da jdm helfen das zu lösen, sodass ichs nachvollziehen kann? Danke schonmal im Vorraus. Gruß Sib + Multi-Zitat Zitieren
#2 28. April 2014 Zuletzt bearbeitet: 28. April 2014 AW: Algorithmus Stack-Datenstruktur Aufgabe Ist doch easy ^^ Es werden immer drei Zahlen ausgelesen. Dabei sind die ersten beiden die Operanden und die dritte Zahl der Operand. Operand kann hierbei 0(Addition) oder 1(Multiplikation) sein. Das Ergebnis der Operation wird dann mittels push wiederum zum Stack hinzugefügt. Also 1. Durchlauf: [0, 7, 1, 5, 0, 4, 3] => 3+4 (da Operand=0) = 12 2. Durchlauf: [0, 7, 1, 5, 12] => 12*5 (da Operand=1) = 60 3. Durchlauf: [0, 7, 60] => 60+7 (da Operand=0) = 67 => Stack hat dann nur noch die 67 drin stehen, deswegen bricht die Schleife ab und der Wert wird zurückgegeben. + Multi-Zitat Zitieren
#3 29. April 2014 AW: Algorithmus Stack-Datenstruktur Aufgabe perfekt, mit deiner erklärung hab ichs verstanden danke! nur beim 1. durchlauf müsste 7 rauskommen oder? [0, 7, 1, 5, 0, 4, 3] => 3+4 = 7 [0, 7, 1, 5, 7] => 7*5 = 35 [0, 7, 35] => 35+7 = 42 Aufgabe b komm ich auch nicht so richtig weiter. Geben Sie die Komplexität des Algorithmus in der O-Notation an. Begründen Sie ihre Antwort. + Multi-Zitat Zitieren