😎 作者介绍:我是程序员洲洲,一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号:程序员洲洲。
🎈 本文专栏:本文收录于洲洲的《算法小记》系列专栏,该专栏记录了许多常见的各种各样有趣的实战技巧。欢迎大家关注本专栏~专栏一键跳转
🤓 同时欢迎大家关注其他专栏,我将分享Web前后端开发、人工智能、机器学习、深度学习从0到1系列文章。
🌼 同时洲洲已经建立了程序员技术交流群,如果您感兴趣,可以私信我加入我的社群~社群中将不定时分享各类福利
🖥 随时欢迎您跟我沟通,一起交流,一起成长、进步!点此即可获得联系方式~
Ackermann函数详解
Ackermann函数要求如下:
我们需要知道的是这个函数的时间复杂度增长的非常非常快,A(2,3)和A(5,0)应该差了几百个量级。
咱们也不多废话,直接上多种代码解释吧。上对应代码把。
解法1: 常规递归(只适合输入量很小的情况)
这个就是无限递归了,如果输入量是 2 3,这种很容易就出答案,因为很容易算。
但是这个代码只适合不限制时间的情况下进行操作。大家可以尝试用这个代码用A(5,0)来处理,会发现出不了结果,直接程序卡死了。
#include<iostream>
#include<cmath>
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;
}
解法2:堆栈解法
创建一个数组,当成一个堆栈。也是一种常见解法。
但是这种如果做A(5,0)也是出不了结果,会超出时间。
#include<iostream>
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;
}
解法3:优化递归(记忆数组)
直接开数组进行算过的存起来,然后进行优化,相当于剪枝。
但是需要注意二维数组开的时候,一维开小一些,二维开10的6次方就够用。
我最开始开2000x2000的数组,一直出错,因为二维马上就不够了。
大家可以观察这个数组,把记忆数组一维开小一些,就能解决了。
#include <iostream>
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;
}
解法4:数学归纳法(数学公式)
其实我们可以看到,这个用数学归纳法,可以进行数学归纳。
归纳的话,我们只归纳到3的层次,大家感兴趣可以自己往后推。
#include<iostream>
#include<cmath>//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;
}
这种就是数学归纳法,但是只限制于输入的m在3以内。
总结
Hello,各位看官老爷们好,洲洲已经建立了CSDN技术交流群,如果你很感兴趣,可以私信我加入我的社群。
📝社群中不定时会有很多活动,例如每周都会包邮免费送一些技术书籍及精美礼品、学习资料分享、大厂面经分享、技术讨论、行业大佬创业杂谈等等。
📝社群方向很多,相关领域有Web全栈(前后端)、人工智能、机器学习、自媒体变现、前沿科技文章分享、论文精读等等。
📝不管你是多新手的小白,都欢迎你加入社群中讨论、聊天、分享,加速助力你成为下一个技术大佬!也随时欢迎您跟我沟通,一起交流,一起成长。变现、进步、技术、资料、项目、你想要的这里都会有
📝网络的风口只会越来越大,风浪越大,鱼越贵!欢迎您加入社群~一个人可以或许可以走的很快,但一群人将走的更远!
📝关注我的公众号(与CSDN同ID:程序员洲洲)可以获得一份Java 10万字面试宝典及相关资料!~
📝想都是问题,做都是答案!行动起来吧!欢迎评论区or后台与我沟通交流,也欢迎您点击下方的链接直接加入到我的交流社群!~ 跳转链接社区~文章来源:https://www.toymoban.com/news/detail-721046.html
文章来源地址https://www.toymoban.com/news/detail-721046.html
到了这里,关于「算法小记」-1:Ackermann函数/阿克曼函数的一点思考解法【递归/非递归/堆栈方法】(C++ )的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!