-
-
Save dave-maldonado/4090410 to your computer and use it in GitHub Desktop.
Programming Challenges (Skiena) - first problem "3n+1 problem"
This file contains hidden or 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
class myStuff implements Runnable{ | |
/* Collatz conjecture problem: Skiena's Programming Challenges textbook: | |
* This program accepts two ints representing a range of ints from the robo-judge. | |
* For each int in the range it peforms the HOTPO operation to produce a hailstone sequence. | |
* outputs (prints) the first and second ints inputted and the largest hailstone sequence. | |
* produced from the range | |
*/ | |
public void run(){ | |
String input; | |
int i, j, accum, cycleLen, maxCycleLen; | |
while ((input = Main.ReadLn(255)) != null) { | |
StringTokenizer tokens = new StringTokenizer(input); // tokenize input string | |
i = Integer.parseInt(tokens.nextToken()); // first int from input | |
j = Integer.parseInt(tokens.nextToken()); // second int from input | |
cycleLen = 1; // cycle length of current Collatz sequence | |
maxCycleLen = 0; // maximum cycle length of Collatz sequence from integer i thru j | |
int min, max; // for reordering inputs if i > j | |
// assign min and max to i and j | |
if (i > j) { | |
min = j; | |
max = i; | |
} | |
else { | |
min = i; | |
max = j; | |
} | |
// init and fill array with i thru j values | |
accum = min; // accumulator for filling array | |
int[] arr = new int[max - min + 1]; | |
for (int k = 0; k < arr.length; k++) { | |
arr[k] = accum++; | |
} | |
// peform logic on each element in array | |
for (int k : arr) { | |
cycleLen = 1; // it's 1 rather than 0 to account for the beginning value | |
while (k != 1) { | |
if (k % 2 == 0) | |
k /= 2; | |
else | |
k = k * 3 + 1; | |
cycleLen += 1; | |
} | |
if (cycleLen > maxCycleLen) | |
maxCycleLen = cycleLen; | |
} | |
// print largest hailstone sequence from integer i thru j | |
System.out.println(i + " " + j + " " + maxCycleLen); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment