Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
Tobias
Anmeldungsdatum: 15.02.2005 Beiträge: 149
|
Verfasst am: 05. Apr 2005 16:23 Titel: |
|
|
Es gibt verschiedene Arten von Rekursionen.
Bei einer Endrekursion (hier wird das Ergebnis z.B. in einem Argument akkumuliert) wird nichts anderes getan als linear an die Tiefe zu gehen und am Schluß nur noch alle return-Befehle abzuklappern. Die Endrekursion wird von optimierten Compilern in Schleifen verwandelt.
Im Allgemeinen werden Rekursionen natürlich nicht in Schleifen übersetzt. (Was auch ohne komplexere Strukturen wie Heaps, Queues oder Stacks auch nicht möglich ist.
Aber deine Lösung scheint auch noch fehlerhaft. Was wäre z.B. bei den Strings
"12341234123412345" und "12345".
Dann merkt der Algo, dass die ersten Zeichen übereinstimmen und wird neu aufgerufen mit stringVergleich("2341234123412345", "2345", 4)
D.h. sobald an einer Stelle die ersten zeichen übereinstimmen wird der Suchstring gekürzt und steht nichtmehr ganz zur Verfügung. |
|
Nach oben |
|
|
|
jovi
Anmeldungsdatum: 04.04.2005 Beiträge: 4 Wohnort: München
|
Verfasst am: 06. Apr 2005 22:40 Titel: |
|
|
Du hast natürlich vollkommen recht. Eigentlich wollte ich ja auch nur eine rekursive Lösung skizzieren. Also meine Verbesserung:
0) wenn Länge(array1) < zahl OR Länge(array2) < zahl dann return(false)
1) wenn die jeweils ersten zahl Zeichen der Strings gleich sind, dann return(true)
sonst return(stringVergleich(REST(array1), array2, zahl) OR stringVergleich(array1, REST(array2), zahl))
Nur die Lösung ist nun tatsächlich furchtbar ineffizient, da stringVergleich dauernd mit den selben Parametern aufgerufen wird. Um das Ganze auch effizient zu machen müsste man sich tatsächlich alle schon einmal durchlaufenen stringVergleich-Aufrufe
in einem globalen 2-dimensionalen Feld merken. Was Besseres fällt mir im Moment leider nicht ein. |
|
Nach oben |
|
|
Georg Administrator
Anmeldungsdatum: 15.02.2005 Beiträge: 57 Wohnort: Aachen
|
Verfasst am: 09. Apr 2005 02:22 Titel: |
|
|
Hi,
da jede iterative Lösung besser ist als eine rekursive sollte sich das doch gut mit zwei for-Schleifen lösen lassen?
Da ich dieses Semester erst Java lerne, hier eine Lösung in Java-ähnlichem Pseudocode
Code: |
for (i = 0; i < array1.length-3; i++) {
for (j = 0; j < array2.length-3; j++) {
if (array1[i:3] == array2[j:3]) {
return true;
}
}
}
return false;
|
Die Notation array1[i:3] soll dabei den Teil von array1 angeben, der bei Zeichen i beginnt und 3 Zeichen lang ist. |
|
Nach oben |
|
|
kurellajunior Administrator
Anmeldungsdatum: 14.02.2005 Beiträge: 214 Wohnort: Berlin-Pankow
|
Verfasst am: 12. Apr 2005 12:58 Titel: |
|
|
Das entspräche der "Holzhammer" methode von Tobias. Zudem war eine rekursive Lösung weiter unten gesucht
Und wenn Du weiterliest, gibt es einen iterativen Vorschlag mit nur einer Schleife von mir
Woher hast Du denn die Pauschalaussage, jede iterative Lösung sei besser als eine rekursive? Wenns Dich interessiert, mach dazu einen Thread in der theoretischen Informatik auf
genug gezwinkert, Jan _________________
|
|
Nach oben |
|
|
Georg Administrator
Anmeldungsdatum: 15.02.2005 Beiträge: 57 Wohnort: Aachen
|
Verfasst am: 22. Apr 2005 00:51 Titel: |
|
|
Tatsächlich, die von mir dargebotene Lösung war ja schon da, allerdings gemein in theoretischen Aussagen versteckt.
Kurellajunior, hier können wir den Wettstreit iterativ gegen rekursiv ausdiskutieren. |
|
Nach oben |
|
|
|