問題 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.

考慮下面的算法來生成一個(gè)數(shù)字序列。從整數(shù)n開始。如果n是偶數(shù)，則除以2。如果n是奇數(shù)，乘以3再加1。用新值n重復(fù)此過程，當(dāng)n=1時(shí)終止。例如，將為n=22生成以下數(shù)字序列：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1據(jù)推測（但尚未證明），對于每個(gè)整數(shù)n，此算法將在n=1處終止。盡管如此，對于所有小于或等于1000000的整數(shù)，此推測仍然成立。對于輸入n，n的循環(huán)長度是在1之前（包括1）生成的數(shù)目。在上面的例子中，22的循環(huán)長度是16。給定兩個(gè)數(shù)字i和j，你要確定在i和j之間的所有數(shù)字上的最大周期長度，包括兩個(gè)端點(diǎn)。

輸入

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
100 200
201 210
900 1000

樣例輸出

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;
    }
}