Ackermann Function C++实现

Ackermann Function 是用递归方法定义的，定义如下：

（有的资料上阿克曼函数的定义中 m, n 的位置调换了，相应的函数式要对称性地变化，注意取值。）

A: N^2 -> N

它的部分函数值如下：

C++ 代码如下：

1 #include <iostream>
 2 using namespace std;
 3 
 4 __int64 Ackermann (int m, int n)
 5 {
 6     if(m == 0)
 7         return (n + 1);
 8     if( m > 0 && n == 0 )
 9         return Ackermann(m - 1, 1);
10     if( m > 0 && n > 0 )
11         return Ackermann( m - 1, Ackermann(m, n - 1) );
12     cout << "Error!" << endl;  // how to use "exit"?
13     return 0;
14 }
15 
16 int main ()
17 {
18     int a,b;
19     while( cin >> a >> b )
20         printf("%I64d\n", Ackermann(a, b));
21     return 0;
22 }

不过时间复杂度过大，A(4, 1) 就运行崩溃了，好像现在也没有更好的算法了。研究中 -ing。。。

原文链接: https://www.cnblogs.com/jjtx/archive/2012/03/07/2533508.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍