编辑代码

#include <iostream>

using namespace std;

// 1. 台阶问题
int climbStairsRecursive(int n) {
    if (n <= 1) {
        return 1;
    }
    return climbStairsRecursive(n-1) + climbStairsRecursive(n-2);
}

int climbStairsIterative(int n) {
    if (n <= 1) {
        return 1;
    }
    int a = 1, b = 1;
    for (int i = 2; i <= n; ++i) {
        int temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}

// 2. 阶乘问题
int factorialRecursive(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return n * factorialRecursive(n-1);
}

int factorialIterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

// 3. 斐波那契问题
int fibonacciRecursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);
}

int fibonacciIterative(int n) {
    if (n <= 1) {
        return n;
    }
    int a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        int temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}

// 4. 回文字符串
bool isPalindromeRecursive(const string& s) {
    string cleaned;
    for (char c : s) {
        if (isalnum(c)) {
            cleaned.push_back(tolower(c));
        }
    }
    if (cleaned.length() <= 1) {
        return true;
    }
    return cleaned[0] == cleaned.back() && isPalindromeRecursive(cleaned.substr(1, cleaned.length()-2));
}

bool isPalindromeIterative(const string& s) {
    string cleaned;
    for (char c : s) {
        if (isalnum(c)) {
            cleaned.push_back(tolower(c));
        }
    }
    int length = cleaned.length();
    for (int i = 0; i < length / 2; ++i) {
        if (cleaned[i] != cleaned[length - i - 1]) {
            return false;
        }
    }
    return true;
}

// 测试用例
int main() {
    // 台阶问题
    cout << "Climb Stairs Recursive: " << climbStairsRecursive(4) << endl;
    cout << "Climb Stairs Iterative: " << climbStairsIterative(4) << endl;
    cout << "Climb Stairs Recursive: " << climbStairsRecursive(10) << endl;
    cout << "Climb Stairs Iterative: " << climbStairsIterative(10) << endl;

    // 阶乘问题
    cout << "Factorial Recursive: " << factorialRecursive(5) << endl;
    cout << "Factorial Iterative: " << factorialIterative(5) << endl;
    cout << "Factorial Recursive: " << factorialRecursive(3) << endl;
    cout << "Factorial Iterative: " << factorialIterative(3) << endl;

    // 斐波那契问题
    cout << "Fibonacci Recursive: " << fibonacciRecursive(6) << endl;
    cout << "Fibonacci Iterative: " << fibonacciIterative(6) << endl;
    cout << "Fibonacci Recursive: " << fibonacciRecursive(11) << endl;
    cout << "Fibonacci Iterative: " << fibonacciIterative(11) << endl;

    // 回文字符串
    cout << "Is Palindrome Recursive: " << isPalindromeRecursive("A man, a plan, a canal, Panama") << endl;
    cout << "Is Palindrome Iterative: " << isPalindromeIterative("A man, a plan, a canal, Panama") << endl;
    cout << "Is Palindrome Recursive: " << isPalindromeRecursive("abba") << endl;
    cout << "Is Palindrome Iterative: " << isPalindromeIterative("abba") << endl;

    return 0;
}