1.

#include <iostream>
#include <stack>
using namespace std;

int f(int x) {
    stack<int> s;  // 用栈来模拟递归
    int result = 1;  // 初始值
    while (x!=0||!s.empty()) {
        if (x != 0) {
            s.push(x);  // 将当前 x 入栈
            x /= 2;     // 计算 x / 2 并继续
        } else {
            int top = s.top();  // 获取栈顶元素
            s.pop();  // 弹出栈顶元素
            result *= top;  // 乘上栈顶元素
        }
    }
    return result;   
}

int main() {
    int x;
    cin >> x;
    cout << f(x) << endl;
    return 0;
}

2.

#include <iostream>
#include <stack>
using namespace std;

int f(int n) {
    // 处理基本情况
    if (n == 1) return 3;
    if (n == 2) return 11;

    stack<int> s;  // 用栈来模拟递归过程
    s.push(3);  // f(1) = 3
    s.push(11); // f(2) = 11

    int result = 0;
    for (int i = 3; i <= n; ++i) {
        // 计算 f(n) = 4 * f(n-1) - f(n-2)
        int f_n_minus_1 = s.top();  // 获取栈顶元素 f(n-1)
        s.pop();  // 弹出栈顶元素

        int f_n_minus_2 = s.top();  // 获取栈第二个元素 f(n-2)
        s.pop();  // 弹出栈第二个元素

        // 计算 f(n)
        result = 4 * f_n_minus_1 - f_n_minus_2;

        // 将新的 f(n) 压入栈
        s.push(f_n_minus_1);  // 将 f(n-1) 重新压入栈
        s.push(result);        // 将计算出的 f(n) 压入栈
    }

    return result;
}

int main() {
    int n;
    cin >> n;
    cout << "f(" << n << ") = " << f(n) << endl;
    return 0;
}

3

#include <iostream>
#include <stack>
using namespace std;

double calculate_val(int n, double x) {
    if (n == 0) return 1.0;  // f(0) = 1
    if (n == 1) return 2 * x; // f(1) = 2*x

    stack<int> s;  // 用栈存储递归层次
    double f0 = 1.0, f1 = 2.0 * x;  // 初始值 f(0) = 1, f(1) = 2*x

    // 将递归层次 n 到 2 入栈
    for (int i = n; i >= 2; i--) {
        s.push(i);  // 递归层次入栈
    }

    // 边出栈边计算函数值
    while (!s.empty()) {
        int current_no = s.top();  // 获取栈顶的递归层次
        s.pop();  // 弹出栈顶元素

        // 计算当前递归层次的值
        double current_val = 2 * x * f1 - 2 * (current_no - 1) * f0;
        f0 = f1;  // 更新 f0 和 f1
        f1 = current_val;  // 更新 f1 为当前计算出的值
    }

    // 最终的结果存放在 f1
    return f1;
}

int main() {
    int n;
    double x;
    cout << "Enter n and x: ";
    cin >> n >> x;
    cout << "Pn(x) = " << calculate_val(n, x) << endl;
    return 0;
}