「算法小记」-1：Ackermann函数/阿克曼函数的一点思考解法【递归/非递归/堆栈方法】（C++ ）

😎 作者介绍：我是程序员洲洲，一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号：程序员洲洲。
🎈 本文专栏：本文收录于洲洲的《算法小记》系列专栏，该专栏记录了许多常见的各种各样有趣的实战技巧。欢迎大家关注本专栏~专栏一键跳转
🤓 同时欢迎大家关注其他专栏，我将分享Web前后端开发、人工智能、机器学习、深度学习从0到1系列文章。
🌼 同时洲洲已经建立了程序员技术交流群，如果您感兴趣，可以私信我加入我的社群~社群中将不定时分享各类福利
🖥 随时欢迎您跟我沟通，一起交流，一起成长、进步！点此即可获得联系方式~

Ackermann函数详解

Ackermann函数要求如下：

我们需要知道的是这个函数的时间复杂度增长的非常非常快，A（2，3）和A（5，0）应该差了几百个量级。

咱们也不多废话，直接上多种代码解释吧。上对应代码把。

解法1： 常规递归（只适合输入量很小的情况）

这个就是无限递归了，如果输入量是 2 3，这种很容易就出答案，因为很容易算。

但是这个代码只适合不限制时间的情况下进行操作。大家可以尝试用这个代码用A（5,0）来处理，会发现出不了结果，直接程序卡死了。

#include
#include
using namespace std;
int A(int i,int j)
{
    if(i>0&&j>0){
    	return A(i-1,A(i,j-1));
	}
    else if(i==0){
    	return j+ 1;
	}
	else{
		return  A(i-1,1);
	}

}

int main()
{
	int a,b;
	cin >> a>>b;
	int ans = A(a,b);
	cout << ans %1000000009<<endl;
}

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

解法2：堆栈解法

创建一个数组，当成一个堆栈。也是一种常见解法。

但是这种如果做A（5，0）也是出不了结果，会超出时间。

#include
using namespace std;
int A(int m,int n)
{
	int a[100000];
	int i=0;
	while(1){
		if(0==m){
			if(0==i){
				return ++n;
			}
			n++;
			m=a[i--];
		}
		if(0==n){
			m--;
			n++;
		}

		if( 0!=m && 0!=n){
			a[++i]=m-1;
			n--;
		}
	}
}
int main()
{
	int m,n;
	cin >> m >> n;
	int b=A(m,n);
	cout<<b <<endl;;
	return 0;
}
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

解法3：优化递归（记忆数组）

直接开数组进行算过的存起来，然后进行优化，相当于剪枝。

但是需要注意二维数组开的时候，一维开小一些，二维开10的6次方就够用。

我最开始开2000x2000的数组，一直出错，因为二维马上就不够了。

大家可以观察这个数组，把记忆数组一维开小一些，就能解决了。

#include 
using namespace std;
const int mod = 1000000009;
const int MAXN = 10; 
const int MAXN2 = 1000000; 
int memo[MAXN][MAXN2];
int A(int i, int j) {
    if (i ==0) return (j+ 1) % mod;
    if (j ==0) return A(i-1, 1);
    if (memo[i][j] != 0) {
    	return memo[i][j];
	}
    int result = A(i-1, A(i, j-1));
    memo[i][j] = result;
    return result;
}
int main() {
    int a, b;
    cin >> a >> b;
    int ans = A(a, b);
    cout << ans << endl;
    return 0;
}

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

解法4：数学归纳法（数学公式）

其实我们可以看到，这个用数学归纳法，可以进行数学归纳。

归纳的话，我们只归纳到3的层次，大家感兴趣可以自己往后推。

#include
#include//pow函数
using namespace std;
int main(){
	int m,n;
	cin>>m>>n;
	if(m==0) cout<<n+1<<endl;
	if(m==1) cout<<n+2<<endl;
	if(m==2) cout<<2*n+3<<endl;
	if(m==3) cout<<pow(2,n+3)-3<<endl;	
}

1
2
3
4
5
6
7
8
9
10
11
12
13

这种就是数学归纳法，但是只限制于输入的m在3以内。

总结

Hello，各位看官老爷们好，洲洲已经建立了CSDN技术交流群，如果你很感兴趣，可以私信我加入我的社群。

📝社群中不定时会有很多活动，例如每周都会包邮免费送一些技术书籍及精美礼品、学习资料分享、大厂面经分享、技术讨论、行业大佬创业杂谈等等。

📝社群方向很多，相关领域有Web全栈（前后端）、人工智能、机器学习、自媒体变现、前沿科技文章分享、论文精读等等。

📝不管你是多新手的小白，都欢迎你加入社群中讨论、聊天、分享，加速助力你成为下一个技术大佬！也随时欢迎您跟我沟通，一起交流，一起成长。变现、进步、技术、资料、项目、你想要的这里都会有

📝网络的风口只会越来越大，风浪越大，鱼越贵！欢迎您加入社群~一个人可以或许可以走的很快，但一群人将走的更远！

📝关注我的公众号（与CSDN同ID：程序员洲洲）可以获得一份Java 10万字面试宝典及相关资料！~

📝想都是问题，做都是答案！行动起来吧！欢迎评论区or后台与我沟通交流，也欢迎您点击下方的链接直接加入到我的交流社群！~ 跳转链接社区~