ackerman

时间:2024-03-22 20:05:05编辑:优化君

利威尔为什么叫里维 进击巨人第二季里为什么叫兵长里维

其实名字是音译过来的,Levi·Ackerman(利威尔·阿克曼)里面的Levi才是原本的发音,然后Levi音译成中文后就是利威尔或里维,都是可以的,至于为什么叫兵长,是应为他是城墙内调查兵团的士兵长、调查兵团特别作战班利威尔班班长,通称“利威尔兵长”或“利威尔士兵长”。当然,也有人调侃因为他的身高是兵长的身高,哈哈哈。


【Pascal递归函数】计算ackerman函数值;

两个问题:1、Integer太小了,数据早就爆了;2、栈的调用过头了,“exitcode = 201”的意思就是栈溢出。事实上,阿克曼函数的值是极大的。Ackermann(0,n)=n+1Ackermann(1,n)=n+2Ackermann(2,n)=2*n+3Ackermann(3,n)=2^(n+3)-3Ackermann(4,n)=2^2^2^……^2-3,乘幂中共有n+3个2。当m≥4,Ackermann函数的增长快得惊人。Ackermann(4,0)=13,Ackermann(4,1)=65533,Ackermann(4,2)=2^65536-3有19729位,而Ackermann(4,3)则即使是位数也不易估计。Ackermann(5,0)=65533,Ackermann(5,1)=Ackermann(4,65533)……针对于小数据,你的程序没问题。


为什么 阿克曼函数不是原始递归函数

阿克曼函数是非原始递归函数的例子它需要两个自然数作为输入值,输出一个自然数。它的输出值增长速度非常高,仅是(4,3)的输出已大得不能准确计算。1920年代后期,数学家大卫·希尔伯特的学生Gabriel Sudan和威廉·阿克曼,当时正研究计算的基础。Sudan发明了一个递归却非原始递归的Sudan函数。1928年,阿克曼又独立想出了另一个递归却非原始递归的函数。他最初的念头是一个三个变量的函数A(m,n,p),使用康威链式箭号表示法是m→n→p。阿克曼证明了它是递归函数。希尔伯特在On the Infinite猜想这个函数不是原始递归。阿克曼在On Hilbert’s Construction of the Real Numbers证明了这点。后来Rozsa Peter和Raphael Robinson定义了一个类似的函数,但只用两个变量。定义: { n+1; m=0,n>0 A(m,n) = { A(m-1,1); n=0,m>0 { A(m-1,A(m,n-1)) n>0,m>0 求 ack(3,3) 的返回值:int ack(int m,int n) { if(m == 0) return n+1; else if(n == 0) return ack(m-1,1); else return ack(m-1,ack(m,n-1)); }0,ack(0,1)=2; ack(1,0)=ack(0,1)=2; ack(1,1)=ack(0,ack(1,0))=ack(1,0)+1=3; //容易口算出来的几个值1,ack(1,n)=ack(0,ack(1,n-1))+1=ack(1,n-1)+1; //递推式 由递推式得:ack(1,n)=n+1; ps:递推式形如 A(n) = A(n-1) + 1,求A(n)。 用的是高中数学知识,方法是“累加法”(加起来然后消掉),是否想起来了?2,ack(2,n)=ack(1,ack(2,n-1))=ack(2,n-1)+2; //递推式 由递推式得:ack(2,n)=2n+3; ps:A(n) = A(n-1) + 2,方法同 13,ack(3,n)=ack(2,ack(3,n-1))=2*ack(3,n-1)+3; //递推式 即:ack(3,n)+3=2(ack(3,n-1)+3) 得: ack(3,n)+3=(ack(3,1)+3)*2n-1; 又ack(3,1)=2ack(3,0)+3 ack(3,0)=a(2,1)=5 所以ack(3,1)=13; 所以 ack(3,n)=2n+3 - 3; ps:递推式形如 A(n) = 2*A(n-1) + 3,求A(n)。 方法是“拆分常数”,拆分常数3后 A(n) + 3 = 2*( A(n-1) + 3 ), 令B(n) = A(n) + 3,即有 B(n) = 2*B(n-1),等比数列啊,B(n)=B(1)*2n-1, 求出B(1),得到B(n),即可得到A(n)。所以:ack(3,3)=61;计算机运行该程序时一共调用了ack()函数2432次……


上一篇:ugly meter

下一篇:highsierra