rekursive funktion, alle möglichkeiten?



  • Schreiben Sie ein vollständiges Programm, das zunächst eine positive ganze Zahl n von
    der Tastatur einliest. Dann alle Wörter der Länge n, die nur aus den beiden Buchstaben
    ’a’ und ’b’ bestehen, übersichtlich ausgibt.
    Beispiel: Wörter der Länge n=3: aaa,baa,aba,bba,aab,bab,abb,bbb

    Also das ist meine aufgabe zu der mir der Ansatz fehlt 😕
    so, zunächst hab ich meine main in der ich n einlese und die funktion aufrufe, kein problem.

    die funktion soll, je nachdem was für ein n eingegeben wird, alle möglichkeiten ausgeben. Zunächst füll ich den string mit a's dann fällt mir nur ein noch ein weiteres string zu erstellen, auch mit a's gefüllt mit dem ich dann vergleiche und das erste dann ändre, nach jeder ändereung wird dann ausgegeben, doch wie krieg ich das hin das mein prog genau alle möglichkeiten schreibt? also aaa dann baa dann die ersten beiden ändert und so weiter, ich komm auf keinen logischen algorithmus 😞


  • Mod

    Muss das denn rekursiv sein? Das ist doch bloß binär von 0 bis 2^n gezählt und statt der Ziffern '0' und '1' eben 'a' und 'b'. Natürlich kann man jede Schleife auch als Rekursion schreiben:

    while(bedingung(foo))
     {
      do_something(bar);
      do_something_else(foo);
     }
    

    ist

    void rekursion(Parameter foo, Parameter bar)
    {
     if (!bedingung(foo))
      return;
       do_something(bar);
       do_something_else(foo);
       rekursion(foo, bar);
    }
    


  • ja, steht in der aufgabe und muss dann auch so abgearbeitet werden ^^



  • wär es möglich einfach erst die möglichkeiten zu berechnen, dann jede zahl (bei n=3 -> 8 möglichkeiten also 1,..,7,8) binär in ein array zu speichern und die nullen und einsen einfach durch 'a' und 'b' ersetzen?


  • Mod

    wintik schrieb:

    wär es möglich einfach erst die möglichkeiten zu berechnen, dann jede zahl (bei n=3 -> 8 möglichkeiten also 1,..,7,8) binär in ein array zu speichern und die nullen und einsen einfach durch 'a' und 'b' ersetzen?

    Möglich ist vieles. Empfehlenswert nicht alles. Empfehlen würde ich dir eines oder alles von:
    1. Forum durchsuchen. Exakt diese Aufgabe kommt hier dauernd
    2. Die Aufgabe als Schleife lösen, dann Schleife zu Rekursion umschreiben, bloß um dem Lehrer zu zeigen, wie dumm seine Aufgabe ist
    3. Der Weg wie die Aufgabe vermutlich gedacht ist:
    - Eine Funktion die bei einer bestimmten Stelle die Zeichen 'a' und 'b' probiert, dann jeweils sich selbst für die nächste Stelle aufruft
    - Wenn die letzte Stelle erreicht ist, Ergebnis ausgeben
    - Funktion im Programm einmal für die erste Stelle aufrufen



  • Man kann auch einfach davon ausgehen, dass jede Stelle entweder aus einem A oder einem B besteht und dies Stellenweise durchgehen, hier mit dem Stellenzähler 'laenge':

    #include <stdio.h>
    #include <string.h>
    
    void zeige_buchstabe( int aktlaenge, int wortlaenge, char * wort ) {
        if( aktlaenge > 0 ) {
    		// Platz für das neue Wort
    		char neueswort[ wortlaenge + 1 ];
    
    		// Ein A und der Rest des alten Wortes
    		sprintf( neueswort, "A%s", wort );
    		zeige_buchstabe( aktlaenge - 1, wortlaenge, neueswort );
    
    		// Oder ein B und der Rest des alten Wortes
    		sprintf( neueswort, "B%s", wort );
    		zeige_buchstabe( aktlaenge - 1, wortlaenge, neueswort );
        } else {
    		// Länge == 0 -> Wort ausgeben!
    		puts( wort );
    	}
    }
    
    int main( int argc, char *argv[] ) {
        int laenge = 0;
    
        printf( "Wortlänge: " );
        scanf( "%d", &laenge );
    
        if( laenge > 0 ) {
    		char wort[ laenge + 1 ];
    		wort[ 0 ] = '\0';							// Leerstring
            zeige_buchstabe( laenge, laenge, wort );
    	}
    }
    

    Diese Lösung ist weder Resourcenschonend noch elegant, benutzt aber eine Rekusrsion, wo keine nötig ist...

    Ciao MM


Log in to reply