计算ackermann函数的较大值 [英] Calculating larger values of the ackermann function

问题描述

我有一些代码：

int CalculateAckermann(int x, int y)
{
    if(!x)
    {
    	return y++;
    }
    if(!y)
    {
    	return CalculateAckermann(x--,1);
    }
    else
    {
    	return CalculateAckermann(x--, CalculateAckermann(x, y--));
    }
}

用于计算ackermann函数。在x和y相当低的数量上，应用程序导致堆栈溢出，因为它递归太深，导致相当大的数字。

Designed to calculate the ackermann function. Above a fairly low number of x and y the application causes a stack overflow because it recurses too deeply and results in pretty big numbers. How would I go about slowly calculating a solution?

推荐答案

注意，如果你只想使用封闭形式，那么m <4的算法是直接的。如果你想扩展到tetration，那么我建议你写一个fastpower算法，可能使用二进制方法，然后使用该方法，你可以写一个tetration函数。其格式如下：

As a note if you wish to just used the closed form, then the algorithms for m<4 are straightforward. If you wish to extend to tetration, then I suggest you write a fastpower algorithm probably using the binary method and then with that method you can write a tetration function. Which would look something like:

int Tetration(int number, int tetrate)
{
    long int product=1;
    if(tetrate==0)
    	return product;
    product=number;
    while(tetrate>1)
    {
    	product=FastPower(number,product);
    	tetrate--;
    }
    return product;
}

然后你可以覆盖n == 4的情况，然后使用递归定义和值的A（5，n）溢出在一个可笑的速度，所以它真的不关心。虽然你的老师可能不会满意这样的算法，但它会运行得更快。在我的一个离散类中，当我要求写一个算法来计算斐波纳契数，然后找到它的O（n），我写了封闭的形式，然后写了O（1）并获得了完全信用，一些教授喜欢聪明的答案。

Then you can cover cases up to n==4 and after that use the recursive definition and values of A(5,n) overflow at a ridiculous rate, so it's really of no concern. Although your teacher probably won't be satisfied with an algorithm such as this, but it will run much faster. In one of my discrete classes when I asked to write an algorithm to compute the fibonacci numbers and then find its O(n), I wrote the closed form and then wrote O(1) and got full credit, some professors appreciate clever answers.

关于Ackerman函数，需要注意的是，它基本上定义了加法函数对整数的亲和度，A（1，n） n）是乘法，A（3，n）是求幂，A（4，n）是tetration，在5之后，函数变得太快以至于不能适用。

What is important to note about the Ackerman function is it essentially defines the heirachy of additive functions on the integers, A(1,n) is addition , A(2,n) is multiplication, A(3,n) is exponentiation, A(4,n) is tetration and after 5 the functions grow too fast to be applicable to very much.

另一种查看加法，乘法等的方法是：

Another way to look at addition, multiplication, etc is:

Φ0 (x, y ) = y + 1
Φ1 (x, y ) = +(x, y )
Φ2 (x, y ) = ×(x, y )
Φ3 (x, y ) = ↑ (x, y )
Φ4 (x, y ) = ↑↑ (x, y )
           = Φ4 (x, 0) = 1 if y = 0
           = Φ4 (x, y + 1) = Φ3 (x, Φ4 (x, y )) for y > 0

（使用前缀符号，即+（x，y）= x + y， x，y）= x y。

(Uses prefix notation ie +(x,y)=x+y, (x,y)=xy.

这篇关于计算ackermann函数的较大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！