It is my code:The Ackermann function is the simplest example of a well-defined Total Function which is Computable but not Primitive Recursive, providing a counterexample to the belief in the early 1900s that every Computable Function was also Primitive Recursive. It grows faster than an exponential function, or even a multiple exponential function. The Ackermann function A(x, y) is defined by
-- y + 1 If x = 0
A(x, y) = | A(x − 1, 1) If y = 0
-- A(x − 1,A(x, y − 1)) Otherwise.
Write a program to calculate the Ackermann function. How large of x, y can you calculate on your computer?
Input The input consists of the number of test cases, m, in the first line and followed by m lines of two positive integers x and y separated by a space as the inputs to A(x, y). For example,
3
3 0
0 3
3 5
Output The output should be m lines of A(x, y).
5
4
253
Code: Select all
#include <stdio.h>
long ack(long x, long y);
long ack(long x, long y)
{
if (x == 0) return (y+1);
if (y == 0) return (ack(x-1, 1));
return (ack(x-1, ack(x, y-1)));
}
int main(int argc, char **argv)
{
long m, i, x, y;
while((scanf("%ld\n", &m)) != -1)
{
for(i=0;i<m;i++)
{
scanf("%ld%ld\n", &x, &y);
printf("%ld\n", ack(x, y));
}
}
return 0;
}