使用非递归算法实现ackerman函数

Ackermann函数是一个著名的递归函数，其定义如下：

A(m, n) =
- 如果 m = 0, 那么 A(m, n) = n + 1
- 如果 m > 0 且 n = 0, 那么 A(m, n) = A(m - 1, 1)
- 否则 A(m, n) = A(m - 1, A(m, n - 1))

要将其转换为非递归算法，我们可以使用记忆化搜索或动态规划的方法。这里我将演示一种基于记忆化的实现方法，即存储中间结果以避免重复计算。

#include <vector>

// 储存中间值的辅助结构体
struct Node {
    int m;
    int n;
    int value;
};

std::vector<Node> memo; // 存储中间结果

int ackermann(int m, int n) {
    // 初始化边界条件
    if (m == 0) return n + 1;
    if (n == 0 && m != 0) return ackermann(m - 1, 1);

    // 搜索缓存中的结果
    for (const auto& node : memo) {
        if (node.m == m && node.n == n) {
            return node.value;
        }
    }

    // 计算 Ackermann 函数并添加到缓存中
    int result = ackermann(m - 1, ackermann(m, n - 1));
    memo.push_back({m, n, result});
    
    return result;
}

int main() {
    int m = 3, n = 5; // 测试的Ackermann数值
    std::cout << "A(" << m << ", " << n << ") = " << ackermann(m, n) << std::endl;

    return 0;
}

在这个实现中，我们首先检查是否已经计算过给定的(m, n)组合，如果已存在，则直接返回结果。否则，根据递归规则计算新的值，并保存到`memo`中供后续使用。