OiClass.com Q&A P1194

这次提问的人是自己

P1194 阿克曼函数超时怎么破？

代码：

#include "iostream"

using namespace std;

int x, y, ans;

int ack(int m, int n){
    if (m == 0){
        return n += 1;
    }
    if (m > 0 && n == 0){
        return ack(m - 1, 1);
    }
    if (m > 0 && n > 0){
        return ack((m - 1), ack(m, n - 1));
    }
}

int main(){
    cin >> x >> y;
    ans = ack(x, y);
    cout << ans;
}

运行结果：

image

解决方法：（超水（nan））

拿出草稿纸，把阿克曼函数m值从0到3的展开算了一遍，如下：

\(ack(0, n) = n + 1\)

\(ack(1, n) = n + 2\)

\(ack(2, n) = 2n + 3\)

\(ack(3, n) = 2^{y + 3} - 3\)

最终代码实现：

#include "iostream"
#include "cmath"

using namespace std;

int x, y;

int main(){
    cin >> x >> y;
    if (x == 0){
        cout << y + 1;
    }else if (x == 1){
        cout << y + 2;
    }else if (x == 2){
        cout << 2 * y + 3;
    }else if (x == 3){
        cout << pow(2, y + 3) - 3;
    }
}