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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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(); | |
| } | |
| } |
Please leave a comment if you have any question regarding this problem or implementation. Thanks.
Collatz Problem a.k.a. 3n+1 Problem.
adilakhter λ 
2 thoughts on “UVa 371. Ackermann Function”