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++編程迭代和遞歸

回答

相關問題