问题 1095: The 3n + 1 problem

题目描述

Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000. For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints.

考虑下面的算法来生成一个数字序列。从整数n开始。如果n是偶数，则除以2。如果n是奇数，乘以3再加1。用新值n重复此过程，当n=1时终止。例如，将为n=22生成以下数字序列：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1据推测（但尚未证明），对于每个整数n，此算法将在n=1处终止。尽管如此，对于所有小于或等于1000000的整数，此推测仍然成立。对于输入n，n的循环长度是在1之前（包括1）生成的数目。在上面的例子中，22的循环长度是16。给定两个数字i和j，你要确定在i和j之间的所有数字上的最大周期长度，包括两个端点。

输入

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

输出

For each pair of input integers i and j, output i, j in the same order in which they appeared in the input and then the maximum cycle length for integers between and including i and j. These three numbers should be separated by one space, with all three numbers on one line and with one line of output for each line of input.

样例输入

样例输出

1 10 20
100 200 125
201 210 89
900 1000 174

import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * User: 76147
 * Date: 2020-01-27
 * Time: 15:14
 * Description:
 */
public class The3n1problem {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int x1 = sc.nextInt();
            int x2 = sc.nextInt();
            System.out.print(x1 + " " + x2 + " ");
            if (x1 > x2) {
                int t = x1;
                x1 = x2;
                x2 = t;
            }
            int max = 0;
            for (int i = x1; i <= x2; i++) {
                int temp = len(i);
                if (temp > max) {
                    max = temp;
                }
            }
            System.out.println(max);
        }
    }

    private static int len(int i) {
        int len = 0;
        while (i != 1) {
            if (i % 2 == 0) {
                i = i / 2;
            } else {
                i = i * 3 + 1;
            }
            len++;
        }
        return len + 1;
    }
}