MINT lernen

Projekt: Bücherverwaltung

Wo steht „Momo“ — und wie viele Bücher muss das Programm anschauen, bis es das weiß?

1

Erst planen

  • Auftrag:die Schulbibliothek will Bücher aufnehmen, nach Titel finden, verleihen und die freien Bücher zählen.
  • Buch:jedes Buch kennt titel, autor und ob es ausgeliehen ist.
  • Bibliothek:hält alle Bücher in einer ArrayList<Buch> — im Diagramm - buecher: Liste vom Typ Buch.
  • Assoziation:eine Bibliothek verwaltet beliebig viele Bücher (*) — eine Linie zwischen den Klassenkarten.
  • Reihenfolge:erst Buch bauen und testen, dann hinzufuegen, dann suche, zuletzt ausleihen und anzahlVerfuegbar.
Bibliothek
  • - buecher: Liste vom Typ Buch
  • c Bibliothek()
  • + hinzufuegen(buch: Buch)
  • + suche(titel: Zeichenkette): Buch
  • + ausleihen(titel: Zeichenkette): Wahrheitswert
  • + anzahlVerfuegbar(): Ganzzahl
verwaltet1*
Buch
  • - titel: Zeichenkette
  • - autor: Zeichenkette
  • - ausgeliehen: Wahrheitswert
  • c Buch(titel: Zeichenkette, autor: Zeichenkette)
  • + getTitel(): Zeichenkette
  • + getAutor(): Zeichenkette
  • + istAusgeliehen(): Wahrheitswert
  • + setAusgeliehen(ausgeliehen: Wahrheitswert)

Der Plan: Bibliothek kennt ihre Bücher, ein Buch weiß nichts von der Bibliothek.

2

Umsetzen und testen

  • suche:for-each über alle Bücher, Titel mit equals vergleichen, beim Treffer sofort return b;.
  • Nicht gefunden:erst nach der Schleife return null; — null heißt „kein Objekt“.
  • ausleihen:nutzt suche; false, wenn das Buch fehlt oder schon verliehen ist.
  • Testen:Erwartung vorher notieren: ausleihen("Momo") → true, noch einmal → false, ausleihen("Emil") ohne Emil im Regal → false.
public Buch suche(String titel) {
    for (Buch b : buecher) {
        if (b.getTitel().equals(titel)) {
            return b;
        }
    }
    return null;
}

public boolean ausleihen(String titel) {
    Buch b = suche(titel);
    if (b == null || b.istAusgeliehen()) {
        return false;
    }
    b.setAusgeliehen(true);
    return true;
}

Stelle ein, wie viele Bücher im Regal stehen und wo „Momo“ steht — mit den Reglern, per Klick auf ein Buch oder mit den Pfeiltasten am gelben Buch. Starte die Suche und miss die Vergleiche. „Alle Fälle messen“ probiert jeden Platz durch.

Wie viele Vergleiche braucht die Suche?

MessungBücher n„Momo“ auf PlatzVergleiche

Halte fest: Die Suche vergleicht von vorn nach hinten. Steht das Buch auf Platz k, braucht sie genau k Vergleiche; fehlt es, vergleicht sie alle n Bücher. Mehr Bücher heißt im Mittel proportional mehr Arbeit.

Herleitung:

\(V_{\mathrm{Mittel}}=\dfrac{1+2+3+\dots+n}{n}\)
| Paare bilden
Start: jeder der n Plätze ist gleich wahrscheinlich; Platz k kostet k Vergleiche.
\(V_{\mathrm{Mittel}}=\dfrac{\tfrac{n}{2}\cdot(n+1)}{n}\)
| : n kürzen
Erste und letzte Zahl ergeben n + 1, ebenso zweite und vorletzte — das sind n/2 solche Paare.
\(V_{\mathrm{Mittel}}=\dfrac{n+1}{2}\)
Ergebnis
Bei 40 Büchern also im Mittel 20,5 Vergleiche — genau das zeigt „Alle Fälle messen“.
Merke

Lineare Suche in n Büchern: mindestens \(1\), höchstens \(n\), im Mittel \(\dfrac{n+1}{2}\) Vergleiche.

3

Allgemeine Hinweise

return null nicht in die Schleife

Steht return null; als else-Zweig in der Schleife, bricht suche schon nach dem ersten Buch ab — „Momo“ auf Platz 5 wird nie gefunden.

null prüfen, bevor du es benutzt

suche("Emil").getAutor() stürzt ab, wenn Emil fehlt: NullPointerException. Erst if (b != null), dann zugreifen.

Klein anfangen, oft testen

Nach jeder Methode ein kurzes main mit drei Büchern ausführen. Ein Fehler in zehn neuen Zeilen ist schneller gefunden als in hundert.

Videos