C Problema de programação em c 3n+1

Caio Emmanuel · 9 de março de 2019

Lendo um livro sobre problemas em programação me deparei com esse clássico problema:

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 esse processo com o novo valor de n, terminando quando n = 1. Por exemplo, a seguinte sequência de números será gerada quando n é 22:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Embora ainda não exista uma prova, os matemáticos acreditam que esse algoritmo sempre termina com n=1, para qualquer inteiro n. Bem, para este problema aqui no Huxley, essa propriedade se mantém para qualquer inteiro menor que 1.000.000.

Para uma entrada n, o "tamanho do ciclo" de n é a quantidade de números gerados até o 1 (incluindo o próprio 1). No exemplo acima, o "tamanho do ciclo" de 22 é 16.

Dado dois números i e j, determine o máximo "tamanho do ciclo" dentre todos os números entre i e j, incluindo tanto i quanto j.

A entrada consiste de 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.

Perceba que a entrada só termina quando não houveram mais números. Descubra como fazer o seu programa funcionar nesse caso. Cada linguagem tem uma forma diferente de ler enquanto ainda houver entrada a ser lida.

Para cada par de inteiros i e j, imprima i e j na mesma ordem na qual eles aparecem na entrada e então imprima o máximo "tamanho de ciclo" encontrado. Esses 3 números devem ser separados por um espaço, com todos os 3 números em uma linha e sendo uma linha de saída para cada linha da entrada.

Veja o arquivo de exemplo para entender melhor o formato da entrada e da saída.

Por exemplo:

Entrada:

1 10
100 200
201 210
900 1000

Saída:

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

Tentando resolver eu cheguei no seguinte código:

#include <stdio.h>
#include <math.h>
int main() {
    
    int i, j, c, n, maior, menor, cg, maiorc=0;
    
    for(cg = 1; cg <= 4; cg++){
        scanf("%d %d", &i, &j);

        if(i >= j){
            maior = i;
            menor = j;
        }
        if(j >= i){
            maior = j;
            menor = i;
        }
        
        for(n = menor; n <= maior; n++){
            int aux=n;
            for(c = 1; aux != 1; c++){
                if(aux%2 == 0){
                    aux = aux / 2;
                }
                else{
                    aux = 3*aux + 1;
                }
            }
            if(c > maiorc){
                maiorc = c;
            }
        }
        
        printf("%d %d %d\n", i, j, maiorc);
        maiorc = 0;
    }
    
    return 0;
    
}

Que quando compilado gera a saída tal qual o exemplo da questão, entretanto, o juiz online onde achei a questão disse que está errado. Já procurei respostas na internet, mas todas elas deixam faltando algo, ou não executam mais de uma vez a entrada. Seria de grande ajuda se alguém pudesse consertar o código. O juiz online que uso é o TheHuxley e essa é a questão 407 do mesmo.

Flávio Pedroza · 9 de março de 2019

O único erro que percebo é que você lê apenas 4 vezes as entradas, enquanto o problema diz " a entrada só termina quando não houveram mais números". Outra coisa é que tem que limitar o valor, "Todos os inteiros serão menores que 1.000.000 e maiores que 0.". Disto isto:

while (1) {
        scanf("%d %d", &i, &j);
		if ((i < 1) || (j < 1) || (i > 1000000) || (j > 1000000)) break;
        if(i >= j){
            maior = i;
            menor = j;
        } else {
            maior = j;
            menor = i;
        }
		...

Pode ser também o fato de que, enquanto no seu código a saída é fornecida a medida que o usuário entra com os dados, o problema exigir que forneça as primeiro todas entradas e somente depois calcule e imprima os resultados, mas não acho eu ficou claro se tem que ser assim mesmo.

Caio Emmanuel · 9 de março de 2019

1 hora atrás, Flávio Pedroza disse:
O único erro que percebo é que você lê apenas 4 vezes as entradas, enquanto o problema diz " a entrada só termina quando não houveram mais números". Outra coisa é que tem que limitar o valor, "Todos os inteiros serão menores que 1.000.000 e maiores que 0.". Disto isto:
while (1) {
        scanf("%d %d", &i, &j);
		if ((i < 1) || (j < 1) || (i > 1000000) || (j > 1000000)) break;
        if(i >= j){
            maior = i;
            menor = j;
        } else {
            maior = j;
            menor = i;
        }
		...
Pode ser também o fato de que, enquanto no seu código a saída é fornecida a medida que o usuário entra com os dados, o problema exigir que forneça as primeiro todas entradas e somente depois calcule e imprima os resultados, mas não acho eu ficou claro se tem que ser assim mesmo.

Já consegui responder, mas obrigado.