Char einfüger per Rekursion

chris35039

Hi ich hoffe, dass mir hier jemand helfen kann!

Ich muss an jeder stelle nacheinander ein X in ein String einfügen, dies aber per Rekursion.

Folgende Lösung habe ich, leider ohne Rekursion.

Hat einer von euch ne ahnung wie ich dies mit Rekursion lösen könnte?

Code:

#include <iostream>
#include <string>
#include <list>

using namespace std;

list <string> allInsertions(char x, string s)
{
list <string> v;
// Induktionsschritt s' = s + x
int len = s.length() + 1;

for(int i=0; i < len; i++) {
// setze in den String das x an die Position: String-Iterator + i
s.insert(s.begin()+i, x);
// füge den neuen String an das Ende in die Liste v hinzu
v.insert(v.end(), s);
// lösche die alte Position von x im String
s.erase(s.begin()+i);
}

return v;
}

int main()
{
string s = "REKURSION!";
list <string> l = allInsertions('X', s);

while(l.size() > 0)
{
cout << l.front() << endl;
l.pop_front();
}

getchar();
return 0;
}

Danke schon mal im vorraus.

Sorry hatte was falsch erklärt!

Ausgabe soll so aussehen:

XREKURSION
RXEKURSION
REXKURSION
REKXURSION
REKUXRSION
REKURXSION
REKURSXION
REKURSIXON
REKURSIOXN
REKURSIONX

string setzeX( string str )
{
  wenn länge von str == 1 return "X";

  return (str - letztes zeichen) + "X";
}

Bye, TGGC (Das Jahr des Helden)

Werner Salomon

chris35039 schrieb:

Hat einer von euch ne ahnung wie ich dies mit Rekursion lösen könnte?

zum Beispiel so:

#include <iostream>
#include <string>

void printMitX( const std::string& txt, std::string::size_type pos )
{
    using namespace std;
    cout << txt.substr( 0, pos ) << 'X' << txt.substr( pos, txt.size() ) << endl;
    if( pos < txt.size() )
        printMitX( txt, ++pos );
}

int main()
{
    printMitX( "Rekursion", 0 );
    return 0;
}

.. es ist nicht unbedingt die Anwendung für Rekursion

Gruß
Werner

chris35039

Danke für die Antworten, das DIng ist leider nur, das ich nur in der allInseration Funktion was schreiben darf.
Unser Prof hat uns kurz vor den ganzen Klausuren ne Hausarbeit reingeknallt bei der man die ohren anlegt.
So wie ich es gepostet hatte läuft es ja, aber leider werde ich keine Punkte darauf bekommen weil es eben nicht Rekursiv ist.

Werner Salomon

chris35039 schrieb:

Danke für die Antworten, das DIng ist leider nur, das ich nur in der allInseration Funktion was schreiben darf.
Unser Prof hat uns kurz vor den ganzen Klausuren ne Hausarbeit reingeknallt bei der man die ohren anlegt.
So wie ich es gepostet hatte läuft es ja, aber leider werde ich keine Punkte darauf bekommen weil es eben nicht Rekursiv ist.

Hallo Chris,

jetzt habe ich Deine Aufgabe erst richtig verstanden. Die Signatur von

std::list< std::string > allInsertions( char x, std::string s );

ist also eine Vorgabe. 'Hausarbeit' lösen sollten wir ja nicht; aber weil heute Freitag ist und ich frei habe

#include <algorithm>    // swap, copy
#include <iostream>
#include <iterator>     // ostream_iterator
#include <list>
#include <string>

std::list< std::string > allInsertions( char x, std::string s )
{
    using namespace std;
    string::size_type i = s.find( x );
    if( i == string::npos )
    {
        s = x + s;      // nicht gefunden, dann vorn einfügen
        i = 0;          // Pos von 'x' ist vorn
    }
    list< string > l( 1, s );
    if( ++i < s.size()  )
    {
        swap( s[i-1], s[i] );
        l.splice( l.end(), allInsertions( x, s ) );
    }
    return l;
}

int main()
{
    using namespace std;
    list< string > l = allInsertions( 'X', "Rekursion" );
    copy( l.begin(), l.end(), ostream_iterator< string >( cout << "Die Liste:\n", "\n" ) );
    cout << endl;
    return 0;
}

Grüße an Deinen Prof
Werner