0

我想编写一个在 S. Wolf 的数学逻辑之旅中定义的函数（Ackermann 函数的修改版本），如下所示：

A(0,n)=n+1 对于每个 n

A(1,0)=2

A(2,0)=0

A(m+3,0)=1 对于每 m

A(m+1,n+1)=A(m,A(m+1,n)) 对于每个 m 和 n

为了制作一个更快的程序，我使用了以下事实

  • A(1,n)=n+2

  • A(2,n)=2n

  • A(3,n)=2^n

这是代码：

#include <iostream>
#include <cmath>

using namespace std;

long long A(long long m, long long n)
{
    if(m==0)
        return n+1;
    else if(m==1)
        return n+2;
    else if(m==2)
        return 2*n;
    else if(m==3)
        return pow(2,n);
    else if(m>=4 && n==0)
        return 1;
    else
        return A(m-1,A(m,n-1));
}

int main(void)
{
    long long m,n;
    cout << "m=";
    cin >> m;
    cout << "n=";
    cin >> n;
    cout << "A(m,n)=" << A(m,n) << endl;
    return 0;
}

它似乎工作正常：手动 A(5,3)=2^16 这就是我得到的结果。但是，程序输出 A(5,4)=4 和 A(5,5)=2^16，而正确的结果确实很大。我无法在我的代码中发现错误。你能告诉我有什么问题吗？先感谢您。

4

1 回答 1

0

正如 NeilButterworth 在评论中所说，错误结果背后的原因是溢出。

正如评论中的 RobertAndrzejuk 所建议的那样，我使用了另一个库 (GMP) 来处理大量数字。这是新代码：

#include <iostream>
#include <cmath>
#include <gmpxx.h>

using namespace std;

mpz_class pow(int a,mpz_class b)
{
    mpz_class res=1;
    for(int i=1;i<=b;++i)
        res*=a;
    return res;
}

mpz_class A(mpz_class m, mpz_class n)
{
    if(m==0)
        return n+1;
    else if(m==1)
        return n+2;
    else if(m==2)
        return 2*n;
    else if(m==3)
        return pow(2,n);
    else if(m>=4 && n==0)
        return 1;
    else
        return A(m-1,A(m,n-1));
}

int main(void)
{
    mpz_class m,n;
    cout << "m=";
    cin >> m;
    cout << "n=";
    cin >> n;
    cout << "A(m,n)=" << A(m,n) << endl;
    return 0;
}

该程序能够计算 A(4,5)，它有 19729 位数字（我无法验证结果是否正确，但 A(4,5) 的确切位数确实是 19729 所以我相信结果是正确的）。然后，当我要求它计算 A(5,4) 时，程序显示分段错误，这确实是巨大的。

于 2018-04-16T10:11:36.290 回答