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

这篇具有很好参考价值的文章主要介绍了「算法小记」-1:Ackermann函数/阿克曼函数的一点思考解法【递归/非递归/堆栈方法】(C++ )。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

「算法小记」-1:Ackermann函数/阿克曼函数的一点思考解法【递归/非递归/堆栈方法】(C++ ),项目踩坑,算法小记,算法,c++,开发语言

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

Ackermann函数详解

Ackermann函数要求如下:

我们需要知道的是这个函数的时间复杂度增长的非常非常快,A(2,3)和A(5,0)应该差了几百个量级。
「算法小记」-1:Ackermann函数/阿克曼函数的一点思考解法【递归/非递归/堆栈方法】(C++ ),项目踩坑,算法小记,算法,c++,开发语言
咱们也不多废话,直接上多种代码解释吧。上对应代码把。

解法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:数学归纳法(数学公式)

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

「算法小记」-1:Ackermann函数/阿克曼函数的一点思考解法【递归/非递归/堆栈方法】(C++ ),项目踩坑,算法小记,算法,c++,开发语言
归纳的话,我们只归纳到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后台与我沟通交流,也欢迎您点击下方的链接直接加入到我的交流社群!~ 跳转链接社区~

「算法小记」-1:Ackermann函数/阿克曼函数的一点思考解法【递归/非递归/堆栈方法】(C++ ),项目踩坑,算法小记,算法,c++,开发语言文章来源地址https://www.toymoban.com/news/detail-721046.html

到了这里,关于「算法小记」-1:Ackermann函数/阿克曼函数的一点思考解法【递归/非递归/堆栈方法】(C++ )的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Unity3D赛车游戏】【四】在Unity中添加阿克曼转向,下压力,质心会让汽车更稳定

    !在这里插入图片描述 👨‍💻个人主页 :@元宇宙-秩沅 👨‍💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍💻 本文由 秩沅 原创 👨‍💻 收录于专栏 :Unity游戏demo – 😶‍🌫️版本: Unity2021 😶‍🌫️适合人群:Unity初学者 😶‍🌫️学习目标:3D赛车游戏的基础制

    2024年02月11日
    浏览(42)
  • 窗函数的介绍以及画出常见窗函数(汉宁窗,矩形窗,汉明窗,布莱克曼窗)的时域图和频谱图

    常见的四种窗函数的表达式为: 四种常见窗函数的参数表 对于实际信号序列,该如何选取窗函数呢?一般来说,选择第一旁瓣衰减大,旁瓣峰值衰减快的窗函数有利于缓解截断过程中产生的频谱泄漏问题。但具有这两个特性的窗函数,其主瓣宽度较大,相应会带来一些副作用

    2024年02月02日
    浏览(33)
  • MySQL小记——存储过程、触发器、函数、视图

    目录 存储过程 procedure 语法 参数 调用存储过程 call 删除存储过程 drop 带有IF逻辑的存储过程 if then elseif else 带有循环的存储过程 while do 变量 触发器 Trigger 语法 old和new 视图 View 函数 自定义函数 内置函数 存储过程是数据库中的一个对象,存储在服务端,用来封装多条SQL语句

    2024年02月08日
    浏览(51)
  • TEB算法2-teb参数说明及调试小记

    teb_local_planner的参数较多,分为以下几类 阿克曼底盘配置参数 : 底盘模型设置 其中oscillation_v_eps和oscillation_omega_eps是用来判断速度是否震荡的阈值, 这里将速度归一化到[0,1]区间,所以配置中这两个值的区间也在(0,1) 震荡判断:

    2024年02月16日
    浏览(36)
  • 【算法小记】深度学习——循环神经网络相关原理与RNN、LSTM算法的使用

    文中程序以Tensorflow-2.6.0为例 部分概念包含笔者个人理解,如有遗漏或错误,欢迎评论或私信指正。 卷积神经网络在图像领域取得了良好的效果,卷积核凭借优秀的特征提取能力通过深层的卷积操作可是实现对矩形张量的复杂计算处理。但是生活中除了图像这样天然以矩阵形

    2024年01月25日
    浏览(52)
  • [log_softmax]——深度学习中的一种激活函数

    [log_softmax]——深度学习中的一种激活函数 随着人工智能技术的发展,深度学习已经成为了众多领域的热点研究方向。在深度学习中,激活函数是非常重要的组成部分之一,而[log_softmax]就是其中的一种。本文将介绍什么是[log_softmax],以及它在深度学习中的应用。 首先,我们

    2024年02月13日
    浏览(47)
  • 【算法小记】——机器学习中的概率论和线性代数,附线性回归matlab例程

    内容包含笔者个人理解,如果错误欢迎评论私信告诉我 线性回归matlab部分参考了up主DR_CAN博士的课程 在回归拟合数据时,根据拟合对象,可以把分类问题视为一种简答的逻辑回归。在逻辑回归中算法不去拟合一段数据而是判断输入的数据是哪一个种类。有很多算法既可以实现

    2024年01月24日
    浏览(42)
  • 【Dijkstra】最短路算法的一种

    首先,本文默认读者基本熟悉Dijkstra基本原理 DIjkstra是单源最短路的一种算法。使用数组d[i]来储存结点i到源点s的最短路径长度,每次更新d[i]数组后,d[i]中最小的一定是一条最短路径长度。也就是说每次更新后都能找到一条最短路径,以下给出证明: 假设d[]数组中当前最小

    2024年02月03日
    浏览(52)
  • 3、利用matlab求f(x)的一阶导函数(完整代码)

    在 MATLAB 中,可以使用符号计算工具箱 Symbolic Math Toolbox 来求 $f(x)$ 的一阶导函数。具体步骤如下: 打开 MATLAB,打开一个新的脚本文件,输入以下代码: 运行代码,MATLAB 会输出 f\\\'(x) 的符号表达式以及 f1_handle 的函数句柄。 以下是对上述代码的解释: 第一行定义符号变量 x 和

    2024年02月03日
    浏览(36)
  • 一文带你玩转C库中的一系列字符串函数

    作者主页: paper jie的博客_CSDN博客-C语言,算法详解领域博主 本文作者: 大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于 《系统解析C语言》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将算法基础知识一网打尽,

    2024年02月13日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包