Beispielaufgaben Informatik – Algorithmen Schritt 1 von 2 0% Aufgabe 1: Java Gegeben ist folgendes Programmfragment in der Programmiersprache Java: int zahl = 0; int a = 7; int b = 13; while (a > 0) { a = a - 1; int c = b; while (c > 0) { c = c - 1; zahl = zahl + 1; } } Welche Größe hat die Variable zahl nach Ausführen des Codes? 0 1 7 13 20 91 104 Aufgabe 2: Algorithmen Man klassifiziert Algorithmen nach ihrer Aufwandsklasse. Vereinfacht ausgedrückt entspricht die Aufwandsklasse der Häufigkeit, mit der die meistaufgerufene Programmzeile zugehöriger Programme ausgeführt wird. Die Aufwandsklasse wird häufig in der O‑Notation angegeben. Beispiel 1: Ein Algorithmus, bei dem unabhängig vom Variablenwert jede Zeile nur einmal aufgerufen wird, ist der Aufwandsklasse $\displaystyle{O}{\left({1}\right)}$ zuzuordnen. Beispiel 2: Ein Algorithmus, der eine beliebige natürliche Zahl n so häufig (abgerundet) halbiert, bis sie 1 ergibt, ist der Aufwandsklasse $\displaystyle{O}{\left( \log{{n}}\right)}$ zuzuordnen.Welcher Aufwandsklasse gehört der beschriebene Algorithmus an, wenn die Variablen a und b jeweils durch n (also eine beliebig hohe natürliche Zahl) ersetzt werden? int zahl = 0; int a = 7; int b = 13; while (a > 0) { a = a - 1; int c = b; while (c > 0) { c = c - 1; zahl = zahl + 1; } } $\displaystyle{O}{\left({1}\right)}$ $\displaystyle{O}{\left( \log{{n}}\right)}$ $\displaystyle{O}{\left({n}\right)}$ $\displaystyle{O}{\left({n}^{2}\right)}$ $\displaystyle{O}{\left({2}^{n}\right)}$
