Algorithmen und Programmierung II

Übungsblatt 9 - Musterlösung


Aufgabe 1

Das Programm wird durch die folgende schrittweise Verfeierung entwickelt.
kursiv: zu verfeinernder Schritt

Fertiges Programm (Testlauf):
import java.io.*;

public class DHondt {

    static BufferedReader br = new BufferedReader(
                                       new InputStreamReader(System.in));
    /** "Hauptprogramm" */
    public static void main(String[] args) throws IOException {
        int[] stimmen    = stimmenLesen();
        int   sitze      = intLesen("Anzahl der Sitze: ");
        int[] verteilung = verteilungBerechnen(stimmen, sitze);
        verteilungAusgeben(verteilung);
    }

    /** erfragt die Anzahl von Parteien und liest deren Stimmen ein */
    static int[] stimmenLesen() throws IOException {
        int anz = intLesen("Anzahl der Parteien: ");
        int[] stimmen = new int[anz];
        System.out.println("Stimmenzahl eingeben:");
        for (int i = 0; i < stimmen.length; i++)
            stimmen[i] = intLesen("Partei " + (i + 1) + ": ");
        return stimmen;
    }

    /** liest wiederholt, bis gültiger int-Wert eingeben */
    static int intLesen(String nachricht) throws IOException {
        System.out.print(nachricht);
        for (;;)
            try { return Integer.parseInt(br.readLine()); }
            catch (NumberFormatException e) {
                System.out.print(
                       "Zahl konnte nicht gelesen werden, bitte wiederholen: ");
            }
    }

    /** Verteilung nach dem d'Hondt'schen Höchstzahlenverfahren */
    static int[] verteilungBerechnen(int[] stimmen, int sitze) {
        double[] hzahlen = new double[stimmen.length];  // "Höchstzahlen"
        int[] verteilung = new int[stimmen.length];     // Rückgabewert
        for (int i = 0; i < stimmen.length; i++)        // erste Höchstzahl
            hzahlen[i] = stimmen[i];                    //  = Stimmenanzahl
        while (sitze-- > 0) {
            int partei = 0; 
            for (int i = 1; i < hzahlen.length; i++)    // größte H.zahl best.
                if (hzahlen[i] > hzahlen[partei]) partei = i;
            verteilung[partei]++;                       // Partei erhält Sitz
            hzahlen[partei] = (double) stimmen[partei]  // nächste H.zahl f. 
                              / (verteilung[partei]+1); // Partei bestimmen
        }
        return verteilung;
    }

    static void verteilungAusgeben(int[] verteilung) {
        System.out.println("\nSitzverteilung:");
        for (int p = 0; p < stimmen.length; p++)
            System.out.println("Partei " + (p + 1) + ": "  + 
                               verteilung[p] + " Sitze");
    }
}

Aufgabe 2

Ausgangspunkt für die Entwicklung ist die Beschreibung des Programmverhaltens: Die Namen der Teilnehmer werden eingelesen, dann werden ein oder mehrere Rennen durchgeführt, bis der Benutzer das Programm beendet. Vor einem weiteren Rennen wird die Rangliste gelöscht. Diese Schritte bilden das "Hauptprogramm" und werden als Methoden realisiert, die schrittweise verfeinert werden.

Es werden zwei einfach verkettete Listen verwaltet: eine Startliste und eine Rangliste. Für beide werden Klassen definiert, die die relevanten Methoden zur Verfügung stellen. Elemente der Listen sind Teilnehmer-Objekte. Die Listen enthalten die selben Teilnehmer-Objekte in unterschiedlichen Reihenfolgen. Neue Teilnehmer-Objekte werden am Ende der Startliste eingefügt. In die Rangliste wird nach dem zeit-Attribut von Teilnehmer sortiert eingefügt.

Der Schritt "Teilnehmer einlesen" wird in Form einer Schleife realisiert, die beendet wird, wenn der Benutzer ohne Eingabe eines Namens <return> drückt. Die Durchführung eines Rennens besteht aus einer Schleife über alle Teilnehmer der Startliste. Für jeden wird die Zeit eingelesen (verfeinert in intLesen), und das Teilnehmer-Objekt wird (sortiert) in die Rangliste eingefügt (verfeinert in einfuegen in der Klasse Rangliste). Dann wird die aktuelle Rangliste dargestellt (ausgeben in der Klasse Rangliste).

import java.io.*;

public class Rennen {

    static BufferedReader br = new BufferedReader(
                                       new InputStreamReader(System.in));
    static Startliste sl = new Startliste();
    static Rangliste  rl = new Rangliste();

    /** "Hauptprogramm" */
    public static void main(String[] args) throws IOException {
        teilnehmerEinlesen();
        int i = 1;
        do {
            System.out.println("\n" + (i++) + ". Rennen - Zeiten eingeben:");
            rennen();
            rl.loeschen();
        } while(endeAbfragen());
    }

    /** liest Teilnehmernamen und baut Startliste auf, Abschließen mit <return> */
    static void teilnehmerEinlesen() throws IOException {
        System.out.println("Namen eingeben (Beenden mit <return>):\n");
        String name;
        for (int i = 1; ; i++) {
            System.out.print("Teilnehmer " + i + ": ");
            name = br.readLine();
            if (name.equals("")) break;
            else sl.einfuegen(new Teilnehmer(name));
        }
    }

    /** list wiederholt bis Eingabe 'j' (Rückgabe true) oder 'n' (false) */
    static boolean endeAbfragen() throws IOException {
        String s = null;
        do {
            System.out.print("\nRennen beendet. Neues Rennen? (j/n) ");
            s = br.readLine();
        } while (s == null || !(s.equals("j") || s.equals("n")));
        return s.equals("j");
    }

    /** führt einen "Lauf" durch: liest für jeden Teilnehmer die Zeit ein
     *  und gibt jeweils die aktuelle Rangliste aus */
    static void rennen() throws IOException {
        Teilnehmer t = sl.erster;
        while (t != null) {
            System.out.print("\nZeit für Teilnehmer \"" + t.name + "\": ");
            t.zeit = intLesen();
            rl.einfuegen(t);
            rl.ausgeben();
            t = t.naechsterStarter;
        }
    }
    
    /** liest wiederholt, bis gültiger int-Wert eingeben */
    static int intLesen() throws IOException {
        for (;;)
            try { return Integer.parseInt(br.readLine()); } 
            catch (NumberFormatException e) {
                System.out.print(
                    "Zahl konnte nicht gelesen werden, bitte wiederholen: ");
            }
    }
}

/** Elemente von Start- und Rangliste */
class Teilnehmer {
    String name;
    int zeit;
    Teilnehmer naechsterStarter,   // für verkettete Startliste 
               naechsterRang;      // für verkettete Rangliste
    
    Teilnehmer(String name) {
        this.name = name;
    }
}

/** eine verkettete Liste von Teilnehmern in Einfügereihenfolge */
class Startliste {
    Teilnehmer erster, letzter;  // Anfang und Ende der Liste

    void einfuegen(Teilnehmer t) {
        if (erster == null) {
            erster = letzter = t;
        } else {
            letzter.naechsterStarter = t;
            letzter = t;
        }
    }
}

/** eine verkettete Liste von Teilnehmern, sortiert nach Teilnehmer.zeit */
class Rangliste {
    Teilnehmer erster;

    /** sortiertes Einfügen, Schlüssel: Teilnehmer.zeit */
    void einfuegen(Teilnehmer t) {
        if (erster == null || erster.zeit >= t.zeit) {
            t.naechsterRang = erster;
            erster = t;
        } else { // mind. ein Vorgänger
            Teilnehmer test = erster, vorg = null;
            do {
                vorg = test;
                test = test.naechsterRang;
            } while (test != null && test.zeit < t.zeit);
            t.naechsterRang = test;
            vorg.naechsterRang = t;
        }
    }

    void ausgeben() {
        Teilnehmer t = erster;
        System.out.println("\nRangliste:");
        for (int i = 1; t != null; i++, t = t.naechsterRang)
            System.out.println(i + ": " + t.name + " (" + t.zeit + " s)");
    }
    
    /** Rangliste löschen, Teilnehmer bleiben jedoch in Startliste */
    void loeschen() {
        Teilnehmer test = erster;
        erster = null;
        while (test != null) {
            Teilnehmer naechster = test.naechsterRang;
            test.naechsterRang = null;
            test = naechster;
        }
    }
}
Testlauf