请问如何理解阿克曼函数 刚接触递归 对阿克曼函数不是很了解 求高人给出一个数学展开式 ack(2,2)的就行

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

阿克曼函数是非原始递归函数的例子
它需要两个自然数作为输入值，输出一个自然数。它的输出值增长速度非常高，仅是(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次……

这些问题最好就是在纸上画着来理解 一步一步来就清楚了

阿克曼Ackerman函数A（m，n）的vb程序设计

阿克曼Ackerman函数A（m，n）是所谓的双递归函数（函数以及它的一个变量由函数自身定义），亦是一个不能消除递归的函数。阿克曼Ackerman函数A（m，n）的自变量均取自然数为值，具体如下：

A（m，n）=n+1 当m=0

A（m，n）= A（ m-1，1） 当m>0，n=0

A（m，n）= A（ m-1，A（m，n-1）） 当m>0，n>0

一、Vb窗体设计如下：

三个文本框，其中文本框1用于输入m的值，文本框2用于输入n的值，文本框3用于输出结果A（m，n）的值，还有一个用于计算求结果的命令按钮。

二、阿克曼Ackerman函数A（m，n）vb程序如下：（调试程序时不能用太大的数字）

Private Sub Command1_Click()

m = Val(Text1.Text)

n = Val(Text2.Text)

Text3.Text = a(m, n)

End Sub

Function a(ByVal m As Integer, ByVal n As Integer) As Long

If m = 0 Then a = n + 1

If m > 0 And n = 0 Then a = a(m - 1, 1)

If m > 0 And n > 0 Then a = a(m - 1, a(m, n - 1))

End Function

三、用阿克曼Ackerman函数计算A（3，8）、A（2，10）、A（3，3）的值如下：

1、A（3，8）=2045

2、A（2，10）=23

3、A（3，3）=61

========================================
您的问题==我的课题 奉献知识==辉煌生命
黑龙江省 张志晨
========================================

下面是我在电子表格里用VBA做的过程展示：
代码设计如下：
Dim b(1000) As Long
Dim k As Integer
Dim x(1000), y(1000)

Sub Command1_Click()
k = 0
m = 2
n = 3
Cells(1, 1) = a(m, n) '在A1里显示最终函数值

For i = 1 To k
Cells(i, 3) = x(i) '在C列显示M的变化
Cells(i, 4) = y(i) '在D列显示N的变化
Cells(i, 5) = b(i) '在E列显示A的变化，也就是函数值的变化过程
Next
End Sub

Function a(ByVal m As Integer, ByVal n As Integer) As Long
k = k + 1
If m = 0 Then a = n + 1
If m > 0 And n = 0 Then a = a(m - 1, 1)
If m > 0 And n > 0 Then a = a(m - 1, a(m, n - 1))
x(k) = m
y(k) = n
b(k) = a
End Function

演示结果：
M N A
. . 0
. . 0
. . 0
. . 0
. . 0
1 0 2
1 0 2
2 0 3
. . 0
. . 0
. . 0
1 0 2
1 0 2
1 1 3
1 2 4
2 1 5
. . 0
. . 0
. . 0
. . 0
. . 0
1 0 2
1 0 2
1 1 3
1 2 4
1 3 5
1 4 6
2 2 7
. . 0
. . 0
. . 0
. . 0
. . 0
. . 0
. . 0
. . 0
1 0 2
1 1 3
1 2 4
1 3 5
1 4 6
1 5 7
1 6 8
2 3 9
...........
a(2,3)＝9
..........
上面的数据中的小点“.”是我为了对齐数列而用的占位符，与实际效果无关。

A（m，n）=n+1 当m=0
A（m，n）= A（ m-1，1） 当m>0，n=0
A（m，n）= A（ m-1，A（m，n-1）） 当m>0，n>0

A(2,2)
=A(1，A(2，1))
=A(1，A(1, A(2, 0)))
=A(1, A(1, A(1, 1)))
=......
-------------------------------------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 n
0 1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12 13
2 3 5 7 9 11 13
3 5 13
4
5
6
m

计算公式为：
A(m,n)=2(m级运算)(n+3)-3
如A(2,3)=2×6-3=9
A(3,4)=2^7-3=125
A(4,3)=2↑↑6-3=2^2^65536-3
因此说明A(4,3)连计算机都算不出来。的确，2^65536=2.0035×10^19728，然后2的二亿亿亿亿……亿多次方(此处有2466个亿字)，计算机肯定不能算它的准确数值。阿克曼函数增长率和高德纳箭号同一等级，但是比康威链和葛立恒数慢。
因此A(2,2)=2×5-3=7

---

禹会区15948481031： 利用递归法求阿克曼函数 - ？
松宰盐酸： 这里给出C语言的阿克曼递归函数:首先,阿克曼函数标准定义:#include #include int Ackmann(int n,int m) { if(m==0)return n+1; else if(m>0 && n==0)return Ackmann(m-1,1); else return Ackmann(m-1,Ackmann(m,n-1)); }int main() { int m,n; printf(＂输入m和n:＂); scanf(＂%d,%d＂,&m,&n); printf(＂结果是:%d＂,Ackmann(n,m)); system(＂pause＂); return 0; }

禹会区15948481031： 阿克曼函数的定义 - ？
松宰盐酸： Ackermann函数定义如下: 若m=0,返回n+1. 若m>0且n=0,返回Ackermann(m-1,1). 若m>0且n>0,返回Ackermann(m-1,Ackermann(m,n-1)).

禹会区15948481031： 阿克曼函数是干什么用的?？
松宰盐酸： 一个递归而非原始递归的函数,参见递归函数和原始递归函数.这一点可直观地说明该函数可计算.

禹会区15948481031： 定义阿克曼递归函数: - ？
松宰盐酸： #include <stdio.h> double ACK(int m,int n) { if(n>=0&&m==0) return n+1; if(n==0&&m>=1) return ACK(m-1,1); else return ACK(m-1,ACK(m,n-1)); } main() { char M[100]; char C[100]; int K=3,i; printf(＂ACK(5,3)=%lf\t\n＂,ACK(3,10)); }//你要求的数太大了,会导致堆栈溢出的,默认情况下只能算到ACK(4,10)

禹会区15948481031： Ackermanns - function是什么意思 - ？
松宰盐酸： Ackermann function[词典][计] 阿克曼函数;[例句]Estimation for the constrain of the actual parameter of Ackermann function in recursive invocationACKERMANN函数递归计算中实参的约束范围估计

禹会区15948481031： 递归函数的计算 - ？
松宰盐酸： 数论函数的一种,其定义域与值域都是自然数集,只是由于构作函数方法的不同而有别于其他的函数.处处有定义的函数叫做全函数,未必处处有定义的函数叫做部分函数.最简单又最基本的函数有三个:零函数O(x)=0(其值恒为0);射影函数;...

禹会区15948481031： 请问高手们:递归就是函数直接调用自己而已吗,还有更多的含义吗,例如函数参数的变化规律.谢谢!! - ？
松宰盐酸： 递归,我的理解就是'按这种方法再做一次 或 先做一次' 也就是做法相同,但形参(如果有)可能不同 一个经典的递归函数就是计算 X!的函数,以下以C语言描述: long func(int x){ if (x<=1) return 1; //数学归定0!=1 else return x* func(x-1); ...

禹会区15948481031： 关于阿克曼函数的非递归算法 满意加300 C语言高手求解 在线等 - ？
松宰盐酸： 楼主如果要加300分,可能要开2贴了,因为1贴最多只能200分,追加最多只能50分.你给的那个解法,写的本来就有问题.不信,你自己试试这个程序:#include<stdio.h>//非递归解法 int akm_nonrecursive(int m, int n) { int m1[50], n1[50], cp; ...

禹会区15948481031： 什么是递归的概念? - ？
松宰盐酸： 递归是一种重要的编程技术.该方法用于让一个函数从其内部调用其自身.一个示例就是计算阶乘.0 的阶乘被特别地定义为 1. 更大数的阶乘是通过计算 1 * 2 * ...来求得的,每次增加 1,直至达到要计算其阶乘的那个数.下面的段落是用文字...