Lernpfad:Rekursion in Java/Selbst eine rekursive Methode schreiben: Unterschied zwischen den Versionen

Zur Navigation springen Zur Suche springen

Lernpfad:Rekursion in Java/Selbst eine rekursive Methode schreiben (Quelltext anzeigen)

Version vom 29. Januar 2020, 00:04 Uhr

740 Bytes entfernt ,  00:04, 29. Jan. 2020
→‎Suche in einem Array
Zeile 53: Zeile 53:
{{Lösung:End}}
{{Lösung:End}}


== Suche in einem Array ==
== Binäre Suche rekursiv ==
Ein häufiges Problem ist die Suche nach einem speziellen Element.


=== Suche in einem unsortieren Array===
Die Möglichkeiten zur Suche ein einem Array ist dir schon bekannt. Sind die Daten nicht vorsortiert, dann muss die ''lineare Suche'' angewandt werden, liegen die Daten sortiert vor, dann kann die Suche mit der ''binären Suche'' beschleunigt werden.
Das einfachste Beispiel ist die Suche der Position einer Zahl in einem Array.  
 
<syntaxhighlight lang="java">
Die binäre Suche lässt sich auch gut rekursiv umsetzen: Der Algorithmus zerlegt das Problem in zwei (in etwa) gleichgroße Teilprobleme. Das eine kann sofort entschieden werden: Es enthält das gesuchte Element auf keinen Fall. Auf den anderen Teil wird derselbe Algorithmus wieder angewandt. So lange, bis das Element gefunden wurde, oder bis das aktuelle Teilproblem leer ist.
public class Zahlenarray{
  int[] zahlen;
  public Zahlenarray(){
      zahlen = int[10];
      for(int i = 0; i<zahlen.length;i++){
        zahlen[i] = (int)(Math.random()*10);
      }
  }
}
</syntaxhighlight>


{{Aufgabe:Start}}
{{Aufgabe:Start}}
<lückentext>
Implementieren sie die rekursive binäre Suche in einer Methode mit der Signatur
Fügen Sie die Methode <code>public int gibPosition(int z)</code> zusammen, die die Position einer Zahl im Array zurückgibt. Falls die Zahl nicht vorhanden ist, soll <code>-1</code> als Position zurückgegeben werden.
'''public_int_gibPosition(int_z){'''
    '''int pos = -1;'''
    '''for&#40;int i=0; i < zahlen.length; i++&#41;{'''
        '''if&#40;zahlen[i]==z&#41;{'''
            '''pos = i;'''
        '''}'''
    '''}'''
    '''return pos;'''
'''}'''
</lückentext>
{{Aufgabe:End}}


=== Suche in einem unsortierten Kartenhaufen ===
<pre>
Sucht man in einem heruntergefallenen Kartenstapel nach einer speziellen Karte, so muss man sich alle Karten ansehen, da sie in keiner speziellen Ordnung herunterfallen, sondern völlig durcheinander sind.
public int binaereSucheRekursiv( int suchzahl, int[] sucharray, int von, int bis )
</pre>


<syntaxhighlight lang="java">
Die Methode soll als Ergebnis die Position des Elements im Array zurückgeben, oder <code>-1</code>, wenn es nicht vorhanden ist.
public class Karte{
  private String farbe;
  private String wert;
  public Karte(){
      String[] farben = {"Kreuz", "Pik", "Herz", "Karo"};
      String[] werte = {"5","6","7","8","9","10","Bube","Dame","König","Ass"};
      farbe = farben[(int)(Math.random()*farben.length())];
      wert= werte[(int)(Math.random()*wert.length())];
  }


  public boolean istGleich(String pFarbe, String pWert){
Überlegen sie sich zunächst konkret, wie die drei Bestandteile der Rekursion hier aussehen müssen.
      return farbe.equals(pFarbe) && wert.equals(pWert);
{{Aufgabe:End}}
  }
{{Lösung:Start}}
<syntaxhighlight lang="java" line="1">
public int binaereSucheRekursiv( int suchzahl, int[] sucharray, int von, int bis ) {
    if( von > bis ) { // Abbruchbedingung
        return -1; // Abbruch der Rekursion
    } else {
        // (int) "schneidet" die Nachkommastellen ab
        int mitte = (int)((von+bis)/2);
        if( suchzahl < sucharray[mitte] ) {
            // Rekursionsaufruf und Reduktion auf die linke Hälfte
            return binaereSucheRekursiv(suchzahl, sucharray, von, mitte-1);
        } else if( sucharray[mitte] < suchzahl ) {
            // Rekursionsaufruf und Reduktion auf die rechte Hälfte
            return binaereSucheRekursiv(suchzahl, sucharray, mitte+1, bis);
        } else {
            // Element gefunden
            return mitte;
        }
    }
}
}
</syntaxhighlight>
</syntaxhighlight>
{{Lösung:End}}
In der Regel werden nicht einfach nur Zahlen sortiert, sondern Objekte mit Eigenschaften, die verglichen werden. Die Sortierung kann dann nach verschiedenen Kriterien erfolgen.
Spielkarten werden zum Beispiel zuerst nach der [[wikipedia:Farbe_(Kartenspiel)|Farbe]] und dann nach dem Kartenwert sortiert.


In Java können die Karten in einem Array verwaltet werden:
<syntaxhighlight lang="java" line="1">
<syntaxhighlight lang="java">
public class Karte {
public class Kartenhaufen{
    private String farbe;
  private Karte[] haufen;  
    private int wert;
  public Kartenhaufen(){
      
     haufen = new Karte[32];
     public Karte( String pFarbe, int pWert ) {
     for (int i= 0; i<haufen.length;i++){
          farbe = pFarbe;
      haufen[i] = new Karte(); // Erzeugt eine zufällige Karte
          wert = pWert;
     }
     }
  }


  public Karte sucheKarte(String farbe, String wert){
    public String getFarbe() {
    for (int i=0; i< haufen.length;i++){  
        return farbe;
      Karte k = haufen[i];                         
      if(k.istGleich(farbe,wert)){       
        return k;                                  
      }                                   
     }
     }
  }
   
</syntaxhighlight>
    public int getWert() {
 
        return wert;
Erläuterungen:
{{Collapse:Start }}
<syntaxhighlight lang="java">
  public Karte sucheKarte(String farbe, String wert){
    for (int i=0; i< haufen.length;i++){  //Der ganze Array soll durchlaufen werden.
      Karte k = haufen[i];                //Die aktuelle Karte wird aus dem Array
                                          //geholt und eine Referenz k auf das Element wird erstellt.
      if(k.getFarbe().equals(farbe) &&    //Die Daten der aktuellen Karte k
        k.getWert().equals(wert)){       //werden mit der Farbe und dem Wert verglichen
        return k;                         //Falls die Werte übereinstimmen,
                                          //wird eine Referenz auf die aktuelle Karte k zurückgegeben.
      }                                    //Die Methode wird dann sofort beendet.
     }
     }
  }
}
</syntaxhighlight>
</syntaxhighlight>
{{Collapse:End}}
{{Aufgabe:Start}}
 
Implementiere eine binäre Suche für Karten-Objekte der Klasse <code>Karte</code> oben.
Z.B. die Telefonnummer in einem Telefonbuch. Das Telefonbuch ist nur deshalb praktikabel, weil es die Namen der Personen geordnet angibt. In einem geordneten Array kann man also schneller suchen, als in
{{Aufgabe:End}}
Abgerufen von „http://ngb.schule/wiki/Spezial:Mobiler_Unterschied/5572“

Navigationsmenü