并非一切递归函数都能用非递归方式定义,为了对递归函数的复杂性有更多的了解,双递归函数——Ackerman函数,当一个函数以及它的一个变量是由函数自身定义时,称这个函数是双递归函数,Ackerman函数A(n,m)有两个独立的整变量m>=0和n>=0,其定义如下:
A(1,0)=2
A(0,m)=1 m>=0
A(n,0)=n+2 n>=2
A(n,m)=A(A(n-1,m),m-1) n,m>=1
A (n,m)的自变量m的每一个值都定义了一个单变量函数,例如,递归式的第三式表示m=0定义了函数"加2"。m=1时,由于A(1,1)=A(A(0,1),0)=A(1,0)=2以及A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2(n>1),因此A(n,1)=2n(n>=1),即A(n,1)是函数"乘2"。
类似地可以推出,A(n,3)=2∧2...2,其中2的层数为n。
A(n,4)的增长速度非常快,以至于没有适当的数学式子来表示这一函数。
单变量的Ackerman函数A(n)定义为:A(n)=A(n,n)。其拟逆函数a(n)在算法复杂性分析中常遇到。它定义为:a(n)=min{k|A(k)>=n}。即a(n)是使n<=A(k)成立的最小的k值。
例如,由A(0)=1,A(1)=2,A(2)=4和A(3)=16推知,a(1)=0,a(2)=1,a(3)=a(4)=2和a(5)=...=a(16)=3。可以看出a(n)的增长速度非常慢。
A(4)=2∧2...2,其中2的层次为65536,这个数非常大,无法用通常德方式来表达它。如果要写出这个数将需要log(A(4))位,即2∧2...2(65535层2的方幂)位。所以,对于通常所见到的正常数n,有a(n)<=4。但在理论上a(n)没有上界,随着n的增加,它以难以想象的慢速度趋向正无穷大。
分享到:
相关推荐
Ackerman函数,也被称为阿克曼函数,是一个非常特殊的数学函数,主要在计算理论和递归函数理论中被研究。这个函数是由美国数学家Maurice Karnaugh在1937年提出的,但以他的老师Gottfried Ackermann的名字命名。它是...
### Ackerman函数的C++实现解析 在计算机科学与数学领域,Ackerman函数是一个递归定义的二元函数,以其快速增长而闻名。本篇文章将深入探讨Ackerman函数的基本概念、特性以及其在C++中的具体实现。 #### Ackerman...
Ackerman函数,通常被称作阿克曼函数,是一个非递归定义的多变量阶乘类函数,由美国数学家Maurice Karnaugh在1962年提出,但以计算机科学家Morse和Ackerman的名字命名。这个函数在计算理论和算法设计中常被用作一个...
Ackerman 函数是一种著名的递归函数,常用于探讨递归理论和计算复杂性。这个函数在计算机科学领域中被广泛讨论,因为它展示了非平凡的计算行为,即使在非常小的输入下也会导致极端的计算深度。本文将深入探讨 ...
Ackerman 函数是一种著名的递归计算函数,常用于探讨计算复杂性和递归理论。它以数学家 Moses J. Ackerman 的名字命名,其定义为一个三元运算符,通常写作 A(m, n),其中 m 和 n 是非负整数。 Ackerman 函数的计算...
Ackerman函数,通常被用来作为一个展示递归深度和复杂性的例子。它是一个多变量的、非线性的递归函数,由数学家Morton Ackerman在20世纪30年代提出。这个函数以其非平凡的递归结构和极端的快速增长而闻名。 首先,...
数据机构的晦涩难懂我有亲身经历,所以提供一些算法来帮助大家!
阿克曼函数是一种著名的计算上界递归函数,它在理论计算机科学中有着重要的地位,尤其是在探讨递归和计算复杂性的领域。这个函数是不可计算的,也就是说,它不能通过有限步骤的算法来解决,但是可以通过其他方法如...
阿克曼函数是一种非常特殊的数学函数,常用于理论计算和计算机科学中,特别是在讨论递归算法和计算复杂性时。这个函数是由荷兰数学家格奥尔格·阿克曼在20世纪早期提出的,它展示了超越函数的概念,即无法用初等函数...
Ackermann 函数是一种著名的递归函数,用于展示非平凡的递归行为。它是由荷兰数学家马里乌斯·阿克曼在1928年提出的。该函数定义如下: 1. ACK(0, n) = n + 1 2. ACK(m, 0) = ACK(m-1, 1) 3. ACK(m, n) = ACK(m-1, ...
Ackerman 函数是一种非常特殊的数学函数,它在计算复杂度理论和计算机科学中被用作一个例子,展示了非平凡的递归函数行为。这个函数以其创造者 Moses Ackerman 的名字命名,它不是普通的算术或组合函数,而是具有...
本实验报告主要探讨了三种使用递归策略的算法:Ackerman函数实现、大数划分以及数据集合的排列组合。 1. **Ackerman函数实现** Ackerman函数是一个经典的双递归函数,其定义如下: - 当n=1且m=0时,A(n, m)=2。 ...
在算法设计与分析的课程中,我们探讨了多个经典算法问题,包括Ackerman函数、斐波那契数列、汉诺塔、阶乘计算、排列生成以及整数划分。这些都是计算机科学基础和算法分析中的重要概念,对于理解和解决复杂问题至关...
由数学家 Willhelm Ackermann 开发的 Ackerman 函数以其极快的增长速度令人印象深刻,并具有更多迷人的功能。 有了这个简单的代码,Ackermann 函数就可以在 Matlab 中轻松使用。
该函数的基本思想是使用递归算法来计算 Ackerman 函数的值。如果 `m` 等于 0,则返回 `n+1`。否则,如果 `n` 等于 0,则返回 `akm ( m-1, 1 )`。否则,返回 `akm ( m-1, akm ( m, n-1 ) )`。 在上面的代码中,我们...
Ackerman函数是一个经典的例子,展示了函数增长速度的极端情况。Ackerman函数是一个双参数函数,定义如下: \[ A(m, n) = \begin{cases} n + 1 & \text{if } m = 0 \\ A(m - 1, 1) & \text{if } m > 0 \text{ ...
1. 递归概述 递归( recursion)是一种编程技巧,某些情况下,甚至是无可替代的技巧。递归可以大幅简化代码,看起来非常简洁,但递归设计却非常抽象,不容易掌握。通常,我们都是自上而下的思考问题, 递归则是...
5. ACKERMAN:该题目考察了Ackerman函数的实现,通过让用户输入多个数字后,计算其结果。 知识点:Ackerman函数、递归函数 6. Arithmetic Progressions:该题目考察了等差数列的处理,通过让用户输入多个数字后,...