题解B2144【阿克曼(Ackmann)函数】

· · 题解

从对函数的定义可以看出，这个函数的计算需要使用递归。直接按照定义来写即可。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a(int m,int n) // akm(m,n)
{
    if(m==0) return n+1;
    if(m>0&&n==0) return a(m-1,1);
    if(m>0&&n>0) return a(m-1,a(m,n-1));
}
int main() 
{
   scanf("%d%d",&m,&n);
   cout<<a(m,n);
   return 0;
}

通过一些测试数据可以看出，阿克曼的函数增长的非常快，因此它的反函数，即反阿克曼函数增长的非常慢。使用路径压缩的并查集单次操作均摊时间复杂度为 O(\log n)，加上按秩合并后降低即为反阿克曼函数，可以近似成一个常数。

对于 \forall n\le2^{2^{10^{19729}}}，都有 a(n)<5 ——《进阶指南》

\texttt{The End.}