Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- arrays:start [2022/12/06 10:33] – angelegt Martin Pabst
+++ arrays:start [2025/03/23 19:22] (aktuell) – [Aufgabe 7] Martin Pabst
@@ Zeile 1: / Zeile 1: @@
-====== Arrays ======
+====== Arrays (Felder) ======
-Die Materialien zum Thema Arrays muss ich noch hierher kopieren. Bis dahin [[https://www.learnj.de/doku.php?id=types:arrays:start|findet Ihr sie hier.]]
+{{ youtube>dqDPcF9tGtc?large }}
+ \\
+Oft möchte man viele gleichartige Daten (d.h. Daten mit demselben Datentyp) speichern, z.B. die ersten 1000 Primzahlen. Stell Dir vor, Du müsstest für jede dieser Zahlen einen eigenen Variablennamen vergeben:
+<code myJava>
+int p1 = 2;
+int p2 = 3;
+int p3 = 5;
+...
+int p1000 = ?!?
+</code>
+Oder stell Dir vor, Du möchtest dann diese 1000 gespeicherten Zahlen kommasepariert ausgeben (2, 3, 5, 7, ...):
+<code myJava>
+println(p1 + ", " + p2 + ", " + p3 + ", " + p4 + ", " + ... + p1000);
+</code>
+**Kein Mensch möchte das tippen müssen. Das muss doch besser gehen!**
+<WRAP center round info 80%>
+Ein **Array** (deutsch: **"Feld"**) ist ein Datentyp, der es gestattet, viele gleichartige Daten (d.h. **Daten mit demselben Datentyp**) zu speichern und durch Angabe eines **Indizes** (d.h. ihrer Position innerhalb des Feldes) schnell auf sie zuzugreifen. \\ \\
+**Beispiel:** \\
+Lege ein Feld an, in dem 10 ''int''-Werte gespeichert werden können und nenne dieses Feld ''test''.
+<code myJava>
+int[] test = new int[10];
+</code>
+Dabei ist ''int[]'' der Datentyp "Feld von ''int''-Werten". Der Term ''new int[10]'' reserviert einen Speicherbereich, in dem 10 ''int''-Werte Platz haben, füllt ihn mit zehn 0-Werten und liefert eine Referenz darauf zurück. Nach der Zuweisung (''='') zeigt die Variable ''test'' auf diesen Speicherbereich. \\ \\
+Die zehn Werte nennt man **Feldelemente**. Sie werden **mit den Indizes 0 bis 9** durchnummeriert. Du kannst Dir das Feld so vorstellen: \\
+{{ :arrays:pasted:20221208-093237.png }} \\
+**Zugriff auf die Feldelemente:**
+  * ''test[3] = 12;'' weist dem vierten(!) Feldelement den Wert 12 zu. Das Feld sieht danach so aus:
+{{ :arrays:pasted:20221208-093256.png }} \\
+  * ''int a = test[0];'' kopiert den Wert des ersten Feldelements in die Variable ''a''.
+</WRAP>
+===== Beispiel 0: Größte Zahl finden =====
+Schreibe ein Programm, das ein Int-Array mit 100 einträgen deklariert reserviert, dann die 100 Einträge mit Zufallszahlen von 1 bis 1000 füllt, anschließend die größte dieser 1000 Zahlen ermittelt und diese ausgibt.
+<HTML>
+<div class="java-online" style="height: 300px; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'groesstefinden'}">
+<script type="text/plain" title="Groesstefinden.java">
+int[] zahlen = new int[100];
+for (int i = 0; i < 100; i++) {
+   zahlen[i] = Random.randint(1, 1000);
+   println(zahlen[i]);
+}
+int groesste = zahlen[0];
+for (int i = 0; i < 100; i++) {
+   if(zahlen[i] > groesste) {
+      groesste = zahlen[i];
+   }
+}
+println("Größte Zahl im Array ist: " + groesste, Color.red);
+</script>
+</div>
+</HTML>
+===== Beispiel 1: Rätsel =====
+Was gibt das folgende Programm aus? **Denke zuerst nach, bevor Du es ausführst!**
+<HTML>
+<div class="java-online" style="height: 300px; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'ArrayRaetsel'}">
+<script type="text/plain" title="ArrayRaetsel.java">
+int[] zahlen = new int[4];    //Das Feld zahlen hat 4 Werte, mit den Indizes 0, 1, 2, 3
+zahlen[1] = 12;
+zahlen[2] = 8;
+zahlen[0] = zahlen[2] * 3;
+zahlen[3] = zahlen[1] + zahlen[0];
+for(int i = 0; i < 4; i++) {
+   println(i + ": " + zahlen[i]);
+}
+</script>
+</div>
+</HTML>
+{{ :types:arrays:array_debugging.gif?direct&200|Ansicht eines Arrays beim Debuggen}}
+Öffne vor dem Ausführen den Reiter "Variablen" und führe dann das Programm schrittweise aus ("Step over": {{:klassen1:anwenden:step_over.png?nolink|}}). Du kannst so Schritt für Schritt sehen, wie sich die Werte des Feldes verändern und das Programm so ganz leicht verstehen. \\ \\ Klicke rechts auf auf die kleine Grafik, dann wird Dir das Vorgehen als animated gif gezeigt!
+===== Beispiel 2: Namenspeicher =====
+Wir schreiben ein kleines Programm, das den Benutzer nach 5 Namen fragt und diese in einem Array speichert. Anschließend kann der Benutzer Indizes von 0 - 4 eingeben und bekommt den zugehörigen Namen vom Computer genannt. \\ \\
+Natürlich ist dieses Programm noch nicht wirklich praktisch verwendbar, aber Du bekommst ein Gefühl dafür, wozu Arrays gut sind.
+<HTML>
+<div class="java-online" style="height: 300px; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'Namenspeicher'}">
+<script type="text/plain" title="Namenspeicher.java">
+String[] namen = new String[5];
+for(int i = 0; i < 5; i++) {
+   namen[i] = Input.readString("Gib den " + (i + 1) + "-ten Namen ein:");
+}
+while(true) {
+   int index = Input.readInt("Gib einen Index von 0 - 4 ein, ich sag' Dir den dazugehörigen Namen:");
+   println(namen[index], Color.lightgreen);
+}
+</script>
+</div>
+</HTML>
+===== Beispiel 3: Größter Wert (Fingerübung) =====
+  * a) Deklariere ein Feld mit dem Bezeichner ''werte'', das 10 double-Werte enthält und fülle es mit den Werten sin(0), sin(1), …, sin(9). Verwende dazu eine while- oder for-Wiederholung.
+  * b) Ergänze Dein Programm so, dass es anschließend den größten der 10 Werte findet und ausgibt!
+<HTML>
+<div class="java-online" style="height: 400px; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'groessterWert'}">
+<script type="text/plain" title="groessterWert.java">
+double[] werte = new double[10];
+for(int i = 0; i < 10; i++) {
+   werte[i] = Math.sin(i);
+   println( i + ": " + werte[i]);
+}
+double maximum = werte[0];
+for(int i = 1; i < 10; i++) {
+   if(werte[i] > maximum) {
+      maximum = werte[i];
+   }
+}
+println("Der größte Wert ist: " + maximum, Color.lightseagreen);
+</script>
+</div>
+</HTML>
+===== Beispiel 4: Absolute und relative Häufigkeiten beim Würfeln =====
+Der Benutzer nennt eine Anzahl ''n''. Der Computer soll n-mal würfeln und dabei mitzählen, wie oft jede der Zahlen 1 bis 6 vorgekommen ist. Am Ende soll er die absoluten und relativen Häufigkeiten der sechs Zahlen ausgeben. \\ \\
+<WRAP center round tip 60%>
+**Was sind absolute und relative Häufigkeiten?**\\ \\
+Stell' Dir vor, Du würfelst 50-mal. Dabei erhältst Du 7-mal die Augenzahl 6. Dann nennt man 7 die **absolute Häufigkeit** des Ereignisses "6 gewürfelt" und $7/50$ (also 14%) die **relative Häufigkeit** dieses Ereignisses.
+</WRAP>
+**Strategie:** \\
+Wir speichern die Anzahl der Einsen, Zweien, Dreien, ... Sechsen in einem int-Feld mit 6 Werten
+<HTML>
+<div class="java-online" style="height: 450px; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'relativeHaeufigkeit'}">
+<script type="text/plain" title="relativeHaeufigkeit.java">
+int n = Input.readInt("Wie oft soll gewürfelt werden?");
+int[] zähler = new int[6];    // zähler[0] ist die Zahl der Einsen, zähler[1] die der Zweien, usw.
+for(int i = 0; i < n; i++) {
+   int zahl = Math.floor(Math.random() * 6 + 1);  // zufällige Zahl aus {1; 2; ...; 6}
+   zähler[zahl - 1]++;
+   print(zahl + ", ");
+}
+println("\nAbsolute Häufigkeiten: ");
+for(int i = 0; i < 6; i++) {
+   print((i + 1) + ": ");
+   println(zähler[i], Color.goldenrod);
+}
+println("\nRelative Häufigkeiten: ");
+for(int i = 0; i < 6; i++) {
+   print((i + 1) + ": ");
+   println((double)zähler[i] / n, Color.cadetblue);
+}
+</script>
+</div>
+</HTML>
+===== Beispiel 5: Selection Sort =====
+<WRAP center round todo 80%>
+**Selection sort**
+Eine gute Beschreibung dieses Algorithmus [[https://de.wikipedia.org/wiki/Selectionsort|findest Du in Wikipedia]]. Wir programmieren eine etwas einfachere Variante:
+  * 1. Eine Variable ''start'' zeigt zunächst auf das erste Element des Arrays (index 0)
+  * 2. Vergleiche jeden Wert rechts von ''start'' mit dem Wert bei ''start''. Falls ersterer kleiner ist, dann vertausche beide
+  * 3. Erhöhe ''start'' um 1. Falls ''start'' dann noch nicht aufs letzte Element des Arrays zeigt, dann fahre bei 1. fort.
+Die ersten Schritte des Algorithmus siehst Du hier an einem Beispiel:
+{{ :arrays:pasted:20221218-191106.png?600 }}
+{{ :arrays:pasted:20221218-191142.png?600 }}
+{{ :arrays:pasted:20221218-191207.png?600 }}
+</WRAP>
+<HTML>
+<div class="java-online" style="height: 70vh; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'selectionsort'}">
+<script type="text/plain" title="Selectionsort.java">
+int[] zahlen = new int[8];
+// Mit Zufallszahlen belegen
+for (int i = 0; i < 8; i++) {
+   zahlen[i] = Random.randint(0, 100);
+}
+// Unsortiert ausgeben
+for (int i = 0; i < 8; i++) {
+   println(" " + zahlen[i]);
+}
+// sortieren
+// Hier bist Du dran!
+for (int start = 0; start <= 6; start++) {
+   for (int i = start + 1; i <= 7; i++) {
+      if(zahlen[i] < zahlen[start]) {
+         int z = zahlen[i];
+         zahlen[i] = zahlen[start];
+         zahlen[start] = z;
+      }
+   }
+}
+// Sortiert ausgeben
+println();
+println("Sortiert:", Color.chartreuse);
+for (int i = 0; i < 8; i++) {
+   println(" " + zahlen[i]);
+}
+</script>
+</div>
+</HTML>
+===== Aufgabe 1: Zweierpotenzen (Fingerübung) =====
+  * a) Deklariere ein Feld test mit 10 int-Werten und fülle es mit den Zweiterpotenzen 1, 2, 4, 8, 16, … 512. Verwende dazu eine while- oder for-Wiederholung!
+  * b) Erweitere das Programm so, dass es anschließend alle Werte ausgibt.
+  * c) Erweitere das Programm so, dass es - wiederum anschließend - die Summe aller Feldwerte berechnet und ausgibt.
+//**Tipp:** Falls Du Dich mit der Berechnung der Zweierpotenzen schwer tust, [[.zweierpotenzen:start|findest Du hier ein Programm, das die Zweierpotenzen auf dem Bildschirm ausgibt.]]// \\ \\
+[[.zweierpotenz:loesung:start|Hier geht's zur Lösung!]]
+===== Aufgabe 2: Listenumkehrer =====
+Schreibe ein Programm, das es dem Benutzer ermöglicht, 5 Namen einzugeben, und diese 5 Namen am Ende **in umgekehrter Reihenfolge** ausgibt. \\ \\
+[[.listenumkehrer:loesung:start|Hier geht's zur Lösung!]]
+===== Aufgabe 3 (Sternchenaufgabe): Das Sieb des Eratosthenes =====
+Das Sieb des Eratosthenes ist ein sehr schneller Algorithmus zum Finden von Primzahlen, den Du aus dem Mathematikunterricht der Jahrgangsstufe 5 kennst. Falls Du Dich nicht mehr genau erinnerst, hier ein kurzes Erklärvideo dazu:
+{{ youtube>HDrJoLxPU40?large }}
+Schreibe ein Programm, das die Primzahlen bis 100 000 mit Hilfe des Sies des Eratosthenes ermittelt und ausgibt! \\ \\
+**Strategie:**
+  * Deklariere ein Feld ''gestrichen'' von 100 001 Werten des Datentyps ''boolean''. ''gestrichen[i]'' soll angeben, ob das Zahlenfeld mit der Zahl ''i'' "gestrichen" ist.
+  * Setze ''gestrichen[0] = true'' und ''gestrichen[1] = true'', denn 0 und 1 sind keine Primzahlen
+  * Jetzt bis Du dran! Hier noch ein paar kleine Tipps:
+    * Du wirst zwei ineinandergeschachtelte Wiederholungen brauchen.
+    * Die Wurzel von 100 000 erhältst Du so: ''Math.sqrt(100000)''
+[[.eratosthenes:loesung|Hier geht's zur Lösung!]]
+===== Aufgabe 4 Erweiterung des Sieb des Eratosthenes =====
+Erweitere das Programm von Aufgabe 3 so,
+  * a) dass der Benutzer zu Beginn eingeben kann, bis zu welcher Obergrenze die Primzahlen gesucht werden sollen.
+  * b) dass es nach der Ermittlung der Primzahlen alle Primzahlzwillinge im Feld sucht und ausgibt.
+<WRAP center round info 60%>
+Zwei Primzahlen, die den Abstand 2 haben, nennt man ein **Primzahlzwilling**, z.B. [3 und 5], [5 und 7], [11 und 13], [17 und 19] usw. \\
+Man vermutet, dass es unendlich viele Primzahlzwillinge gibt, dies ist aber bis heute nicht bewiesen.
+</WRAP>
+[[.eratosthenes:loesung2|Hier geht's zur Lösung!]]
+===== Aufgabe 5: Bubble Sort =====
+Ein Feld mit 10 ganzen Zahlen soll mit Zufallszahlen (von 1 bis 100) belegt und ausgegeben werden. Anschließend soll der Rechner es der Größe nach aufsteigend sortieren und erneut ausgeben. Zum Sortieren verwenden wir den Bubble Sort-Algorithmus. Hier eine kurze Erklärung:
+{{ youtube>Jdtq5uKz-w4?large }}
+<HTML>
+<div class="java-online" style="height: 400px; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'BubbleSort'}">
+<script type="text/plain" title="bubbleSort.java">
+int[] zahlen = new int[10];
+// Mit Zufallszahlen belegen
+for(int i = 0; i < zahlen.length; i++) {
+   zahlen[i] = Random.randint(1, 100);
+}
+for(int i = 0; i < zahlen.length; i++) {
+   print(zahlen[i] + " ");
+}
+println();
+boolean fertig = false;
+while(!fertig) {
+   fertig = true;
+   // Sortieren!
+   // i zeigt auf die linke zu überprüfende Zahl
+   for(int i = 0; i < zahlen.length - 1; i++) {
+      if(zahlen[i] > zahlen[i + 1]) {
+         fertig = false;
+         int z = zahlen[i];
+         zahlen[i] = zahlen[i + 1];
+         zahlen[i + 1] = z;
+      }
+   }
+}
+println();
+for(int i = 0; i < zahlen.length; i++) {
+   print(zahlen[i] + " ");
+}
+</script>
+</HTML>
+===== Aufgabe 6 =====
+Schreibe ein Programm, das ein Feld mit 10 zufälligen ganzen Zahlen von 1 bis 100 füllt und ausgibt. Danach soll folgendes gemacht werden:
+  * a) Das Programm soll die größte der 10 Zahlen ausgeben.
+  * b) Das Programm soll die Summe der 10 Zahlen ausgeben.
+  * c) Das Programm soll untersuchen, ob das Feld mindestens zwei gleiche Zahlen enthält und dann ausgeben "Zwei gleiche Zahlen gefunden!" oder "Das Feld enthält lauter unterschiedliche Zahlen.".
+  * d) Das Programm soll die Reihenfolge der Zahlen im Feld umkehren, aus dem Feld [12, 3, 44, 8, 10, 1, 90, 50, 40, 30] soll also das Feld [30, 40, 50, 90, 1, 10, 8, 44, 3, 12] werden.
+[[.aufgabe6loesungen:start|Hier geht's zu den Lösungen!]]
+===== Aufgabe 7 =====
+Erweitere das Programm zum Sieb des Eratosthenes (Aufgabe 3, siehe oben) so, dass es am Ende nach Primzahlzwillingen sucht und die gefundenen Zwillinge ausgibt.
+<WRAP center round tip 60%>
+Sind zwei Primzahlen nur 2 voneinander entfernt, so spricht man von einem Primzahlzwilling. z.B.
+  * 3 und 5
+  * 5 und 7
+  * 11 und 13
+  * 17 und 19
+  * 29 und 31
+usw.
+</WRAP>
+[[.aufgabe7Loesung:start|Lösung]]
+===== Übungen vor der Kurzarbeit am 28.03.2025 =====
+[[.uebungenKurzarbeit:start|Hier entlang!]]