[Java] 100 – The 3n + 1 problem

題目連結：UVa Online Judge

本來中間的if/else判斷是用

[code lang=”java”]
if(n%2 == 1)
int number = (3 * n) + 1;
else
n = n/2;
[/code]

後來考慮到會超過執行時間，故改成用>>位移運算子來代替。而輸出時，需按照官方的格式輸出，所以用replaceAll，將”\\s”之正規表示式換成” “，否則會有presentation error產生。

解答如下，實際執行時間為0.936sec：
[code lang=”java”]
public class Test_3N_1 {
public static long countIteration(long i) {
long n = i;
long count = 1;
while (n > 1) {
if (((n – 1) >> 1) == (n >> 1)) {
long number = (3 * n) + 1;
if (number < n) {
//TODO
} else {
n = number;
}
} else {
n = n >> 1;
}
count++;
}
return count;
}
public static long countMaxIterationBetweenTwoNumbers(long a, long b) {
final long big;
final long small;
if (a > b) {
big = a;
small = b;
} else {
small = a;
big = b;
}
long winner = -1;
for (long i = small; i < big; i++) {
long count = countIteration(i);
if (count > winner) {
winner = count;
}
}
return winner;
}
public static void main(String[] args) {
try {
final BufferedReader reader = new BufferedReader(new
InputStreamReader(System.in));

String line;
while ((line = reader.readLine()) != null) {
String REGEX_WHITESPACE = "\\s+";
String cleanLine = line.trim().replaceAll(REGEX_WHITESPACE, " ");
String[] tokens = cleanLine.split(REGEX_WHITESPACE);
if (tokens.length == 2) {
long a = new Long(tokens[0]).longValue();
long b = new Long(tokens[1]).longValue();
System.out.println(cleanLine + " "+
countMaxIterationBetweenTwoNumbers(a, b));
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
[/code]