[Java] 100 – The 3n + 1 problem

[Java] 100 – The 3n + 1 problem

題目連結:UVa Online Judge

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

if(n%2 == 1)
    int number = (3 * n) + 1;
else
    n = n/2;


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

解答如下,實際執行時間為0.936sec:

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();
        }
    }
}
(Visited 19 times, 1 visits today)
Comments are closed.