阿克曼(Ackmann)函数

题目描述

阿克曼(Ackmann)函数 $A(m,n)$ 的 $m,n$ 为非负整数（ $m \le 3$ 、 $n \le 10$ ），定义分三条分支： $A(0,n)=n+1$ ； $m>0,n=0$ 时 $A(m,n)=A(m-1,1)$ ； $m,n>0$ 时 $A(m,n)=A(m-1,A(m,n-1))$ 。

输入一行两个整数 $m$ 和 $n$ ，输出 $A(m,n)$ ；样例输入 2 3，样例输出 9。

思路

数据规模很小，按题目给出的三条分支逐条翻译成递归函数即可。最大的一组 $A(3,10)=8189$ 需要约 8190 层调用栈，C++ 默认栈深足以承受，所以不必加记忆化，也不必改成递推填表。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 22:14
# update_at: 2026-09-29 22:14

import sys


def ackermann(m: int, n: int) -> int:
    """阿克曼函数 A(m, n)：按层自底向上填表，消掉朴素递归的重复子问题。"""
    # rows[k][j] = A(k, j)；第 k 层只读第 k-1 层，所以可以逐层往后填
    rows: list[list[int]] = [[] for _ in range(m + 1)]

    def value(k: int, j: int) -> int:
        """取 A(k, j)：按需把第 k 层延长到下标 j，递归深度只有 k 层。"""
        if k == 0:
            return j + 1                                   # 唯一出口：A(0, j) = j + 1
        row = rows[k]
        while len(row) <= j:                               # 惰性填表：只算被问到的下标
            # A(k, 0) = A(k-1, 1)；A(k, t) = A(k-1, A(k, t-1))，左邻值就是上一层要取的列号
            column = row[-1] if row else 1
            row.append(value(k - 1, column))
        return row[j]

    return value(m, n)


def solve() -> None:
    m, n = map(int, sys.stdin.buffer.read().split())
    print(ackermann(m, n))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:58
 * update_at: 2026-10-05 03:58
 */

// 阿克曼(Ackmann)函数：把三分支定义逐条翻译成递归函数。
// 数据规模 m<=3、n<=10，答案最大 A(3,10)=8189，递归深度最多约 8190 层，
// C++ 的调用栈完全够用，直接照抄定义即可，不需要记忆化或改成递推。

#include <cstdio>

typedef long long ll;

ll m, n; // 输入的一对非负整数

// ackermann(m, n)：按定义返回 A(m, n)
ll ackermann(ll m, ll n) {
    if (m == 0) {
        return n + 1; // 分支一：A(0, n) = n + 1
    }
    if (n == 0) {
        return ackermann(m - 1, 1); // 分支二：A(m, 0) = A(m-1, 1)
    }
    // 分支三：A(m, n) = A(m-1, A(m, n-1))，内层先算出 A(m, n-1) 再作为下标传下去
    return ackermann(m - 1, ackermann(m, n - 1));
}

int main() {
    scanf("%lld %lld", &m, &n);
    printf("%lld\n", ackermann(m, n));
    return 0;
}

阿克曼(Ackmann)函数

目录

题目描述

思路

参考代码