Ir ao conteúdo

Posts recomendados

Postado

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.

 

  • Curtir 1
Postado

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.

  • Curtir 1
Postado
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.

Crie uma conta ou entre para comentar

Você precisa ser um usuário para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...

LANÇAMENTO!

eletronica2025-popup.jpg


CLIQUE AQUI E BAIXE AGORA MESMO!