🥇 Algoritmo: O problema 3n + 1

Considere o seguinte algoritmo para gerar uma sequência de números. Comece com um
inteiro n. Se n for par, divida por 2. Se n for ímpar, multiplique por 3 e some 1. Repita este
processo com o novo valor de n, terminando quando n = 1. Por exemplo, a seguinte
sequência de números será gerada para n = 22:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
É conjecturado (mas ainda não provado) que este algoritmo terminará em n = 1 para
cada inteiro n. Ainda assim, a conjectura é válida para todos os inteiros até pelo menos 1.000.000.
Para uma entrada n, a duração do ciclo de n é o número de números gerados até e
incluindo 1. No exemplo acima, a duração do ciclo de 22 é 16. Dados quaisquer dois
números i e j, você deve determinar a duração máxima do ciclo sobre todos os números
entre i e j, incluindo ambos os pontos finais.

Entrada
A entrada consistirá em uma série de pares de inteiros i e j, um par de inteiros por
linha. Todos os inteiros serão menores que 1.000.000 e maiores que 0.

Saída
Para cada par de inteiros de entrada i e j, saída i, j na mesma ordem em que
apareceram na entrada e, em seguida, o comprimento máximo do ciclo para inteiros entre e
incluindo i e j. Esses três números devem ser separados por um espaço, com todos os três
números em uma linha e com uma linha de saída para cada linha de entrada.
Amostra de entrada Amostra de saída
1 10 1 10 20

100 200 100 200 125
201 210 201 210 89

900 1000 900 1000 174

Solução:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main3NPlusOneProblem {
/ **
* @param args
* @throws IOException
* /
public static void main (String [] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = "";

    //read the input from the console
    while ((input = br.readLine()) != null && !input.trim().equals("n") && !input.trim().equals(""))
    {
        String[] data = input.split("\s+");
        for(String in : data )
        {
            System.out.print(in + " ");
        }

        int startPoint = Integer.parseInt(data[0]);
        int endPoint = Integer.parseInt(data[1]);
        int maxCycleLength = Integer.MIN_VALUE;

        for(int i = startPoint; i<=endPoint; i++)
        {
            int cycleLength = getCycleLength(i);
            if(maxCycleLength < cycleLength)
            {
                maxCycleLength = cycleLength;
            }
        }

        System.out.println(maxCycleLength);
    }

}

private static int getCycleLength(int n) {

    if (n == 1)
    {
        return 1;
    }
    else if (n%2 == 0)
    {
        return 1 + getCycleLength(n/2);
    }
    else
    {
        return 1 + getCycleLength(n*3 + 1);
    }
}

}

Related Posts