UVa 371. Ackermann Function

The underlying concepts of UVa 371: Ackermann Functions have been discussed in great details in our post of Collatz problem. In this post, we simply outlines an ad-hoc algorithm as a solution to this problem as follows.

import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
private final Scanner in;
private final PrintWriter out;
private final static int _MaxValue = 1000000;
private final static long[] memo = new long[_MaxValue];
public Main() {
in = new Scanner(System.in);
out = new PrintWriter(System.out, true);
}
public Main(Scanner in, PrintWriter out) {
this.in = in;
this.out = out;
}
private static long[] getInts(String input) {
String[] ints = input.trim().split(" ");
long[] rets = new long[2];
rets[0] = Long.parseLong(ints[0]);
rets[1] = Long.parseLong(ints[1]);
return rets;
}
private void solveAckermannProblem(long from, long to) {
long maxValue = from;
long maxLength = 0;
for (long i = from; i <= to; i++) {
long length = computeCycleLength(nextAckermannNumber(i));
if (maxLength < length) {
maxValue = i;
maxLength = length;
}
}
out.println(String
.format("Between %d and %d, %d generates the longest sequence of %d values.",
from, to, maxValue, maxLength));
}
private static long computeCycleLength(long n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
if (n < _MaxValue && memo[(int) n] != 0)
return memo[(int) n];
long len = 1 + computeCycleLength(nextAckermannNumber(n));// computing
// length of
// Ackermann
// sequence
if (n < _MaxValue) // storing it in cache
memo[(int) n] = len;
return len;
}
public static long nextAckermannNumber(long n) {
if (n % 2 == 0)
return n / 2;
else
return n * 3 + 1;
}
public void run() {
while (in.hasNextLine()) {
long[] range = getInts(in.nextLine());
if ((range[0] == 0) && (range[1] == 0))
break;
long from = Math.min(range[0], range[1]);
long to = Math.max(range[0], range[1]);
solveAckermannProblem(from, to);
}
}
public static void main(String[] args) {
Main solver = new Main();
solver.run();
}
}
view raw UVa371.java hosted with ❤ by GitHub

Please leave a comment if you have any question regarding this problem or implementation. Thanks.


See Also

see Collatz Problem a.k.a. 3n+1 ProblemCollatz Problem a.k.a. 3n+1 Problem.
see UVa100. 3n+1 ProblemUVa 100. 3n+1 Problem.

2 thoughts on “UVa 371. Ackermann Function”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s