Diese Rekursion...
-
ich habe angefangen aufzuschreiben:
3 + 1 und 3 + 2
dann habe ich zunächst mit 3 + 1 weitergemacht und die Blätter 4 + 1 und 4 + 2 angehangen. Und auch hier das gleiche wiederholt.
Irgendwann kommt man dann zu einem Punkt, wo das Ergebnis größer als 7 ist und braucht keine Blätter mehr einzeichnen.
Wenn man das alles gemacht hat, dann fängt man unten an und schreibt das Ergebnis auf. Bei 7 + 1 ist das 1, da hier die Abbruchbedingung erfüllt ist und 1 zurückgegeben wird. Ebenso bei 7 + 2. Beides wird addiert, da ja:
funk(n+1)+funk(n+2)Also ergibt sich als Ergebnis für 6 + 1 die 2. Bei 6 + 2 ist wieder die Abbruchbedingung erfüllt, also ergibt sich hier nur 1. Addiert man beides wieder zusammen hat man 3 und das ist das Ergebnis von 5 + 1... Und so geht das immer weiter und am Ende bleibt eben nur noch 8 und 5 über, was zusammen das Endergebnis 13 ergibt. Leider kann ich nicht so gut mit der Maus zeichnen, sonst wäre der Baum etwas leserlicher.
-
wow nein das ist super also bezieht sich das ganze im grunde genommen auf "die Anzahl der Funktionsaufrufe" bzw. weil ja immer 1 zurückgeben wird. Alle zusammenzählen wie auf deiner Skizze schön ersichtlich ist und das sind dann 13. Super jetzt hab ichs. Fettes DANKE !!
-
Dave01 schrieb:
wow nein das ist super also bezieht sich das ganze im grunde genommen auf "die Anzahl der Funktionsaufrufe" bzw. weil ja immer 1 zurückgeben wird. Alle zusammenzählen wie auf deiner Skizze schön ersichtlich ist und das sind dann 13. Super jetzt hab ichs. Fettes DANKE !!
Die Anzahl der Funktionsaufrufe ist aber nicht 13. Ich habe noch mal versucht den Baum besser darzustellen:
http://www.imgupload.org/images/1_baum2.pngDie rote Zahl bedeutet, dass das Ergebnis dieses Blattes 1 ist, da die Abbruchbedingung erreicht wurde. Und da gibt die Funktion laut des Codes ja eben 1 zurück. Und dann hangelt man sich von da an rückwärts hoch und muss eben noch die Summe bilden, da der Code ja sagt: return funk(n+1)+funk(n+2);
-
Oh, da ist ein Fehler. Der Strich vom grünen ganz oben in der Mitte müsste natürlich bei der 5 enden.
-
Danke dir, so eine kleine Grafik hilft schon um einiges weiter um es verständlich nachvollziehen zu können und auf die richtige Lösung zu kommen
-
Als weitere Übung kannst du ja mal testen, ob du es nun schaffst für diese Funktion (für n = 3) selber einen Baum zu erstellen:
int funk(int n) { if(n > 6) return 2; return funk(n+2) + funk(n+3) - 1; }Da die Abbruchbedingung und die Berechnung anders sind muss man da aufpassen, das man sich nicht vertut.
Der entstehende Baum ist übrigens vergleichsweise klein. Solltest du dann auch merken warum der so klein ist.
-
Nun möchte ich etwas weitergehen und muss ein mein Programm "Palindrome" auf eine Rekursive Art umschreiben.(oT12TO, gilt als Palindrome) Nach langen herumprobieren komme ich leider auf keine Lösung. Ich hoffe ihr könnt mir weiterhelfen.
So sieht das Grundkonzept aus:
#include <stdio.h> #include <stdlib.h> /*Filtert alle Sonderzeichen raus*/ void filter(char *s) { int i=0; int j=0; while(s[i] != '\0') { if((s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= 'a' && s[i] <= 'z') ) { s[j]=s[i]; j++; } i++; }s[j]='\0'; } /*Macht kleinbuchstaben zu großbuchstaben*/ void toUpper(char *s) { int i=0; while(s[i] != '\0') { if(s[i] >= 'a' && s[i] <= 'z') { s[i]-=32; } i++; } } int ja_nein(int anzahl, char *s, int temp) /*überprüfe auf Palindrome*/ { int i,j; for(i=0, j=anzahl; i < anzahl+1, j >= 0 ; i++, j--) /*i------><------j*/ { if(s[i] != s[j]) { temp++; } } return temp; } int main() { char *ptr; int i,j=0; int a=0; char buffer[100]; int tmp=0; int uebernahme; printf("\t\t\t\t=================\n"); printf("\t\t\t\tPointerPalindrome\n"); printf("\t\t\t\t=================\n\n\n"); ptr=buffer; printf("Eingabe: "); gets(ptr); filter(ptr); toUpper(ptr); a=strlen(ptr)-1; uebernahme=ja_nein(a, ptr, tmp); printf("\n"); if(uebernahme == 0) { printf("Your entered string is a PALINDROME!\n"); } else { printf("Your entered string is - NOT - a PALINDROME!\n"); } return 0; }
-
Ich geb dir mal nen Tipp, die ToUpper Funktion würde so aussehen:
void ToUpper(char *s) { if (*s) { if(*s >= 'a' && *s <= 'z') { *s -= 32; } ToUpper(s + 1); } }Wobei ich Rekursion in den meisten Fällen offen gesagt recht hässlich finde, wie auch hier. Warum nicht einfach so?
void ToUpper(char *s) { while (*s) { if (*s >= 'a' && *s <= 'z') *s -= 32; ++s; } }Edit: Und weiter: die "Laufvariablen" übergibst du einfach der Rekursiven Funktion. Die Funktionssignatur könnte dann zB. so aussehen:
int IsPalin(char *s, int i, int j)
-
Was spricht eigentlich dagegen, die Funktionen der <ctype.h> einzusetzen? (toupper() und isalpha()/isalnum())
Ansonstens zu deiner Funktion ja_nein(): (ich nehme mal an, die willst du rekursiv verwenden)
Was für einen Sinn hat denn der Parameter temp, den du dort übergibst? Das könnte genausogut eine lokale Variable sein.
Und die rekursive Definition eines Palindroms lautet in etwa: Ein Palindrom ist ein leeres Wort, ein einbuchstabiges Wort oder die Verkettung x p x für ein Palindrom p und einen Buchstaben x. In Code:bool palindrom(char* wort, int len) { if(len<=1) return true; else return wort[0]==wort[len-1] && palindrom(wort+1,len-2); }Allerdings gehen die meisten Menschen eher den umgekehrten Weg und versuchen aus einem rekursiven Programm ein iteratives zu bauen.
-
CStoll schrieb:
Was spricht eigentlich dagegen, die Funktionen der <ctype.h> einzusetzen? (toupper() und isalpha()/isalnum())
Eigentlich nichts, aber vielleicht der Lerneffekt
CStoll schrieb:
bool palindrom(char* wort, int len) { if(len<=1) return true; else return wort[0]==wort[len-1] && palindrom(wort+1,len-2); }Hm.. schöne Lösung, aber seit wann kennt C denn bool und true?
-
cooky451 schrieb:
Hm.. schöne Lösung, aber seit wann kennt C denn bool und true?
Da habe ich den Überblick verloren, ich dächte einer der neueren C-Standards hätte es eingeführt. Zur Not kannst du aber auch int und 1 dort verwenden, wenn dir das lieber ist
-
VERDAMMT, hab ich jetzt mal deine ToUpper und die ispalindrome eingebaut und das funktioniert ja wie ne eins.. nur leider fehlt mir einfach die Übung um auf das draufzukommen
-
Die Funktion ToUpper von euch habe ich mittlerweile verstanden, danke! bei der ispalindrome bin ich etwas verwirrt. Ich möchte ja dazulernen und habe deshalb mal meine etwas von euch abgeänderte Funktion geschrieben, so schaut es für mich als "leihe" sehr verständlicher aus. Bei einem Palindrome wird mir 1 ausgegeben, bei keinem Palindrome wird glaub ich eine Adresse ausgegeben auf jeden Fall mehrere Zahlen. Soll das so sein
int ispalr(char *s, int i, int len) /*Bsp für Aufruf:printf("%d", ispalr("OTTO", 0, 3));*/ { if(len<=1) { return 1; } if(s[i] == s[len]) { return ispalr(s, i+1, len-1); } }EDIT: Fehler gefunden: kann es aber so als Rekursiv verwendet werden.. sieht doch etwas anders aus als eure Varianten..?
int ispal(char *s, int i, int len) { if(len<=1) { return 1; } else { if(s[i] == s[len]) { return ispal(s, i+1, len-1); } else { return 0; } } }
-
Dave01 schrieb:
Die Funktion ToUpper von euch habe ich mittlerweile verstanden, danke! bei der ispalindrome bin ich etwas verwirrt. Ich möchte ja dazulernen und habe deshalb mal meine etwas von euch abgeänderte Funktion geschrieben, so schaut es für mich als "leihe" sehr verständlicher aus. Bei einem Palindrome wird mir 1 ausgegeben, bei keinem Palindrome wird glaub ich eine Adresse ausgegeben auf jeden Fall mehrere Zahlen. Soll das so sein
Wenn die Eingabe kein Palindrom ist, werden beide if()-Anweisungen übersprungen und du verlässt die Funktion ohne einen Rückgabewert anzugeben. Das nennt sich dann "undefiniertes Verhalten" und sollte einem guten Compiler zumindest eine Warnung wert sein.
EDIT: Fehler gefunden: kann es aber so als Rekursiv verwendet werden.. sieht doch etwas anders aus als eure Varianten..?
int ispal(char *s, int i, int len) { if(len<=1) { return 1; } else { if(s[i] == s[len]) { return ispal(s, i+1, len-1); } else { return 0; } } }Das ist nur optisch
ich hatte anstelle der inneren if()-Anweisung einen Ausdruck gebildet, der das selbe aussagt (der nutzt die Tatsache, daß die Vergleichsoperatoren auch 0 bzw. 1 liefern, sowie die Kurzschlußauswertung von &&). Allerdings haben deine Parameter eine andere Bedeutung als bei meinem Beispiel und da würde als Rekursionsabbruch schon if(len-i<1)ausreichen.
-
Ok verstehe, ich habe die Funktion nun probiert graphisch darzustellen. Ich bin der Meinung das sollte so ungefähr stimmen.
http://img4web.com/view/2QM6X4
Wenn man sich den Aufwand anschaut, dann entspricht das doch ungefähr len/2 wenn ich das richtig verstanden habe.
Zu guter letzt hätte wüsste ich gern, ob man so eine Funktion wie bei mir void Filter(), welche jedes Sonderzeichen rauslöscht, auch als rekursive Funktion darstellen kann bzw. ob das überhaupt geht weil ich ja ansich den string komplett verändern muss?
-
In dem Fall hast du in der Funktion ja nur einen rekursiven Aufruf, da wird aus dem Aufrufbaum eine lineare Liste. Was genau dein Bild darstellen könnte, bin ich mir nicht sicher.
Die Filter-Funktion lässt sich sicher auch rekursiv definieren, aber ob das soviel Sinn macht, lasse ich mal im Raum stehen. Du benötigst dafür zwei Zeiger (quelle und ziel - am Anfang beide auf den Anfang des Strings gezielt) als Parameter und rufst die Funktion dann mit passend verschobenen Zeigern wieder auf.
-
Dave01 schrieb:
void Filter(), welche jedes Sonderzeichen rauslöscht
Die Funktion funktioniert ja so schon nicht
Mal probiert einfach "-----" einzugeben?^^
Die Funktion könnte so aussehen:void Filter(char *s) { while (*s) { if (!isalpha(*s)) memmove(s, s + 1, strlen(s)); else ++s; } }Jetzt schreib du sie rekursiv. Ja, es geht und es ist auch nicht sonderlich schwer
-
@cookie: Bist du sicher, daß diese Konstruktion mit memmove() und strlen() wirklich die beste (schnellste) Lösung ist? Ich hätte die einzelnen Einträge zeichenweise zusammengeschoben:
void Filter(char *s) { char* t = s; for(;*s;++s) { if (isalpha(*s)) *t++ = *s } *t='\0'; }(oder in C++ per remove_if())
-
CStoll schrieb:
die beste (schnellste) Lösung ist?
Ne, hatte nur schnell etwas zweckmäßiges gebastelt, deine Lösung ist besser
-
Tut mir leid, mit isalpha..memmove fang ich leider nicht sehr viel an, da ich noch nicht die Funktionen verwendet hatte.
Bei der Funktion Filter geht es nur drum aus einem Wort "Re123iTTiE!r" die Sonderzeichen zu löschen und bei mir funktioniert das eig. ganz gut. Auf jeden Fall hab ich nun probiert die Funktion rekursiv zu schreiben und zu verstehen. So sieht das bei mir aus. Es funktioniert.. ist es aber richtig rekursiv programmiert? Bzw. was macht es für einen unterschied wenn ich eine Void funktion daraus mach und eben die funktion in der funktion aufrufe?int filter_rek(char *s, char *ptr) { if(*s == '\0') { *ptr='\0'; return 1; } else { if((*s >= 'A' && *s <= 'Z') || (*s >= 'a' && *s <= 'z')) { *ptr=*s; ptr++; } return filterr(s+1,ptr); } }
