1

最近面接で聞かれました。最近卒業したばかりで、プログラミングを約 2 年 (すべて学業) しか行っていないので、途方に暮れていました。漠然とした考えはありましたが、間違いなく失敗しました。これは私が書いたものです：

string Reverse(string word, string reversed)
{
    if(word.length() == 0)
    {
        return reversed;
    }
    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        Reverse(temp, reversed);
    }

    return reversed;
}

家に帰ってテストしていると、リターンは入力の最初の文字だけです。私は再帰の概念に漠然と精通していますが、明らかにこれに失敗しています。ヘルプ/ポインター/提案​​は大歓迎です。ありがとうございました。

編集: Dennis Meng の投稿に続いて、次の変更を加えました。

string Reverse(string word, string reversed)
{
    if(word.length() == 0)
    {
        return reversed;
    }
    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        return Reverse(temp, reversed);
    }
}

これで、適切な戻り値が得られました。どうもありがとうございました。

4

6 に答える 6

2

何が問題なのかは次のとおりです。

    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        Reverse(temp, reversed); // <-- Here's your problem
    }

    return reversed;
}

呼び出しが正しい答えを返さなければならないことはわかっているのに、なぜそれを返さないのでしょうか? 言い換えれば、あなたがした場合はどうなりますか

    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        return Reverse(temp, reversed);
    }
}

代わりは？コードが最初の文字のみを返す理由の詳細には、参照渡し/値渡しが含まれます。値渡しのため、再帰呼び出しで行われたことを実際に使用したことはありません。(呼び出しを行い、返されたものを破棄しました。)

于 2012-08-09T16:56:34.210 に答える
1 
string Reverse(string word, string reversed) 
{
    ...
    Reverse(temp, reversed);

まず、wordconst 参照と参照渡しを行う必要がありreversedます。再帰関数を呼び出すと、これらの各文字列のコピーが作成されるため、最も外側の関数はそれらの動作を認識できません。別のオプションは、再帰関数の結果を に割り当てることでしたreversed。そのため、参照によって変数を渡します。

2番目: 文字列を逆にする簡単な方法があります:

 string Reverse(string word) //caller should _not_ see my changes, so I pass by value
 {
     for(int i=0; i<word.size()/2; ++i) { //for each letter in the first half
         int otherindex = word.size()-1-i; //find the letter on the other half
         char t = word[i];  //and swap them
         word[i] = word[otherindex];
         word[otherindex] = t;
     }
     return word; //return the result
 }
于 2012-08-09T16:51:31.383 に答える
1

ここで再帰を使用している理由がわかりません。それは本当に不要です：

string Reverse(string word)
{
    string reversed = "";

    if(word.length() == 0)
    {
        return reversed;
    } 

    for (int i = word.length()-1; i>=0; i--){
        reversed = reversed+word[i];
    }

    return reversed;
}
于 2012-08-09T16:49:59.653 に答える
0

文字列は文字の配列に他なりません。通常、この場合、文字の配列を使用してアルゴリズムを説明する必要があります。ここにそれを行うためのより良い方法があります。

void reverse(char* str, int len)
{
    for (int i = 0, j = len -1 ; i < len / 2; ++i, --j) {
         // Swap the values as i and j.
         int temp = str[i];
         str[i] = str[j];
         str[j] = temp;
    }
}

Java で同じ質問がされた場合は、文字列を char[] 配列に変換していることを確認し、それを逆にしてから文字列を形成する必要があります。これにより、作成されるオブジェクトの数を最小限に抑えることができます。少なくとも、StringBuilder を使用する必要があります。

于 2012-08-09T16:55:07.100 に答える
0

これが別の解決策です（すでに投稿されたものと同様）。しかし、標準のものを使用しているため、このソリューションは適切ではないことがわかりました。

std::string reverse(std::string const& character_queue_) {
    using namespace std;
    string result;
    if(!character_queue_.empty()) {
        vector<char> character_stack;
        std::copy(character_queue_.begin(),character_queue_.end(),std::back_inserter(character_stack));
        while(!character_stack.empty()) {
           result.push_back(character_stack.back());
           character_stack.pop_back();
        }
    }
    return result;
}
于 2012-08-09T18:48:26.543 に答える
-2

再帰を処理するためのより良い方法を提案するためだけに：

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;
}
于 2013-02-28T22:02:51.193 に答える