wake-up-neo.com

Schreiben Sie eine rekursive Funktion, die die Eingabezeichenfolge umkehrt

Ich habe das Buch C++ For Everyone gelesen und in einer der Übungen eine Funktion string reverse(string str) geschrieben, bei der der Rückgabewert die Umkehrung von str ist.

Kann jemand einen grundlegenden Code schreiben und ihn mir erklären? Ich habe seit gestern auf diese Frage gestarrt und kann es nicht herausfinden. Das weiteste, was ich bekommen habe, ist, dass die Funktion den ersten Buchstaben von str zurückgibt (was ich immer noch nicht weiß, wie es passiert ist)

So weit bin ich gekommen (eine Stunde nach dem Posten dieser Frage):

string reverse(string str)
{
    string Word = "";

    if (str.length() <= 1)
    {
        return str;
    }
    else
    {
        string str_copy = str;
        int n = str_copy.length() - 1;
        string last_letter = str_copy.substr(n, 1);

        str_copy = str_copy.substr(0, n);
        Word += reverse(str_copy);
        return str_copy;
    }
    return Word;
}

Wenn ich "Wolf" eingebe, wird Wol zurückgegeben. Jemand hilft mir hier raus Wenn ich return Word anstelle von return str_copy bekomme ich eine w Wenn ich return last_letter bekomme ich eine l

9
Alex

Ich habe zwei Minuten Zeit, um stattdessen den rekursiven Algorithmus selbst zu erklären. Nehmen Sie das Beispiel "input", das "tupni" erzeugen soll. Sie können die Zeichenfolge rekursiv umkehren

  • Wenn die Zeichenfolge leer oder ein einzelnes Zeichen ist, geben Sie sie unverändert zurück.
  • Andernfalls,
    1. Entfernen Sie das erste Zeichen.
    2. Kehren Sie die verbleibende Zeichenfolge um.
    3. Fügen Sie das erste Zeichen der umgekehrten Zeichenfolge hinzu.
    4. Gibt den neuen String zurück.
19
David Harkness

Probier diese

string reverse(string &s)
{
    if( s.length() == 0 )  // end condtion to stop recursion
        return "";

    string last(1,s[s.length()-1]);  // create string with last character
    string reversed = reverse(s.substr(0,s.length()-1));
    return last+reversed; // Make he last character first
}

Eine rekursive Funktion muss die folgenden Eigenschaften haben

  • Es muss sich wieder anrufen
  • Es muss eine Bedingung haben, wenn die Rekursion endet. Andernfalls haben Sie eine Funktion, die einen Stapelüberlauf verursacht.

Diese rekursive Funktion erstellt im Grunde genommen eine Zeichenfolge des letzten Zeichens und ruft sich dann erneut auf, wobei der Rest der Zeichenfolge das letzte Zeichen ausschließt. Die reale Umschaltung erfolgt in der letzten Zeile, in der last + reverse zurückgegeben wird. Wenn es umgekehrt wäre, würde nichts passieren. Es ist sehr ineffizient, aber es funktioniert, um das Konzept zu zeigen.

Ihr Alois Kraus

7
Alois Kraus

Nur um eine bessere Methode zur Behandlung von Rekursionen vorzuschlagen:

Stringumkehr mit Rekursion in C++:

#include <iostream>
#include <string>
using namespace std;

string reverseStringRecursively(string str){
    if (str.length() == 1) {
        return str;
    }else{
        return reverseStringRecursively(str.substr(1,str.length())) + str.at(0);
    }
}

int main()
{
    string str;
    cout<<"Enter the string to reverse : ";
    cin>>str;

    cout<<"The reversed string is : "<<reverseStringRecursively(str);
    return 0;
}
6
totjammykd

Ich werde keinen vollständigen Algorithmus für Sie schreiben, aber hier ist ein Hinweis:

Wie wäre es, wenn Sie die beiden äußersten Zeichen vertauschen und dann dasselbe auf die Zeichen in der Mitte anwenden?

Oh, und wenn dieses Buch wirklich string reverse(string str) als geeignete Funktionssignatur dafür vorgeschlagen hat, werfen Sie es weg und kaufen Sie stattdessen ein gutes Buch .

2
sbi

Hier ist meine Version einer rekursiven Funktion, die die Eingabezeichenfolge umkehrt:

void reverse(char *s, size_t len)
{
    if ( len <= 1 || !s )
    {
        return;
    }
    std::swap(s[0], s[len-1]);// swap first and last simbols
    s++; // move pointer to the following char
    reverse(s, len-2); // shorten len of string
}
2
Ann Orlova

Kürzeste und einfachste

class Solution {
public:
    string reverseString(string s) {
        string str;
        if(s != "\0"){
            str = reverseString(s.substr(1, s.length()));
            str += s.substr(0,1);
        }
        return str;    
    }   
};
1
Prem K Chettri

1-zeilige rekursive Lösung:

string RecursiveReverse(string str, string prev = "") {
    return (str.length() == 0 ? prev : RecursiveReverse(str.substr(0, str.length()-1), prev += str[str.length()-1]));
}

Du nennst es so:

cout << RecursiveReverse("String to Reverse");
0
PieThon

Ich weiß, dass ich keine Lösung geben sollte, aber da niemand diese einfache Lösung erwähnte, dachte ich, ich sollte sie teilen. Ich denke, der Code ist buchstäblich der Algorithmus, daher ist kein Pseudocode erforderlich.

void c_plusplus_recursive_swap_reverse(std::string::iterator start, 
    std::string::iterator end) 
{
    if(start >= end) {
        return;
    }

    std::iter_swap(start, end);
    c_plusplus_recursive_swap_reverse(++start, --end);
}

Um es zu nennen, benutze:

c_plusplus_recursive_swap_reverse(temp.begin(), temp.end());
0
ArmenB

sie können Ihr eigenes Reverse ähnlich wie std :: reverse implementieren.

template <typename BidirIt>
void reverse(BidirIt first, BidirIt last)
{
    if((first == last) || (first == --last))
        return;

    std::iter_swap(first, last);
    reverse(++first, last);
}
0
MORTAL

Die Zeichenfolge kann an Ort und Stelle umgekehrt werden. Wenn wir von der kleinstmöglichen Zeichenfolge ausgehen, d. H. Von einer Zeichenfolge, müssen wir nichts tun. Hier stoppen wir oder kehren von unserem rekursiven Aufruf zurück und es wird unser Basisfall.

Als nächstes müssen wir uns eine generische Methode überlegen, um die kleinste Zeichenfolge auszutauschen, d. H. Zwei oder mehr Zeichen. Die einfachste Logik besteht darin, das aktuelle Zeichen str[current_index] Mit dem Zeichen auf der gegenüberliegenden Seite str[str_length-1 - current_index] Zu tauschen.

Rufen Sie am Ende die Umkehrfunktion für den nächsten Index erneut auf.

#include <iostream>
using namespace std;

void reverse_string(std::string& str, int index, int length) {
  // Base case: if its a single element, no need to swap
  // stop swapping as soon as we reach the mid, hence index*2
  // otherwise we will reverse the already reversed string
  if( (length - index*2) <= 1 ) { 
    return;
  }

  // Reverse logic and recursion:

  // swap current and opposite index
  std::swap(str[index], str[length-1 - index]); 

  // do the same for next character (index+1)
  reverse_string(str, index+1, length);
}

int main() {
  std::string s = "World";
  reverse_string(s, 0, s.length());
  std::cout << s << endl;
}
0
SMUsamaShah

Ich habe so etwas gemacht, es hat die Umkehrung an Ort und Stelle gemacht. Ich habe zwei Variablen verwendet, die die Zeichenfolge vom äußersten Ende bis zur Mitte der Zeichenfolge durchlaufen. Wenn sie sich überlappen oder gleich sind, wird die Umkehrung beendet.

Nehmen Sie ein Beispiel: Geben Sie string str = "abcd" ein und rufen Sie die Funktion als auf

ReverseString(str,0,str.length()-1);

und Inkrementieren/Dekrementieren der Variablenzeiger rekursiv. Zuerst zeigen die Zeiger auf 'a' und 'd' und tauschen sie aus, dann zeigen sie auf 'b' und 'c' und tauschen sie aus. Eventuell i >= j, der verlangt, dass der Basisfall wahr ist und daher die Rekursion endet. Das Hauptproblem bei dieser Frage ist die Übergabe einer Eingabezeichenfolge als Referenz.

string ReverseString(string& str,int i,int j){
        if(str.length() < 1 || str == "" || i >= j){
            return "";
        }

        else{
            char temp = str[i];
            str[i] = str[j];
            str[j] = temp;
            ReverseString(str,i+1,j-1);
        }
        return str;
    }
0
Marco167

Alle vorhandenen Lösungen enthielten viel zu viel Code, der eigentlich nichts ausmachte.

#include <iostream>
#include <string>

std::string
r(std::string s)
{
    if (s.empty())
        return s;
    return r(s.substr(1)) + s[0];
}

int
main()
{
    std::cout << r("testing") << std::endl;
}

P.S. Ich bin auf diese Frage gestoßen und habe versucht, einen C++ - Weg für std::string zu finden, wie s+1 für einen char * in C aussieht. ohne den ganzen Weg von s.substr(1, s.length()-1) zu gehen, der zu hässlich aussieht. Es stellt sich heraus, dass es std::string::npos gibt, das heißt, bis zum Ende der Zeichenfolge, und es ist bereits der Standardwert für das zweite Argument. Daher ist s.substr(1) ausreichend (und es sieht aucheffizienter aus und ist mit dem vergleichbar) einfacher s + 1 in C).


Beachten Sie jedoch, dass die Rekursion im Allgemeinen nicht skaliert, wenn die Eingabe größer wird, es sei denn, der Compiler kann eine so genannte Schwanzrekursionsoptimierung durchführen. (In imperativen Sprachen wird selten auf Rekursion zurückgegriffen.)

Damit die Schwanzrekursionsoptimierung aktiviert wird, ist es jedoch im Allgemeinen erforderlich, dass (0) die Rekursion nur innerhalb der Anweisung return erfolgt und (1) mit dem Ergebnis der Rekursion keine weiteren Operationen ausgeführt werden Rückruf in der übergeordneten Funktion.

Beispiel: Im obigen Fall wird der + s[0] nach Abschluss des untergeordneten Aufrufs logisch vom übergeordneten Aufruf ausgeführt (und dies wäre wahrscheinlich auch dann der Fall, wenn Sie die hässlichere s[s.length()-1] +-Route einschlagen), sodass die meisten Compiler möglicherweise genauso gut daran gehindert werden, einen auszuführen Tail-Recursion-Optimierung, wodurch die Funktion bei großen Eingaben sehr ineffizient ist (wenn sie nicht aufgrund von Heap-Erschöpfung völlig kaputt ist).

(Für das, was es wert ist, habe ich versucht, eine schwanzrekursionsfreundlichere Lösung zu schreiben (um sicherzustellen, dass das Rückgabeergebnis durch ein Argument an die Funktion selbst erweitert wird), aber das Disassemblieren der resultierenden Binärdatei scheint darauf hinzudeuten, dass es aufwändiger ist als dass in den imperativen Sprachen wie C++, siehe gcc: gibt es keine Schwanzrekursion, wenn ich std :: string in C++ zurückgebe? .)

0
cnst