1

宿題の簡単なヒントを探しています。いくつかの問題が与えられ、反復と再帰をそれぞれ 1 つずつ使用して問題を解決する方法について、2 つの簡単なプログラムを作成する必要があります。これは思ったより簡単だと思いますが、この 2 つについて簡単に混乱してしまいます。誰かに問題を完全に解決してもらいたくありません。何も学びません。しかし、私がこれまでに得たものを見て、私が正しい方向に向かっているかどうかを教えていただければ. また、コードをコンパイルする必要はありません。私たちの教授は、反復と再帰の違いについての一般的な考え方を知りたいと考えています。

問題: 文字列が回文かどうかを調べます。

私の解決策-それは反復的な解決策だと思います：

bool iterative_palindrome (const string& str) {
string line, result;
stack <char> stack_input;

//user enters string, program takes it
cout << "Enter string: " << endl;
while (getline (cin, line) && (line != "")) {

    //push string into stack
    for (size_t i = 0; i < line.size(); i++) {
        stack_input.push(line[i]);

        //create reverse of original string
        while (!stack_input.empty()) {
            result += stack_input.top();
            stack_input.pop();
            return result;
        }
        //check for palindrome, empty string
        if (line == result || line = "0" || line.empty()) {
            return true;
            cout << line << " is a palindrome!" << endl;
        } else {
            return false;
            cout << line << " is NOT a palindrome." << endl;
            cout << "Enter new string: " << endl;
        }
     }
  }
}

私は皆に思い出させます、私はこのことにはかなり慣れていません。私はすでにいくつかのことを読みましたが、これについて頭を悩ますのにまだ苦労しています.

4

2 に答える 2

2

一般的な考え方は次のとおりです。

反復: 文字列の先頭と末尾を指す 2 つのポインターを初期化します。

  1. 指摘された文字を比較し、異なる場合 -> 回文ではありません。
  2. 開始ポインタを増やし、終了ポインタを減らします。
  3. 開始ポインタ >= 終了ポインタになるまで繰り返します。

再帰的 (この場合、反復的より難しい):

終了条件: 長さが 0 または 1 の文字列は回文です。

最初と最後の文字が同じで、最初と最後の文字がない文字列が回文である場合、その文字列は回文です。

この再帰アルゴリズムは、再帰間で文字列をコピーする代わりに、文字列の最初と最後の文字へのポインターを渡すことで、より効率的に実装できます。

お役に立てれば ：-）

于 2012-11-02T00:30:24.723 に答える
0

2 つのアプローチを説明するには、コードを記述することが最善の方法だと思います。このコードは理解できますか?

bool iterative_palindrome(const string& str) {
    int size = str.size();

    for (int i=0; i<str.size()/2; i++) {
        if (str[i] != str[size-i-1])
            return false;
    }

    return true;
}

これを のように呼び出しますrecursive_palindrome(str, 0)。

bool recursive_palindrome(const string& str, int index) {
    int size = str.size();

    if (index >= size/2)
        return true;

    if (str[index] == str[size-index-1])
        recursive_palindrome(str, index+1);
    else
        return false;
}
于 2012-11-02T00:26:50.880 に答える