1

我正在寻找一些关于家庭作业的快速提示。我们遇到了一些问题，必须编写两个快速程序来说明如何用迭代和递归中的一个来解决这些问题。我敢肯定这比我想象的要容易，但是我很容易对这两者感到困惑。我不希望任何人为我完全解决问题，我不会学到任何东西！但是，如果你能看看我到目前为止所拥有的，让我知道我是否朝着正确的方向前进。此外，代码不需要编译，我们的教授希望我们对迭代与递归的区别有一个大致的了解。

问题：检查一个字符串是否为回文。

我的解决方案-我认为这是迭代解决方案：

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

这是一般的想法：

迭代：初始化两个指针，一个指针指向字符串的开始和结束。

  1. 比较指出的字符，如果不同 -> 不是回文。
  2. 增大起始指针并减小结束指针。
  3. 重复直到开始指针 >= 结束指针。

递归（在这种情况下比迭代更困难）：

结束条件：长度为零或一的字符串是回文。

如果第一个和最后一个字符相同并且没有第一个和最后一个字符的字符串是回文，则字符串是回文。

您可以通过传递指向字符串中第一个和最后一个字符的指针来更有效地实现此递归算法，而不是在递归之间复制字符串。

希望这可以帮助 ：-）

于 2012-11-02T00:30:24.723 回答
0

我认为编写代码是解释这两种方法的最佳方式。这段代码可以理解吗？

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 回答