Diese Rekursion...



  • 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);
        }
    }
    


  • Ja, das sieht rekursiv aus (wenn du noch die Namen korrekt hinbekommst :D) und sieht auf den ersten Blick auch korrekt aus. Das ganze als void-Funktion umzusetzen dürfte kein größeres Problem sein.
    Was du mit Schleife meinst, bin ich mir jetzt nicht sicher - du hast die Schleife ja durch den rekursiven Aufruf ersetzt.

    PS: isalpha() ist eine etwas kürzere Form, das selbe zu sagen wie bei deinen Bereichsvergleichen, memmove() verschiebt größere Blöcke im Speicher.

    PPS: Darf man erfahren, ob dieses rekursiv-Gebastel einen tieferen Sinn hat? Normalerweise ist eine iterative Version (Schleife) schneller und kompakter, deshalb geht man eher den Weg, rekursive Funktionen durch iterative zu ersetzen als umgekehrt.



  • Nur mal ein Beispiel aus meinem Umfeld: Es gibt Lehrer, die tierisch auf rekursion abfahren 😃



  • Ok wollte nur wissen ob man das ganze auch als void schreiben könnte.
    Das Rekursionsgebastel ist einfach vom Lehrer so vorgegeben worden. Wir üben das ganze indem wir ein paar Bsp. einfach auf die Rekursionsform umschreiben. Und das steht leider so im Lehrplan drinnen. Iterativ ist mir auf jeden Fall um einiges lieber (vielleicht aber auch nur weil ich es besser kann) 🙂



  • Dave01 schrieb:

    Ok wollte nur wissen ob man das ganze auch als void schreiben könnte.

    Wie schon gesagt: Ja das geht.

    Das Rekursionsgebastel ist einfach vom Lehrer so vorgegeben worden. Wir üben das ganze indem wir ein paar Bsp. einfach auf die Rekursionsform umschreiben. Und das steht leider so im Lehrplan drinnen. Iterativ ist mir auf jeden Fall um einiges lieber (vielleicht aber auch nur weil ich es besser kann) 🙂

    OK, das erklärt einiges.


Anmelden zum Antworten