C++编程迭代和递归

我正在寻找关于作业分配的一些快速提示。我们遇到了一些问题，并且必须编写两个关于如何通过迭代和递归分别解决问题的快速程序。我相信这比我想象的要容易，但是我对这两者很容易感到困惑。我绝不希望任何人为我完全解决问题，我不会学到任何东西！但如果你能看看我目前为止的情况，并告诉我是否正朝着正确的方向前进。此外，代码不需要编译，我们的教授希望我们对迭代与递归的差异有一个大致的了解。C++编程迭代和递归

问题：检查字符串以查看它是否是回文。

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

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; 
     } 
    } 
    } 
}

我提醒大家的是，我非常新的这个东西。我已经阅读了一些东西，但是我仍然很难把这个东西包裹起来。

来源

2012-11-02 supersix3

line =“0”是一项任务而不是比较。此外，返回后的代码根本不会执行。 – imreal

你被要求使用堆栈吗？你比这更难以做到。 – Duck

不一定非要使用堆栈，但是我们的教授花了很多时间来讨论它们，在看了讲义和幻灯片之后，有点儿来找我。来自其他用户的评论，似乎你是对的！ – supersix3

我认为写代码是解释这两种方法的最好方法。这段代码是否可以理解？

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-02 00:26:50 snibbets

感谢您的快速回复 - 我可以通过此代码了解您要去哪里。我对迭代解决方案中的一部分有点困惑，你有：“size（）/ 2” - 为什么我们除以二？另外，在if语句中，为什么我们要减去[size-i-1]？ – supersix3

我除以2，因为您只需进行大小/ 2比较（字符串的一半正在与另一半进行比较）。索引是size-i-1，因为它从字符串的末尾向后计数。（请记住，字符串的第一个索引是0，而不是1，所以我需要减1）。希望澄清它。 – snibbets

这里的总体思路：

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

比较指出的字符，如果不同 - >不是回文。
增加开始指针并减少结束指针。
重复，直到开始指针> =结束指针。

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

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

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

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

希望这有助于:-)

来源

2012-11-02 00:30:24

C++编程迭代和递归

回答

相关问题