arrays

[julia123]

so sieht die Aufgabe aus:

Eine Softwarekomponente zum Test, ob ein Feld von ganzen Zahlen Duplikate enth¨alt, werde durch folgenden JUnit–
Test gestestet:
package duplikate;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import org.junit.Test;
public class DuplikateTest {
@Test
public void test() {
assertTrue(Duplikate.duplikatFrei(new int[]{}));
assertTrue(Duplikate.duplikatFrei(new int[]{1}));
assertTrue(Duplikate.duplikatFrei(new int[]{1,2,3,4,5,6,7,8,9,0}));
assertFalse(Duplikate.duplikatFrei(new int[]{1,2,3,4,5,6,7,8,9,0,0}));
assertFalse(Duplikate.duplikatFrei(new int[]{1,1,2,3,4,5,6,7,8,9,0}));
assertFalse(Duplikate.duplikatFrei(new int[]{1,2,3,4,5,5,6,7,8,9,0}));
assertFalse(Duplikate.duplikatFrei(new int[]{1,2,3,4,5,5,6,7,8,9,0,1}));
assertFalse(Duplikate.duplikatFrei(new int[]{1,2,3,4,5,6,2,7,8,9,0}));
}
}


Schreiben Sie eine zum Test passende Softwarekomponente, die auf Duplikate testet und Rekursion nutzt.


Hinweis: Der rekursive Test auf Freiheit von Duplikaten kann durch folgendes Verfahren realisiert werden:
(i) Ein Feld mit weniger als zwei Elementen ist stets frei von Duplikaten.
(ii) a[0..n] ist frei von Duplikaten, wenn a[0..n-1] frei von Duplikaten ist
und a[n] nicht in a[0..n-1] vorkommt.
Dabei kann eine Hilfsfunktion eingesetzt werden, die neben dem Feld einen zweiten Parameter hat, der angibt, bis zu
welchem Index das Feld untersucht werden soll.

 

[sheel]

Zuerst etwas Theorie:
a)
Beim iterativen Code oben wird ja prinzipiell so vorgegangen,
dass für jedes Element vom Ersten bis zum Letzten
alle Elemente nach diesem damit verglichen werden
0->1 2 3 4...
1->2 3 4...
2->3 4...
Der Bereich vom Array, den man untersucht,
wird also von vorne weg immer etwas kleiner geschnitten
(die vorderen Elemente vorm aktuellen bleiben ja uninteressant)

Der Hinweis zur Rekursion zur prinzipiellen Vorgehensweise ist das Selbe,
nur wird von hinten begonnen.
Man beginnt mit dem Letzten und prüft alle davor auf Gleichheit,
dann das Vorletzte mit allen davor, das Vorvorletzte mit allen davor...
die Elemente hinter dem Aktuellen sind hier also die Uninteressanten.

(Es steht nicht dabei, dass man es in der Reihenfolge Hinten-Vorne machen muss,
nur kann. Umgekehrt wirds also auch kein Problem sein)

b)
Eine Rekursion hat ja den Sinn, etwas zu wiederholen.
Wie eine Schleife, nur auf eine andere Art.
Oft kann man Schleifen<->Rekursion beide jeweils in andere umschreiben.

Im iterativen Code gibt es ja zwei verschachtelte Schleifen,
prinzipiell kann man jetzt also drei verschiedene rekursive Möglichkeiten machen:
Eine, die die außere Schleife rekursiv löst; eine für die Innere;
und eine Variante, wo beide Schleifen ersetzt werden.

Der Hinweis in der Aufgabe deutet auf eine bestimmte Art hin:
Man darf für ein bestimmtes Element alle (vorne/hinten) prüfen,
und zwar in der Methode -> Schleife.
Nur das Durchlaufen der "Haupt"-Elemente beim Vergleich soll per Rekursion passieren.


Man darf einen zusätzlichen Parameter haben:
Da wird dann übergeben, welches Element gerade das Hauptelement ist.

Um endlich zum Code zu kommen:
Zuerst mal eine Methode, die für ein einzelnes Element prüft,
ob alle danach etwas gleich sind.
Welches Element das Hauptelement ist wird eben per Parameter mitgegeben.

static boolean duplikatFeldHilfsfunktion(int[] x, int i) {
    boolean result = false;
    for (int j = i + 1; x.length > j; j++) {
         if (x[i] == x[j]) {
                result = true;
                break;
         }
    }
    return result;
}

Das ist praktisch die iterative Funktion ohne der äußeren Schleife.
Die Schleife hat ja alle Elemente durchlaufen (die innen jeweils das Hauptelement waren),
jetzt gehts ja nur um eins.

Jetzt wäre es noch gut, damit etwas Rekursion reinkommt,
dass beim Aufruf für Index 0 nicht nur das ganze Array auf Doppel zu [0] untersucht wird,
sondern auch die Untersuchung für das nächste Element gestartet wird.
Und hier ist der Knackpunkt vom Ganzen:
Es reicht, das jeweils Nächste Element zu startet,
weil das ja wieder sien Nächstes startet usw...bis zum Ende.
Vom Prinzip her sowas:

static boolean duplikatFeldHilfsfunktion(int[] x, int i) {
    boolean result = false;
    for (int j = i + 1; x.length > j; j++) {
         if (x[i] == x[j]) {
                result = true;
                break;
         }
    }
    if(!result) //NEU
        result = duplikatFeldHilfsfunktion(x, i + 1); //NEU
    return result;
}

Man untersucht zuerst die Sache mit dem eigenen Element,
dann startet man die Untersuchung fürs Nächste.
Wieviel Nächste-Untersuchungen da drin dann verschachtelt ablaufen ist einem an der Stelle egal.

Warum das if:
Wenn schon in der Schleife festgestellt wurde,
dass es Duplikate gibt, kann man sich die
restliche Untersuchung sparen und einfach true zurückgeben.
Nur wenn man in der Schleife nichts gefunden hat zählt das Ergebnis vom Rest.


Ein Problem gibts aber noch:
Irgendwann ist man beim Letzten Element im Array
und muss dort erkennen, dass es beim Element i+1 nichts mehr gibt (und man damit fertig ist)
Code zuerst:

static boolean duplikatFeldHilfsfunktion(int[] x, int i) {
    boolean result = false;
    for (int j = i + 1; x.length > j; j++) {
         if (x[i] == x[j]) {
                result = true;
                break;
         }
    }
    if(!result && (i+1) < x.length) //NEU
        result = duplikatFeldHilfsfunktion(x, i + 1);
    return result;
}

Wenn also das Element Nummer i+1 noch existiert,
dann kann die Funktion mit dem Element als Hauptding aufgerufen werden.
Sonst einfach nichts mehr tun.

 

[julia123]

Das kommt auf mein Spickzettel , Spaß. Sehr Gut erklärt vielen Dank !

 

[sheel]

Ich hätt damit kein Problem, aber wenn du erwischt wirst bist selbst schuld

Und eigentlich wollte ich oben noch was dazuschreiben:
Jetzt gibt es ja die duplikatFeldHilfsfunktion mit Parametern Array und Index.
Wie der Name sagt, das ist eine Hilfsfunktion.
Die eigentliche Funktion soll ja nur ein Array bekommen, also ohne Index aufrufbar sein.

Die Hilfsfunktion startet ja bei einem Index jeweils den Nächsten mit,
und dieser wieder den Nächsten usw.
Alles, was in der Hauptfunktion also zu tun ist:
Die Hilfsfunktion mit Index 0 aufrufen
(und das Array natürlich auch mitgeben,
dass bei der Hauptfunktion ja auch schon ein Parameter ist).