Zeichen vergleichen & aus einem String löschen

D

deiro

Grünschnabel
Guten Abend,

ich bräuchte bitte Hilfe bei einer Aufgabe:
Es sind 4 unterschiedliche binäre muster A - D gegeben, sowie eine Zeichenreihe str aus 0en und 1en. Ich soll aus str wiederholt Vorkommen der unterschiedlich Muster löschen, bis entweder nichts mehr übrig bleibt oder nur noch 1en. Das ganze soll rekursiv geschehen, ich schätze die verschränkte Rekursion wäre hier ganz gut. Hab das mit den Rekursionen aber noch nicht so wirklich verstanden... und das nächste problem ist, dass ich keinen schimmer habe wie man einzelne Zeichen eines Strings vergleichen und löschen kann :/
Geht das überhaupt? Oder sollte ich lieber einen StringBuilder verwenden?
Ich hab leider auch keinen Quelltext, da ich keinen richtigen Ansatz habe... ich bin für jeden Ansatz dankbar.

Grüße deiro
 
Als erfahrener Entwickler würde ich ja die Ersetzung mit einem Regex vornehmen per
https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#replaceAll(java.lang.String, java.lang.String)

Die Frage ist ob du in deiner Ausbildung Regexe schon verwenden darfst oder auf ein anderes Mittel entsprechend eures Kapitels zugreifen solltest. Das kann ich dir nicht beantworten.


Rekursion ist eigentlich nicht schwer. Du folgst einem bestimmten Muster
Java: 
public Ergebnis doSomething(Foo bar) {
// Abbruch wenn bar eine bestimmte Bedingung erfüllt
// verändere bar
// rekursiver Aufruf mit verändertem bar - return
}
 
Regex kam bei uns noch nicht vor, ich gucks mir mal an. Wir gehen nach dem Buch "Sprechen Sie Java" und haben jetzt bis Kapitel 9 (Strings) und zusätzlich noch Kapitel 16 (Rekursion) gelesen. Ich finde da sind Rekursionen nicht so gut erklärt.
Danke aufjedenfall für deine Antwort.
 
Rekursion ist fast immer untrennbar mit dem/einem spezifischen (für nat. Zahlen/auf Bäumen/allg. auf induktiven Datentypen) Induktionsprinzip verbunden imo. Habt ihr Induktion mal angesprochen?
Angenommen, du wüsstest, wie man für einen String mit (n-1) Vorkommnissen deines Musters das Muster entfernt: und zwar alle bis auf das letzte Vorkommnis. Dann könntest du auch einen Algorithmus schreiben, um einen String mit n Vorkommnissen zu behandeln: Einfach den für (n-1) starten und danach das letzte Vorkommniss entfernen: indexOf(string, Muster) => resulting string = substr(anfang bis indexOf) + substr(indexOf + Musterlänge, Ende).

Wir haben oben keine Annahmen an n getroffen - bis auf eine (!): n >= 1, sonst würden wir (0-1)=-1 schreiben, was wir erst einmal nicht definiert haben.
Man hat z. B. für n=50 eine riesige Annahmenkette, die man sich basteln kann: Angenommen, ich wüsste es für 49... für 49: angenommen, ich wüsste es für 48... für 38: angenommen, ich wüsste es für 47 usw.... für 1: angenommen, ich wüsste es für 0. Halt stop! Bei 0 wissen wir es nicht, da wir n >= 1 gefordert haben.
Für n = 0 müssen wir also tatsächlich einen Algorithmus angeben, aber der ist einfach: Gebe den Eingabestring unverändert zurück.
 
Wir haben gesagt bekommen, das Induktion ein wichtiger Bestandteil von Rekursionen ist, haben es aber nur angeschnitten. Ich bin halt noch ein totaler Anfänger und habs bisher ganz gut hingekriegt, aber diese Rekursionen machen mich fertig. Ich hab auch schon kleine Beispiele dazu gesehen und kann sie nachvollziehen, aber selber schreiben kriege ich irgendwie nicht hin. In dieser Aufgabe soll es glaube ich eine verschränkte Rekursion sein, also 2 oder mehr methoden die sich gegenseitig aufrufen. Ich hatte überlegt für jedes Muster eine Methode zu schreiben (also 4 Stk) und str dann einfach immer weiterzugeben.
Bei einem Kommilitonen bin ich der Meinung, habe ich gesehen das er das mit nur 2 methoden gemacht hat. Jedoch weiß ich nicht wie. Danke auch für deine Hilfe ComFreek, ich werds später nochmal versuchen.
 
Rekursion ist einfach, es muss nur mal klick machen, danach hast du eigentlich nie wieder Probleme damit.

Ganz ehrlich, eine verschränkte Rekursion habe ich in der Praxis noch nie gesehen und ich kann mir auch nicht unbedingt vorstellen, dass das in diesem Fall sinnvoll ist. Nur weil du eine einfache Methode in einer Rekursion aufrufst ist diese dann nicht gleich verschränkt. Natürlich könntest du alle 4 zikular aufrufen, aber dann wird es schwer mit der Abbruchbedingung.


Mache auf keinen Fall 4 Methoden! Wenn du die Ersetzung selbst in eine Methode auslagern möchtest, dann bitte
Java: 
public String ersetzeMusterInZeichenkette(String zeichenkette, String muster) {
    // z.B. mit Substring (siehe ComFreak)
}
Dann kannst du für alle Muster die gleiche Methode aufrufen, also 4x innerhalb einer Rekursion. Die Abbruchbedingung kannst du in diesem Fall auch nach diesen Aufrufen stellen und abbrechen, sofern sich die Zeichenkette nach dem Ersetzen nicht von der Eingangszeichenkette unterscheiden. Es wurde also keines der 4 Muster gefunden.
 
Was noch ganz wichtig bei Rekursion ist: Versuche niemals die Aufrufhierarchien selbst abzuwickeln! Also die Funktion beim rekursiven Aufruf selbst einsetzen und wieder einsetzen usw. Das versteht kein Mensch mehr bei komplizierteren Rekursionen, z. B. bei den Türmen von Hanoi (Algorithmus siehe Wikipedia)! Rekursive Aufrufe entwickeln und verstehen tut man am besten über das Induktionsprinzip dahinter: "Wenn der rekursive Aufruf mir das Richtige liefert [Induktionsvoraussetzung], und ich das Richtige nun mit diesem Ergebnis mache für n+1 [Induktionsschritt], dann ist meine Funktion korrekt."

deiro hat gesagt.:
Ich soll aus str wiederholt Vorkommen der unterschiedlich Muster löschen
Zum Vergrößern anklicken....
Ah, das hatte ich überlesen: Die Muster können auch gemischt drin vorkommen. Vielleicht wird von euch sowas erwartet:
Javascript: 
function deletePattern1(str) {
  // im Basisfall
  return deletePattern2(str);
}
function deletePattern2(str) {
  // im Basisfall
  return deletePattern3(str);
}
function deletePattern3(str) {
  // im Basisfall
  return deletePattern4(str);
}
function deletePattern4(str) {
  // im Basisfall
  return str;
}

Das ist aber eine nicht gerade sinnvolle Idee ;) Es kann also auch gut etwas Anderes gemeint sein.
 
Ich würde gerne die komplette Aufgabenstellung hier rein machen, aber hier kann man scheinbar keine screenshots einfach so einfügen. Ich bin mir auch nicht ganz sicher ob ihr mich richtig verstanden habt^^ aber trotzdem vielen Dank für eure Hilfe. Muss die Aufgabe morgen abgeben, werde dann wohl auf die Musterlösung warten..
 
@comfreak, ich schätze damit ist das gemeint:

Angenommen du hast den String ABBACC

Pattern1 sei AA, dann löschst du Pattern2 BB und der String enthält nun AA, also muss wiederholt gesucht werden.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück