Lernkarten

Karten 106 Karten
Lernende 8 Lernende
Sprache Deutsch
Stufe Universität
Erstellt / Aktualisiert 15.01.2013 / 10.02.2020
Lizenzierung Kein Urheberrechtsschutz (CC0)
Weblink
Einbinden
0 Exakte Antworten 106 Text Antworten 0 Multiple Choice Antworten
Fenster schliessen

Implementieren Sie eine Methode boolean istEnthalten(String wert, String[] feld), die überprüft, ob die übergebene Zeichenkette im Feld enthalten ist. Was müssen Sie hierbei im Gegensatz zur Implementierung für Felder primitiver Typen beachten?

 

Die Elemente sollten nicht mit ==, sonder mit Hilfe der Methode equals() verglichen werden.

    boolean istEnthalten(String wert, String[] feld) {        if (feld == null) {            return false;        }        for (String s : feld) {            // Wert gefunden?            if (s.equals(wert)) {                return true;            }        }        return false;    }
 

 

Fenster schliessen

Implementieren Sie eine Methode int bestimmeAnzahl(int wert, int[] feld), die zählt,

wie oft der übergebene Wert in dem Feld enthalten ist.

 

 

 

    int bestimmeAnzahl(int wert, int[] feld) {        if (feld == null) {            return 0;        }        int anzahl = 0;        for (int i : feld) {            // Wert gefunden?            if (i == wert) {                anzahl++;            }        }        return anzahl;    }
Fenster schliessen

Gegeben seien die folgenden Klassen

public class Kunde {     // ... } 

public class Rechnung {    

private Kunde rechnungsempfaenger;     // ...  

      

public Kunde liefereRechnungsempfaenger() {        

return this.rechnungsempfaenger;    

}     

public int bestimmeBetragInCent() {       

                // ...    

          }

     // ...

}  

 

public class Rechnungssammlung {    

private Rechnung[] rechnungen;   

      // ...

}

 

Implementieren Sie eine Methode

int bestimmeGesamtbetragAllerRechnungenVon(Kunde k)

in der Klasse Rechnungssammlung, die die Summe aller Rechnungsbeträge dieses Kunden in Cent bestimmt.

 

 

    int bestimmeGesamtbetragAllerRechnungenVon(Kunde k) {        // wenn kein Kunde oder keine Rechnungen vorhanden        if (k == null || rechnungen == null) {            return 0;        }        int betrag = 0;        // alle Rechnungen betrachten        for (Rechnung r : rechnungen) {            // wenn gesuchter Kunde            if (r.liefereRechnungsempfaenger() == k) {                // Betrag dazuaddieren                betrag += r.bestimmeBetragInCent();            }        }        return betrag;    }

 

 

Fenster schliessen

Implementieren Sie eine Methode Rechnung findeTeuersteRechnung() in der Klasse Rechnungssammlung, die die Rechnung mit dem größten Betrag bestimmt.

 

Rechnung findeTeuersteRechnung() {   // wenn keine Rechnungen vorhanden    if (rechnungen == null) {        return null;    }    Rechnung max = null;    // alle Rechnungen betrachten    for (Rechnung r : rechnungen) {        // wenn noch kein Maximum gefunden        // oder aktuelle Rechnung teurer        if (max == null || max.bestimmeBetragInCent()                            < r.bestimmeBetragInCent()) {            // Maximum anpassen            max = r;        }    }    return max;}
Fenster schliessen

Wie können in einem Feld Teilfolgen ermittelt werden?

 

 

Man beginnt damit, den ersten Wert des Feldes mit dem ersten Wert der Zahlenfolge zu vergleichen. Stimmen die Werte überein, vergleicht man anschließend die zweiten Werte und so weiter. Stimmen die Werte nicht überein, so weiß man lediglich, dass die Zahlenfolge nicht beim ersten Element des Feldes beginnend gefunden werden kann. Man beginnt dann mit dem zweiten Element des Feldes und vergleicht es mit dem ersten der gesuchten Folge. Stimmen diese überein, so vergleicht man anschließend das dritte mit dem zweiten und so weiter. Wurde die gesamte Teilfolge gefunden, so kann die Methode beendet werden. Bei der Implementierung müssen wir aufpassen, dass wir nicht auf ungültige Feldelemente zugreifen.

Fenster schliessen

Wie können in einem Feld Teilfolgen ermittelt werden?

 

boolean istTeilfolge(int[] feld, int[] gesuchteFolge) {        // es muss nicht bis zum letzten Element gesucht werden,        // da dort die Folge nicht mehr vollständig vorkommen kann        for (int i = 0; i < feld.length                             - gesuchteFolge.length + 1; i++) {            for (int j = 0; j < gesuchteFolge.length; j++) {                // Vergleiche entsprechende Einträge                if (feld[i + j] != gesuchteFolge[j]) {                    // Zahl an Position j stimmt nicht überein                    // suche bei i+1 weiter                    break;                } else if (j == gesuchteFolge.length - 1) {                    // gesamte Folge wurde gefunden                    return true;                }            }        }        // Teilfolge konnte nicht vollständig gefunden werden        return false;    }
Fenster schliessen

Implementieren Sie eine Methode int bestimmeAnfangdesWorts(char[] feld, String wort), die die Position zurückliefert, ab der das Wort vollständig im Feld gefunden wurde. Wird das Wort nicht vollständig gefunden, so soll -1 zurückgeliefert werden.

 

    int bestimmeAnfangdesWorts(char[] feld, String wort) {        for (int i = 0; i < feld.length - wort.length() + 1; i++) {            for (int j = 0; j < wort.length(); j++) {                // Vergleiche entsprechende Buchstaben                if (feld[i + j] != wort.charAt(j)) {                    // Buchstabe an Position j stimmt nicht überein                    // suche bei i+1 weiter                    break;                } else if (j == wort.length() - 1) {                    // gesamtes Wort wurde gefunden                    return i;                }            }        }        // Wort konnte nicht vollständig gefunden werden        return -1;    }
Fenster schliessen

Wie kann das suchen in großen Datenbeständen beschleunigt werden?

 

Wenn die Datenelemente gemäß einer Ordnungsrelation sortiert werden. Der Suchalgorithmus kann diese Eigenschaft nutzen, um ein bestimmtes Element in der sortierten Menge zu finden.

Fenster schliessen

Schreiben eine Methode, die Aufsteigend ein einfaches Feld sortiert.

 

void sortiereAufsteigend(int[] feld) {        // beginne beim zweiten Element und betrachte         // die Liste bis zum Index i - 1 als sortiert        for (int i = 1; i < feld.length; i++) {            // gehe solange von i nach links            // bis das Element an die richtige            // Stelle gerutscht ist            for (int j = i;  j > 0; j--) {                if (feld[j - 1] > feld[j]) {                    // wenn linkes groesser,                    // vertausche die Elemente                    int temp = feld[j];                    feld[j] = feld[j - 1];                    feld[j - 1] = temp;                   } else {                    // das Element ist                    // an der richtigen Stelle                    break;                }            }        }}
Fenster schliessen

 

Wie viele Vergleichs- und Vertauschungsoperationen benötigt der Algorithmus „Sortieren beim Einfügen“, um das folgende Feld zu sortieren?

    int[] beispiel = {4, 35, 23, 5, 2, 67, 45, 21};

Als Vergleich zählt die Auswertung der if-Bedingung.

Wir betrachten die drei Anweisungen im if-Block als eine Vertauschungsoperation.

Es werden 18 Vergleiche und 12 Vertauschungen benötigt.

Fenster schliessen

Entwerfen Sie eine Methode void sortiereAbsteigend(String[] feld), die absteigend ein Feld von Zeichenketten sortiert.

 

   void sortiereAbsteigend(String[] feld) {        // beginne beim zweiten Element und betrachte        // die Liste bis zum Index i - 1 als sortiert        for (int i = 1; i < feld.length; i++) {            // gehe solange von i nach links            // bis das Element an die richtige            // Stelle gerutscht ist            for (int j = i; j > 0; j--) {                if (feld[j - 1].compareTo(feld[j]) < 0) {                    // wenn linkes kleiner,                    // vertausche die Elemente                    String temp = feld[j];                    feld[j] = feld[j - 1];                    feld[j - 1] = temp;                } else {                    // sonst, ist das Element                    // an der richtigen Stelle                    break;                }            }        }    }
Fenster schliessen

Schreiben Sie eine Methode, die ein Feld nach dem klassischer Sortierungsalgorithmus Bubblesort bearbeitet.

 

void bubblesort(int[] feld) {        // es werden  maximal feld.length - 1 Durchläufe benötigt        for (int i = 0; i < feld.length - 1; i++) {            // solange keine Vertauschungen vorgenommen werden            // ist das Feld sortiert            boolean sorted = true;            // Durchlaufe das Feld, in jedem Durchlauf muss            // ein Element weniger berücksichtigt werden            for (int j = 0; j < feld.length - 1 - i; j++) {                if (feld[j] > feld[j + 1]) {                    // wenn linkes größer                    // dann vertausche                    int temp = feld[j];                    feld[j] = feld[j + 1];                    feld[j + 1] = temp;                       // Feld ist nicht sortiert                    sorted = false;                }            }            if (sorted) {                // keine Vertauschungen, Feld ist                 // folglich vollständig sortiert                break;            }        }    }
 
Fenster schliessen

Entwerfen Sie mit Hilfe des Bubblesort-Algorithmus eine Methode void sortiereAufsteigend(Rechnung[] rechnungen), die die Rechnungen aufsteigend nach ihren Beträgen sortiert.

 

void sortiereAufsteigend(Rechnung[] rechnungen) {        // es werden maximal length - 1 Durchläufe benötigt        for (int i = 0; i < rechnungen.length - 1; i++) {            // solange keine Vertauschungen vorgenommen werden            // ist das Feld sortiert            boolean sorted = true;            // Durchlaufe das Feld, in jedem Durchlauf muss            // ein Element weniger berücksichtigt werden            for (int j = 0; j < rechnungen.length - 1 - i; j++) {                if (rechnungen[j].bestimmeBetragInCent()                        > rechnungen[j + 1].bestimmeBetragInCent()) {                    // wenn linkes größer dann vertausche                    Rechnung temp = rechnungen[j];                    rechnungen[j] = rechnungen[j + 1];                    rechnungen[j + 1] = temp;                    // Feld ist nicht sortiert                    sorted = false;                }            }            if (sorted) {                // keine Vertauschungen, Feld ist                // folglich vollständig sortiert                break;            }        }    }
Fenster schliessen

Der Algorithmus „Sortieren durch Auswählen“ (engl. selection sortselection sortselection sort) nimmt am Anfang das komplette Feld als unsortiert an, sucht sich das größte Element unter den unsortierten Elementen und vertauscht es, wenn nötig, anschließend mit dem letzten Element des unsortierten Bereichs.

Im nächsten Schritt gehört das letzte Element nun zum sortierten Bereich. Es wird wiederum das größte Element des unsortierten Bereichs mit dem letzten Element vertauscht, so dass es anschließend zum sortierten Bereich gehört. Der Algorithmus terminiert, wenn der unsortierte Bereich aus einem Element besteht.

Wenden Sie den Algorithmus auf das folgende Feld an und zählen Sie die dabei nötigen Vergleichs- und Vertauschungsoperationen .

    int[] beispiel = {4, 35, 23, 5, 2, 67, 45, 21};

Es werden 28 Vergleiche und 6 Vertauschungen benötigt.

Fenster schliessen

Implementieren Sie die Methode void sortiere(double[] feld) so, dass sie das übergebene Feld mit Hilfe des Algorithmus „Sortieren durch Auswählen“ sortiert.

 

void sortiere(double[] feld) {        // suche length-1 mal das Maximum        for (int i = 0; i < feld.length - 1; i++) {            // Position des Maximums            int max = 0;            // Suche das Maximum            for (int j = 1; j < feld.length - i; j++) {                // wenn aktueller Wert größer als Maximum                if (feld[j] > feld[max]) {                    // speichere aktuelle Position                    max = j;                }            }            // setzte das Maximum an die letzte der unsortierten            // Positionen, wenn es dort nicht schon ist            if (max != feld.length - 1 - i) {                double temp = feld[max];                feld[max] = feld[feld.length - 1 - i];                feld[feld.length - 1 - i]  = temp;            }        }    }
 

 

Fenster schliessen

Wann ist eine Methode oder Funktion Rekursiv?

 

Ein Algorithmus ist rekursiv, wenn er Methoden (oder Funktionen) enthält, die sich selbst aufrufen.

Jede rekursive Lösung umfasst zwei grundlegende Teile:

·       den Basisfall, für den das Problem auf einfache Weise gelöst werden kann, und

·       die rekursive Definition.

Die rekursive Definition besteht aus drei Facetten:

1.die Aufteilung des Problems in einfachere Teilprobleme,

2.die rekursive Anwendung auf alle Teilprobleme und

3.die Kombination der Teillösungen in eine Lösung für das Gesamtproblem.

Bei der rekursiven Anwendung ist darauf zu achten, dass wir uns mit zunehmender Rekursionstiefe an den Basisfall annähern. Wir bezeichnen diese Eigenschaft als Konvergenz der Rekursion.

 

Fenster schliessen

Was passiert, wenn die Methode summeRekursiv() mit negativen Werten aufgerufen wird? Wie kann dieses Problem gelöst werden?

 

Es tritt ein StackOverflowError auf. Um dies zu verhindern, kann bei negativen Werten entweder eineIllegalArgumentException geworfen oder die Abfrage n == 0 durch n <= 0 ersetzt werden.

 

 

Fenster schliessen

Implementieren Sie eine Methode fakultaetIterativ    (int n), die iterativ die Fakultät berechnet und eine MethodefakultaetRekursiv(int n), die die Fakultät rekursiv berechnet. Die Methoden sollen dabei nur Werte  akzeptieren.

 

  int fakultaetIterativ(int n) {        // ungültige Werte abfangen        if (n < 0) {            throw new IllegalArgumentException();        }        // Ergebnis initialisieren        int erg = 1;        for (int i = 2; i <= n; i++) {            erg *= i;        }        return erg;    }    int fakultaetRekursiv(int n) {        // ungültige Werte abfangen        if (n < 0) {            throw new IllegalArgumentException();        }        // Basisfall        if (n == 0) {            return 1;        }        // rekursiver Aufruf        return n * fakultaetRekursiv(n - 1);    }
Fenster schliessen

Begründen Sie, warum die Lösung für fakultaetRekursiv() konvergiert.

 

 

 

In jedem Schritt wird n um eins verringert. Somit nähert sich n immer weiter an den Basisfall 0 an.

 

 

Fenster schliessen

Schreiben Sie die Methode double power(int p, int n), die für zwei ganze Zahlen  und  rekursiv den Wert  berechnet. Testen Sie Ihr Programm und vergleichen Sie es mit der Lösung von Selbsttestaufgabe 14.1-2, die eine iterative Variante aufzeigt.

 

 

public double power(int p, int n) {        if (n < 0) {            return 1.0 / power(p, -n);        }        if (n == 0) {            return 1;        }        return p * power(p, n - 1);    }
Fenster schliessen

Berechnen Sie alle Fibonacci-Zahlen bis und schreiben Sie die passenen Methode.

0, 1, 1, 2, 3, 5, 8, 13, 21

 

    long fibRekursiv(int n) {        if (n < 0) {            throw new IllegalArgumentException();        }        // Basisfall: n ist 0 oder 1        if (n == 0 || n == 1) {            return n;        }        // sonst: rekursiver Aufruf        return fibRekursiv(n - 1) + fibRekursiv(n - 2);    }
 

 

Fenster schliessen

Implementieren Sie eine iterative Lösung für die Berechnung der Fibonacci-Zahlen in der Methode long fibIterativ(int n).

 

    long fibIterativ(int n) {        if (n < 0) {            throw new IllegalArgumentException();        }        // Basisfall: n ist 0 oder 1        if (n == 0 || n == 1) {            return n;        }        // die ersten beiden Zahlen        int a = 0; // fib(0)        int b = 1; // fib(1)        // berechne die nächsten Zahlen        for (int i = 2; i <= n; i++) {            // fib(i) = fib(i - 1) + fib(i - 2);            int temp = a + b;            // Werte für nächste Berechnung            // speichern            a = b;            b = temp;        }        return b;     }
Fenster schliessen

Implementieren Sie eine Methode long zufallszahl(int n), die rekursiv f(n) berechnet. Implementieren Sie außerdem eine Methode void gebeZufallszahlenAus(), die die Pseudozufallszahlen f(5) bis einschließlich f(30) ausgibt.

  long zufallszahl(int n) {

        // Basisfall n < 3        if (n < 3) {            return n + 1;        }        // rekursive Aufrufe        long f1 = zufallszahl(n - 1);        long f2 = zufallszahl(n - 2);        long f3 = zufallszahl(n - 3);        // berechne Ergebnis        return 1 + (((f1 - f2) * f3) % 100);    }    void gebeZufallszahlenAus() {        for (int i = 5; i < 30; i++) {            System.out.println(zufallszahl(i));        }    }
Fenster schliessen

Ein Palindrom ist ein Wort, dass sowohl vorwärts als auch rückwärts gelesen das gleiche ist.

Implementieren Sie die Methode boolean istPalindromIterativ (String s), die iterativ prüft ob es sich bei der Zeichenkette um ein Palindrom handelt.

 

    boolean istPalindromIterativ(String s) {        int laenge = s.length();        // betrachte erste Haelfte des Wortes        for (int i = 0; i < s.length() / 2; i++) {            // und prüfe ob korrespondierendes            // Zeichen identisch ist            if (s.charAt(i) != s.charAt(laenge - 1 - i)) {                return false;            }        }        // alle Zeichen passen        return true;    }
Fenster schliessen

Der Begriff Palindrom lässt sich auch rekursiv definieren. Ein Wort aus einem oder keinen Zeichen ist immer ein Palindrom. Ein längeres Wort ist dann ein Palindrom, wenn der erste und letzte Buchstabe identisch sind und der Rest der Zeichenkette, also ohne den ersten und letzten Buchstaben, auch ein Palindrom ist.

Implementieren Sie die Methode boolean istPalindromRekursiv (String s), die mit Hilfe der rekursiven Definition prüft, ob es sich bei der Zeichenkette um ein Palindrom handelt.

 

    boolean istPalindromRekursiv(String s) {        // Basisfall        if (s.length() <= 1) {            return true;        }        // erstes und letztes Zeichen vergleichen        if (s.charAt(0) != s.charAt(s.length() - 1)) {            return false;        }        return istPalindromRekursiv(s.substring(                                        1, s.length() - 1));    }
Fenster schliessen

Führen Sie auf dem folgenden Feld eine binäre und eine lineare Suche nach dem Element 38 aus. Wie viele Vergleiche benötigen Sie, bis Sie das Element gefunden haben?

int[] y = {3, 7, 14, 16, 18, 22, 27, 29, 30, 34, 38, 40, 50};

 

 

Bei der linearen Suche sind genau 11 Vergleiche nötig, bis der Wert gefunden wird.

Bei der binären Suche werden die folgenden Schritte und Vergleiche durchgeführt: start =  0 und ende = 12 => mitte =  6 => Vergleich mit 27     start =  7 und ende = 12 => mitte =  9 => Vergleich mit 34     start = 10 und ende = 12 => mitte = 11 => Vergleich mit 40     start = 10 und ende = 10 => Basisfall  => Vergleich mit 38

Es finden insgesamt 4 Vergleiche mit den Werten 27, 34, 40 und 38 statt.

Fenster schliessen

Ergänzen Sie die Klasse Binaersucher um eine Methode boolean istEnthalten(String s, String[] feld), die mit Hilfe einer binären Suche prüft, ob die Zeichenkette in dem Feld enthalten ist. Sie können sich dabei Hilfsmethoden definieren. Hilfsmethoden sollten nach dem Geheimnisprinzip gekapselt sein.

 

// wir gehen von einem sortierten Feld aus    boolean istEnthalten(String s, String[] feld,                                            int start, int ende) {        // Basisfall: Bereich enthält maximal 2 Elemente        if (ende - start <= 1) {            return feld[start].equals(s) || feld[ende].equals(s);        }        // sonst: rekursive Aufteilung        // Mitte bestimmen        int mitte = start + (ende - start) / 2;        System.out.println(mitte + " " + feld[mitte]);        if (feld[mitte].equals(s)) {            // wert gefunden            return true;        }        if (feld[mitte].compareTo(s) > 0) {            // in linker Hälfte suchen            return istEnthalten(s, feld, start, mitte - 1);        } else {            // in rechter Hälfte suchen            return istEnthalten(s, feld, mitte + 1, ende);        }    }
Fenster schliessen

Quicksort Teil 1:

Für das Sortieren von Feldern gibt es beispielsweise den Algorithmus Quicksort. Bei diesem Verfahren wird zufällig ein Element des Feldes als sogenanntes Pivotelement ausgewählt. Anschließend werden die Elemente des Feldes aufgeteilt. In dem einen Teil befinden sich alle Elemente, die kleiner als das Pivotelement sind und im anderen alle, die größer als das Pivotelement sind. Anschließend werden beide Teile wiederum mit dem gleichen Verfahren aufgeteilt. Bei Teilen mit maximal zwei Elementen kann die Sortierung dann direkt vorgenommen werden. Anschließend ist das gesamte Feld sortiert.Abb.  34-6 veranschaulicht dieses Verfahren.

 

void quicksort(int[] feld, int start, int ende) {        // Basisfall: leeres Feld        if (ende < start) {            return;                    }        // Basisfall: maximal 2 Elemente,        if (ende - start <= 1) {            // wenn nötig die beiden Werte vertauschen            if (feld[start] > feld[ende]) {                int temp = feld[start];                feld[start] = feld[ende];                feld[ende] = temp;            }            return;        }        // Feld aufteilen        int grenze = aufteilen(feld, start, ende);        // linken Teil (ohne Pivot) Sortieren        quicksort(feld, start, grenze - 1);        // rechten Teil (ohne Pivot) Sortieren        quicksort(feld, grenze + 1, ende);    }

 

Fenster schliessen

Quicksort Teil 2

 

// teilt die Elemente auf und liefert die// Position des Pivotelements zurückint aufteilen(int[] feld, int start, int ende) {    // Index von links    int l = start + 1;    // Index von rechts    int r = ende;     // Pivotelement    int pivot = feld[start];    // Umsortierung    while (l < r) {        // erstes Element größer als Pivot finden        while(feld[l] <= pivot && l < r) {            l++;        }
        // erstes Element kleiner als Pivot finden        while(feld[r] > pivot && l < r) {            r--;        }        // Elemente vertauschen        int temp = feld[l];        feld[l] = feld[r];        feld[r] = temp;                    }    // Indizes haben sich getroffen    // prüfen ob Grenze korrekt    if(feld[l] > pivot) {        // Grenze anpassen        l--;    }    // Grenze gefunden, Pivot entsprechend vertauschen    feld[start] = feld[l];    feld[l] = pivot;      return l;}
Fenster schliessen

Versuchen Sie, die einzelnen Schritte in der Implementierung mit Hilfe des folgenden Beispielaufrufs nachzuvollziehen.

int[] x = {12,2,6,1,8,34,10,7,20};quicksort(feld, 0, feld.length - 1);

Antwort siehe Abl.