Iteration in Rekursion



  • Hallo,

    Wir haben nächste Wochen einen Test in dem wir eine Iteration in eine Rekursion umschreiben sollen.

    Deshalb frage ich ob jemand von euch gute Beispiele dafür zum Üben hätte, wie zum Beispiel kgv und ggt.
    Wäre nett, wenn ihr mir einen Code von einer Iteration schicken könnt.

    Fibonacci, Binärzahlenumrechner und Fakultät hab ich schon gemacht.

    Vielen dank im voraus!


  • Mod

    Da muss man nichts üben, jede Iteration ist trivial in eine Rekursion umschreibbar:

    zustand
    while(bedingung):
      tu was mit zustand
    

    ->

    def funktion(zustand):
      if not bedingung:
        return
      tu was mit zustand
      funktion(zustand)
    

    Diese paar Zeilen sind alles, was du wissen musst. Sofern du die Aufgabe richtig verstanden hast. Vermutlich hast du etwas missverstanden, denn das wäre viel zu einfach sonst.



  • @Padrophil die habe ich aus meinem alten übungsbuch. viel spaß!

    Familie Müller ist zu einer Geburtstagfeier eingeladen. Leider können sich die Familienmitglieder (Anton, Berta, Claus und Doris nicht einigen, wer hingeht und wer nicht. In einer gemeinsamen Diskussion kann man sich jedoch auf die folgenden Grundsätze verständigen.
    
    1. Mindesten ein Familienmitglied geht zur Feier.
    2. Anton geht auf keinen Fall zusammen mit Doris.
    3. Wenn Berta geht, dann geht Claus mit.
    4. Wenn Anton und Claus gehen, dann bleibt Berta zu Hause.
    5. Wenn Anton zu Hause bleibt, dann geht entweder Doris oder Claus.
    
    Helfen Sie Familie Müller, indem Sie ein Programm erstellen, das alle Gruppierungen ermittelt, in denen Familie Müller zur Feier gehen kann.
    


  • This post is deleted!


  • /*
    
    Familie Müller ist zu einer Geburtstagfeier eingeladen. Leider können sich die Familienmitglieder (Anton, Berta, Claus und Doris nicht einigen, wer hingeht und wer nicht. In einer gemeinsamen Diskussion kann man sich jedoch auf die folgenden Grundsätze verständigen.
    
    1. Mindesten ein Familienmitglied geht zur Feier.
    2. Anton geht auf keinen Fall zusammen mit Doris.
    3. Wenn Berta geht, dann geht Claus mit.
    4. Wenn Anton und Claus gehen, dann bleibt Berta zu Hause.
    5. Wenn Anton zu Hause bleibt, dann geht entweder Doris oder Claus.
    
    Helfen Sie Familie Müller, indem Sie ein Programm erstellen, das alle Gruppierungen ermittelt, in denen Familie Müller zur Feier gehen kann.
    
    */
    
    
    familiemueller(int Anton, int Berta, int Claus, int Doris)
    {
    
      if ( Anton==1&&Claus==1) if (Berta==1) return;
    	
     if ( Anton==1 || Berta ==1 || Claus==1 || Doris==1 )
      if ( !(Anton==1 && Doris ==1) )
       if( (Berta==1&&Claus==1) || (Berta==0 && Claus==0 ) || (Berta==0 && Claus==1) )  
    	    if ( ( Anton==0 && (Doris==1|| Claus==1 ) ) || Anton==1)
         {
          printf("\nMoeglich:\n");
           printf("Anton geht");
           if ( Anton==1 ); else printf(" nicht");
             printf(".\n");
    
    
           printf("Berta geht");
           if ( Berta==1 ); else printf(" nicht");
             printf(".\n");
    
           printf("Claus geht");
           if ( Claus==1 ); else printf(" nicht");
             printf(".\n");
    
           printf("Doris geht");
           if ( Doris==1 ); else printf(" nicht");
             printf(".\n");
    
         }
    
    }
    
    int main(void)
    {
     int a=0;
    
     while ( a < 16 )
     {
      familiemueller( (a>>3)&1, (a>>2)&1, (a>>1)&1, a&1);
      a++; 
     }
    }
    

    Habe da noch ein anderes mit einem Lexer, einem Parser, einem Haufen Zufallsversuchen und "größer als", "kleiner als", "ist gleich"-Vergleichen. Was heißt da Rekursion? Das Programm müßte einfach alle Wertekombinationen durchiterieren und auf Stimmigkeit prüfen, bis kein Widerspruch mehr auftritt. Das kann man iterativ, rekursiv oder einfach sehr sicher dadurch machen, daß man den Zufallsgenerator lange genug ackern läßt?!



  • @Klagenderlamer sagte in Iteration in Rekursion:

    Das Programm müßte einfach alle Wertekombinationen durchiterieren und auf Stimmigkeit prüfen, bis kein Widerspruch mehr auftritt. Das kann man iterativ, rekursiv oder einfach sehr sicher dadurch machen, daß man den Zufallsgenerator lange genug ackern läßt?!

    Ja, genau! Und hier ist nach der rekursiven Variante gefragt.



  • @Belli Rekursiv macht man es sinnvollerweise so, daß man das Durchzählen rekursiv ausführt. Kann eine erste Bedingung durch die Wertebelegung grundsätzlich nicht erfüllt werden, kehrt die rekursive Funktion einfach zu ihrer Aufrufenden zurück und von dort wird dann weiter durchgezählt oder es werden andere Permutationsketten durch Selbstaufrufe durchgegeben.
    So spart man da Rechenleistung.
    Man muß wohl unterscheiden zwischen Permutationen und simplem Durchzählen. Die einzelnen Bedingungen, vorgegeben durch logische Terme, ließen sich zu Optimierungszwecken wohl häufig zusammenraffen. Aber wie das genau geht, weiß ich nicht, weil ja wie gesagt Durchzählen und Permutationen gemeinsam auftreten können und die einzelnen, dann zusammengeführten Ausdrücke auch ziemlich kompliziert sein können.
    Ich hatte bei meinem Programm Personen und logische Relationen separat als Struct-Arrays zusammengelistet und den Personen Werte zugewiesen, die die Vergleichsoperatoren (älter, jünger, gleich als) dann allesamt erfüllen mußten. Bei Prolog gibt es das sogenannte Backtracking. Nur mal erwähnt. Und dann noch der Nachtrag für die Erklärung eines nicht-rekursiven Permutationsalgorithmus:
    Wähle von hinten den ersten Wert aus, der größer ist als sein Vorgänger und vertausche die zwei.
    Hinten am Anhang ist ja dann immer das größere weiter vorne. Also drehe die Reihenfolge vom Anhang um, um auf
    die nächsthöhere Sortierung zu kommen?
    Klar hoffentlich. So zählt man nach der Größe geordnet Permutationen hoch.



  • OT

    @Klagenderlamer sagte in Iteration in Rekursion:

       if ( Anton==1 ); else printf(" nicht");
    

    Das ist aber nicht Dein ernst!?



  • @Klagenderlamer sagte in Iteration in Rekursion:

    if((anton == 1 || berta == 1 || claus == 1 || doris == 1) //punkt 1
    && ((anton == 1 && doris == 0) || (anton == 0 && doris == 1)) //punkt 2
    && (berta == 0 || claus == 1) //punkt 3
    && ((anton == 1 && claus == 1) || berta == 1) //punkt 4
    && (anton == 1 || ((doris == 1 && claus == 0) || (doris == 0 && claus == 1)))) //punkt 5
    {
         //print lösung
    }
    

    etwas kürzer und übersichtlicher, oder?



  • @Wade1234
    Bei solchen Dingen baue ich mir fast immer ein Lambda oder ne Funktion im anonymous namespace.

    void f()
    {
       auto check_condition = []( bool anton, bool berta, bool claus, bool doris )
       {
          if( !(anton && berta && claus && dories) ) return false; // Punkt 1
          if( anton && doris ) return false; // Punkt 2
          ...
          return true;
       };
       ...
       if( check_condition( anton, berta, claus, doris ) )
       {
          ...
       }
    }
    


  • @Klagenderlamer sagte in Iteration in Rekursion:

    /*
    
    Familie Müller ist zu einer Geburtstagfeier eingeladen. Leider können sich die Familienmitglieder (Anton, Berta, Claus und Doris nicht einigen, wer hingeht und wer nicht. In einer gemeinsamen Diskussion kann man sich jedoch auf die folgenden Grundsätze verständigen.
    
    1. Mindesten ein Familienmitglied geht zur Feier.
    2. Anton geht auf keinen Fall zusammen mit Doris.
    3. Wenn Berta geht, dann geht Claus mit.
    4. Wenn Anton und Claus gehen, dann bleibt Berta zu Hause.
    5. Wenn Anton zu Hause bleibt, dann geht entweder Doris oder Claus.
    
    Helfen Sie Familie Müller, indem Sie ein Programm erstellen, das alle Gruppierungen ermittelt, in denen Familie Müller zur Feier gehen kann.
    
    */
    
    
    familiemueller(int Anton, int Berta, int Claus, int Doris)
    {
    
      if ( Anton==1&&Claus==1) if (Berta==1) return;
    	
     if ( Anton==1 || Berta ==1 || Claus==1 || Doris==1 )
      if ( !(Anton==1 && Doris ==1) )
       if( (Berta==1&&Claus==1) || (Berta==0 && Claus==0 ) || (Berta==0 && Claus==1) )  
    	    if ( ( Anton==0 && (Doris==1|| Claus==1 ) ) || Anton==1)
         {
          printf("\nMoeglich:\n");
           printf("Anton geht");
           if ( Anton==1 ); else printf(" nicht");
             printf(".\n");
    
    
           printf("Berta geht");
           if ( Berta==1 ); else printf(" nicht");
             printf(".\n");
    
           printf("Claus geht");
           if ( Claus==1 ); else printf(" nicht");
             printf(".\n");
    
           printf("Doris geht");
           if ( Doris==1 ); else printf(" nicht");
             printf(".\n");
    
         }
    
    }
    
    int main(void)
    {
     int a=0;
    
     while ( a < 16 )
     {
      familiemueller( (a>>3)&1, (a>>2)&1, (a>>1)&1, a&1);
      a++; 
     }
    }
    

    Habe da noch ein anderes mit einem Lexer, einem Parser, einem Haufen Zufallsversuchen und "größer als", "kleiner als", "ist gleich"-Vergleichen. Was heißt da Rekursion? Das Programm müßte einfach alle Wertekombinationen durchiterieren und auf Stimmigkeit prüfen, bis kein Widerspruch mehr auftritt. Das kann man iterativ, rekursiv oder einfach sehr sicher dadurch machen, daß man den Zufallsgenerator lange genug ackern läßt?!

    Ich nehme mal an, das das Pseudocode sein soll, denn weder kompiliert das, noch ist das C++, noch funktioniert das wie gewünscht. Abgesehen davon, dass ich es anders gelöst hätte, ist z.B. sowas hier:

     familiemueller( (a>>3)&1, (a>>2)&1, (a>>1)&1, a&1);
    

    furchtbar unintuitiv. Ziel von Quellcode sollte unter anderem auch sein, dass man auf einen Blick erkennt was er tut.


Log in to reply