Informatik II - Übung 7

Pascal Schärli

othello@pascscha.ch

06.11.2020

Nachbesprechung

Pascal Schärli 06.11.2020

Klassen

Pascal Schärli 06.11.2020

Eine Zuweisung ist dann möglich ist, falls die neue Klasse (links) weiter oben im selben Ast wie die bereits existierende Klasse (rechts) ist.

D d = new D();
C c = d;
//E e = d;

Klassen

Pascal Schärli 06.11.2020

Beim Casten kommt es also nicht darauf an, was Java denkt, dass das Objekt ist, sondern als was es erstellt wurde. Solange alle nötigen Informationen vorhanden sind, ist ein Cast möglich.

B b = new D();
C c = (C) b;
//E e = (E) b;

Polymorphie

package u6a3;

/**
 * abstract class for geometric objects
 */
public abstract class GeometricObject implements Comparable {
    public abstract int area();

    public boolean smallerThan(Comparable rhs) {
        GeometricObject other = (GeometricObject) rhs;
        return this.area() < other.area();
    }
}

Pascal Schärli 06.11.2020

Polymorphie

private GenericList insertSorted(GenericList list, Object value) {
    if (list == null) return new GenericList(value, null);

    Comparable lhs = (Comparable) value;
    Comparable rhs = (Comparable) list.value;
    if (lhs.smallerThan(rhs)) return new GenericList(value, list);

    list.next = insertSorted(list.next, value);
    return list;
}

public GenericList sort(GenericList list) {
    if (list == null) return null;
    return insertSorted(sort(list.next), list.value);
}

Pascal Schärli 06.11.2020

Vorlesung

Pascal Schärli 06.11.2020

Generics

ArrayList myList = new ArrayList();

myList.add(42);
myList.add(“I <3 Info II”);

int i = (Integer)myList.get(0);
String s = (String)myList.get(1);

Eine ArrayList kann beliebige Typen speichern:

  • Flexibel, aber Casts sind gefährlich
  • Falls man nicht mehr weiss, was wo in der Liste ist, kann es zu Chaos führen
  • \(\rightarrow\) Generics

Pascal Schärli 06.11.2020

Generics

ArrayList<Integer> myList = new ArrayList<Integer>();
myList.add(42);
int i = myList.get(0);
myList.add(“Hello World”);

Man kann einer ArrayList sagen, dass sie nur einen bestimmten Typ speichern darf:

  • Vorteile:
    • Typsicherheit
    • keine Casts nötig
  • Nachteile:
    • Weniger Flexibel

Compile-Error

Pascal Schärli 06.11.2020

Generics - Beispiel

public class Tree<T> {

  private T value;
  Tree right;
  Tree left;
  
  public Tree(T value) {
    right = null;
    left = null;
    this.value = value;
  }
  
  public T getValue() {
  	return value;
  }

  public void setValue(T v) {
  	value = v;
  }
}
Tree<Integer> tree1 = new Tree<Integer>(5);
tree1.right = new Tree<Integer>(3);
tree1.left = new Tree<Integer>(6);

Tree<String> tree2 = new Tree<String>("root");
tree2.right = new Tree<String>("left");
tree2.left = new Tree<String>("right");

5

3

6

"root"

"left"

"right"

tree1

tree2

Pascal Schärli 06.11.2020

Binäre Suchbäume

1

3

5

6

9

10

12

18

20

19

22

  • Alle Elemente im linken Ast sind kleiner
     
  • Alle Elemente im rechten Ast sind grösser
     
  • \(\rightarrow\) kleinstes Element ganz links
     
  • \(\rightarrow\) grösstes Element ganz rechts

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

18

20

19

22

Element Finden:
  Falls die Wurzel das gesuchte Element ist
    -> gefunden!
  
  Falls der geschte Wert kleiner als die Wurzel ist
    -> Links weitersuchen
    
  Falls der geschte Wert grösser als die Wurzel ist
    -> Rechts weitersuchen

Gesucht: 9

Binäre Suchbäume - Element Finden

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

18

20

19

22

Element Finden:
  Falls die Wurzel das gesuchte Element ist
    -> gefunden!
  
  Falls der geschte Wert kleiner als die Wurzel ist
    -> Links weitersuchen
    
  Falls der geschte Wert grösser als die Wurzel ist
    -> Rechts weitersuchen

Gesucht: 9

Binäre Suchbäume - Element Finden

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

18

20

19

22

Element Finden:
  Falls die Wurzel das gesuchte Element ist
    -> gefunden!
  
  Falls der geschte Wert kleiner als die Wurzel ist
    -> Links weitersuchen
    
  Falls der geschte Wert grösser als die Wurzel ist
    -> Rechts weitersuchen

Gesucht: 9

Binäre Suchbäume - Element Finden

Pascal Schärli 06.11.2020

Binäre Suchbäume - Element Finden

1

3

5

6

9

10

12

18

20

19

22

Element Finden:
  Falls die Wurzel das gesuchte Element ist
    -> gefunden!
  
  Falls der geschte Wert kleiner als die Wurzel ist
    -> Links weitersuchen
    
  Falls der geschte Wert grösser als die Wurzel ist
    -> Rechts weitersuchen

Gesucht: 9

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

18

20

19

22

Element Finden:
  Falls die Wurzel das gesuchte Element ist
    -> gefunden!
  
  Falls der geschte Wert kleiner als die Wurzel ist
    -> Links weitersuchen
    
  Falls der geschte Wert grösser als die Wurzel ist
    -> Rechts weitersuchen

Gesucht: 15

Binäre Suchbäume - Element Finden

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

18

20

19

22

Element Finden:
  Falls die Wurzel das gesuchte Element ist
    -> gefunden!
  
  Falls der geschte Wert kleiner als die Wurzel ist
    -> Links weitersuchen
    
  Falls der geschte Wert grösser als die Wurzel ist
    -> Rechts weitersuchen

Gesucht: 15

Binäre Suchbäume - Element Finden

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

18

20

19

22

Element Finden:
  Falls die Wurzel das gesuchte Element ist
    -> gefunden!
  
  Falls der geschte Wert kleiner als die Wurzel ist
    -> Links weitersuchen
    
  Falls der geschte Wert grösser als die Wurzel ist
    -> Rechts weitersuchen

Gesucht: 15

Binäre Suchbäume - Element Finden

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

18

20

19

22

Element Finden:
  Falls die Wurzel das gesuchte Element ist
    -> gefunden!
  
  Falls der geschte Wert kleiner als die Wurzel ist
    -> Links weitersuchen
    
  Falls der geschte Wert grösser als die Wurzel ist
    -> Rechts weitersuchen

Gesucht: 15

Binäre Suchbäume - Element Finden

\(\rightarrow\) Nicht vorhanden

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

18

20

19

22

Element Finden:
  Falls grösser
    -> im rechten Teilbaum einfügen
    
  Falls kleiner
    -> im linken Teilbaum einfügen
    
  Falls Knoten noch nicht existiert
    -> fertig

Einfügen: 14

Binäre Suchbäume - Element Einfügen

14

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

18

20

19

22

Element Finden:
  Falls grösser
    -> im rechten Teilbaum einfügen
    
  Falls kleiner
    -> im linken Teilbaum einfügen
    
  Falls Knoten noch nicht existiert
    -> fertig

Einfügen: 14

Binäre Suchbäume - Element Einfügen

14

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

18

20

19

22

Element Finden:
  Falls grösser
    -> im rechten Teilbaum einfügen
    
  Falls kleiner
    -> im linken Teilbaum einfügen
    
  Falls Knoten noch nicht existiert
    -> fertig

Einfügen: 14

Binäre Suchbäume - Element Einfügen

14

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

18

20

19

22

Element entfernen - Methode 1
  Ersetzen durch kleinstes Element
  im rechten Teilbaum
  
Element entfernen - Methode 2
  Ersetzen durch grösstes Element
  im linken Teilbaum

Entfernen: 18

Binäre Suchbäume - Element Entfernen

14

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

20

22

Element entfernen - Methode 1
  Ersetzen durch kleinstes Element
  im rechten Teilbaum
  
Element entfernen - Methode 2
  Ersetzen durch grösstes Element
  im linken Teilbaum

Entfernen: 18

Binäre Suchbäume - Element Entfernen

19

14

Pascal Schärli 06.11.2020

1

3

5

6

9

10

12

19

20

22

Element entfernen - Methode 1
  Ersetzen durch kleinstes Element
  im rechten Teilbaum
  
Element entfernen - Methode 2
  Ersetzen durch grösstes Element
  im linken Teilbaum

Entfernen: 6

Binäre Suchbäume - Element Entfernen

14

Pascal Schärli 06.11.2020

1

3

5

9

10

12

20

22

Element entfernen - Methode 1
  Ersetzen durch kleinstes Element
  im rechten Teilbaum
  
Element entfernen - Methode 2
  Ersetzen durch grösstes Element
  im linken Teilbaum

Entfernen: 6

Binäre Suchbäume - Element Entfernen

19

14

Pascal Schärli 06.11.2020

1

3

5

9

10

12

19

20

22

Gib den Wert vom Knoten aus
Gib den Linken Teilbaum in Pre-Order aus
Gib den Rechte Teilbaum in Pre-Order aus

Binäre Suchbäume - Preorder

14

12 5 3 1 9 10 19 14 20 22

Pascal Schärli 06.11.2020

1

3

5

9

10

12

19

20

22

Gib den Linken Teilbaum in In-Order aus
Gib den Wert vom Knoten aus
Gib den Rechte Teilbaum in In-Order aus

Binäre Suchbäume - Inorder

14

1 3 5 9 10 12 14 19 20 22

Pascal Schärli 06.11.2020

1

3

5

9

10

12

19

20

22

Gib den Linken Teilbaum in Post-Order aus
Gib den Rechte Teilbaum in Post-Order aus
Gib den Wert vom Knoten aus

Binäre Suchbäume - Postorder

14

1 2 10 9 5 14 22 20 19 12

Pascal Schärli 06.11.2020

Spielbäume

Spielregeln:

  • Die Spieler können abwechslungsweise entweder 1 oder 2 Zündhölzer ziehen.
  • Der Spieler, welcher das letzte Zündholz nimmt hat verloren.

Blau

gewinnt

Blau

gewinnt

Grün

gewinnt

Grün

gewinnt

Grün

gewinnt

Pascal Schärli 06.11.2020

Spielbäume

Spielregeln:

  • Die Spieler können abwechslungsweise entweder 1 oder 2 Zündhölzer ziehen.
  • Der Spieler, welcher das letzte Zündholz nimmt hat verloren.

Blau

gewinnt

Blau

gewinnt

Grün

gewinnt

Grün

gewinnt

Grün

gewinnt

Blau

gewinnt

Blau

gewinnt

Grün

gewinnt

Grün

gewinnt

Grün

gewinnt

Grün

gewinnt

Grün

gewinnt

\(\Rightarrow\) Grün gewinnt!

Pascal Schärli 06.11.2020

Pascal Schärli 06.11.2020

Vorbesprechung

Pascal Schärli 06.11.2020

  • Gegeben: Liste von Übungsgruppen
    • groups = ArrayList \(\leftarrow \{group1, group2, \dots\}\)
      • group1 = ArrayList \(\leftarrow \{student1, student2, \dots\}\)
      • group2 = ArrayList \(\leftarrow \{student21, student22, \dots\}\)
      • \(\dots\)
  • Jeder Student hat eine gewisse Punktzahl erreicht
    • myStudent.getPoints()
  • Aufgabe: ArrayList aller Studente, welche eine gewisse Punktzahl erreicht haben
    1. filterRaw \(\rightarrow\) Filter mit ArrayList als raw type implementieren
      \(\rightarrow\) Viel Casten
    2. filterGeneric \(\rightarrow\) Filter mit ArrayList als generic type implementieren
      \(\rightarrow\) ArrayList<ArrayList<Student>>

Pascal Schärli 06.11.2020

X ist am Zug - wer gewinnt?

  • Spielbaum aufzeichnen
     
  • Resultate von unten nach oben eintragen (1 \(\rightarrow\) Sieg, 0 \(\rightarrow\) Unentschieden, -1 \(\rightarrow\) Niederlage)
     
  • Wie wird das Spiel ausgehen, wenn beide perfekt spielen?
     
  • Analog zu unserem Streichholz-Beispiel

Pascal Schärli 06.11.2020

  • Entfernt nacheinander die Elemente 15, 12 und 20
     
  • Verwendet Strategie "Ersetzen durch kleinstes Element des rechten Teilbaums"
     
  • Zeichnet den resultierenden Baum nach jedem Entfernen

Pascal Schärli 06.11.2020

  • Implementiert das Interface IBinarySerachTreeUtils<T>
     
  • Generics \(\rightarrow\) Verwendet T als euer Datentyp.
     
  • Pro Knoten werde 2 Attribute gespeichert:
    • int key: Die id von eurem Element. Sortiert euren Baum nach diesem Attribut
    • T thing: Ein Objekt, welches im Baum gespeichert wird
       
  • Die benötigten Algorithmen habe ich im Best-Of erklärt

Pascal Schärli 06.11.2020

  • Super Möglichkeit praktische Programmierkentnisse zu sammeln
  • Viel Prüfungsrelevanter Stoff wurde in den Reversi Übungen vertieft
  • Sehr viel Spass
  • Tolle Preise beim Turnier
  • Schaut, ob ihr meinen Bot Trash.Can auf der Webseite schlagen könnt (machbar)
  • Bei Fragen zögert nicht, Ich helfe sehr gerne

Pascal Schärli 06.11.2020

Das Reversi.jar File könnt ihr in den Properties wie J-Unit einfügen

Pascal Schärli 06.11.2020

Um ein Spiel zu starten müsst Ihr dafür eine neue Run-Configuration erstellen:

  1. Run \(\rightarrow\) Run Configurations (im dropdown-Menu links vom Grünen Run-Knopf)
  2. Rechtsklick auf JavaApplication \(\rightarrow\) new Configuration
  3. Name: Reversi (oder was auch immer)
    Project: u7
    Main class: reversi.Arena
  4. Wählt Tab Arguments
  5. Program arguments: -t 0 -r 50 TestGame u7a4.HumanPlayer u7a4.HumanPlayer
  6. Apply
  7. Run

Pascal Schärli 06.11.2020

  • Implementiert einen "Random Player", welcher zufällig spielt

  • Lasst euch vom "Human Player" inspirieren

  • Benutzt Generics ArrayList<Coordinates> um die legalen Spielpositionen zu speichern

  • Bei Fragen helfe ich sehr gerne

Pascal Schärli 06.11.2020

Viel Spass!

Pascal Schärli 06.11.2020