C Tempo de execução de um programa - simplificação de algoritmo

kampa896 · 6 de outubro de 2021

Senhores, boa tarde!

Estou estudando a linguagem C e colocando em prática através de resoluções de diversos exercícios. Me deparei com um, de um site conhecido, e o site retornou como "tempo limite excedido". Creio que deva ser devido a resposta do programa não ser em tempo hábil, definido pelo site. Dessa forma, trata-se de otimização do código, para ser mais simples, mais eficiente. Colocarei o enunciado e o código aqui, pra ver se alguém me da uma ajuda. Já dediquei um tempo considerável nesta questão, para chegar onde cheguei e não vejo como simplificar ainda mais.

Hyam é um menino que adora sequências. Ele anda descobrindo sequências interessantes que nem mesmo Fibonacci imaginaria. Certo dia, Hyam percebeu que dado um número N, ele poderia fazer uma sequência do tipo 0 1 2 2 3 3 3 4 4 4 4 ... N N N ... N. No entanto, Hyam percebeu que cada valor que aumentava no número da sequência, a quantidade total de números da sequência aumentava semelhantemente à um crescimento fatorial, neste caso, ao invés de multiplicar, soma-se o número total de números da sequência com o valor do próximo número da sequência. Por exemplo, se N = 2. A sequência correta seria 0 1 2 2, obtendo-se 4 digitos. Agora, se N = 3, o próximo número da sequência tem valor 3, então a quantidade total de número da sequência seria a quantidade de números com N = 2, que é 4, mais o valor do próximo número da sequência, neste caso 3, obtendo-se 7, já que a sequência correta para N = 3 é 0 1 2 2 3 3 3.

Sua tarefa é fazer um algoritmo que dado um número inteiro N, tenha como resposta a quantidade total de números dessa sequência e logo abaixo a sequência completa.

Entrada

A entrada é composta de vários casos de testes. Cada caso é composto por um inteiro N (0<=N<=200) que indica o valor dos últimos N números da sequência.

A entrada termina com final de arquivo (EOF).

Saída

A saida é no formato Caso X: N numeros onde X é a ordem do número de casos e N é a quantidade de numeros que contém na sequência completa, na próxima linha a sequência de números com um espaço entre eles. É pedido que deixe uma linha em branco após cada caso.

Exemplo de EntradaExemplo de Saída

0

1

2

3

Caso 1: 1 numero

0

Caso 2: 2 numeros

0 1

Caso 3: 4 numeros0 1 2 2

#include <stdio.h>

int qtd(int total);

int main() {

    int casos = 1, numero, i, j;

    scanf("%d", &numero);

    if(numero == 0){
    	printf("Caso %d: %d numero\n", casos, qtd(numero));
    }
    else{
    	printf("Caso %d: %d numeros\n", casos, qtd(numero));
    }

    while(numero != EOF){
    	if(numero == 0){
    		printf("%d", numero);
    	}
    	else{
    		printf("0 ");
    		for(i = 0; i <= numero; i++){
				for(j = 0; j < i; j++){
					if(j == numero){
						printf("%d", i);
					}
					else{
						printf("%d ", i);
					}
				}
    		}
    	}
        printf("\n\n");
        casos++;
        scanf("%d", &numero);
        if(numero == 0){
        	printf("Caso %d: %d numero\n", casos, qtd(numero));
        }
        else{
        	printf("Caso %d: %d numeros\n", casos, qtd(numero));
        }
    }

    return 0;
}

int qtd(int total){
	if(total == 0){
		return 1;
	}
	return total + qtd(total - 1);
}

Caso 4: 7 numeros

0 1 2 2 3 3 3

arfneto · 6 de outubro de 2021

Parece muito complicado mesmo...

3 horas atrás, kampa896 disse:

Sua tarefa é fazer um algoritmo que dado um número inteiro N, tenha como resposta a quantidade total de números dessa sequência e logo abaixo a sequência completa.

É uma pena não poder inverter a ordem e mostrar primeiro a sequência

Seu programa de novo, com menos espaços:

#include <stdio.h>

int qtd(int total);

int main()
{
    int casos = 1, numero, i, j;
    scanf("%d", &numero);
    if (numero == 0)
    {
        printf("Caso %d: %d numero\n", casos, qtd(numero));
    }
    else
    {
        printf("Caso %d: %d numeros\n", casos, qtd(numero));
    }

    while (numero != EOF)
    {
        if (numero == 0) { printf("%d", numero); }
        else
        {
            printf("0 ");
            for (i = 0; i <= numero; i++)
            {
                for (j = 0; j < i; j++)
                {
                    if (j == numero) { printf("%d", i); }
                    else
                    {
                        printf("%d ", i);
                    }
                }
            }
        }
        printf("\n\n");
        casos++;
        scanf("%d", &numero);
        if (numero == 0)
        {
            printf("Caso %d: %d numero\n", casos, qtd(numero));
        }
        else
        {
            printf("Caso %d: %d numeros\n", casos, qtd(numero));
        }
    }

    return 0;
}

int qtd(int total)
{
    if (total == 0) { return 1; }
    return total + qtd(total - 1);
}

Tem um loop com um loop dentro e depois outro, e múltiplas condições. Mas tudo o que quer é uma série de operações onde mostra o fatorial de um número e depois a sequência. E não tem uma função que calcula o fatorial? Nem uma função para fazer um único teste?

E porque não lê de uma arquivo que já tem o que sabe, no caso

0 1 2 3

?

E no geral pode guardar os números que já calculou. Não precisa ser "honesto" nesse tipo de aplicação. Isso se chama cache e pode guardar alguns dos números que já processou...

kampa896 · 6 de outubro de 2021

Obrigado pelas dicas, @arfneto!

JorgeGus · 6 de outubro de 2021

@kampa896 Não sei se está mais rápido, mas parece estar mais simples.

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    int caso = 1;
    while ((scanf("%d", &n) != EOF)) {
        int quant = 1;
        for (int c = 1; c <= n; c++) {
            quant += c;
        }
        printf("Caso %d: %d numero%s\n0", caso, quant, (quant > 1 ? "s" : ""));
        for (int c = 1; c <= n; c++) {
            for (int d = 0; d < c; d++) {
                printf(" %d", c);
            }
        }
        caso++;
        printf("\n\n");
    }
    return 0;
}

arfneto · 7 de outubro de 2021

5 horas atrás, kampa896 disse:

Obrigado pelas dicas, @arfneto!

Nesse tópico eu não tinha ainda escrito isso: escreva em torno dos dados e não comece a programar antes de ter uma boa ideia do que são os seus dados.

Lendo melhor os exemplos do enunciado:

0         0
1         0 1
2         0 1 2 2
3         0 1 2 2 3 3 3 
4         0 1 2 2 3 3 3 4 4 4 4 

// ...

Então, mais conhecidos os dados, tudo pode ser bem mais simples.

Essa conta, conhecida desde o ensino fundamental, deve dar o total de números sem estourar o tempo de processamento :

        int numero = 1 + (1 + N) * N / 2;

Porque?

sempre tem ao menos o zero
exceto pelo 0 o resto é uma progressão aritmética de razão 1 e N termos
para 0 termos a soma acima é meio zero, o popular 0

E assim esse loop é algo já conhecido, @JorgeGus

4 horas atrás, JorgeGus disse:

        int quant = 1;
        for (int c = 1; c <= n; c++) {
            quant += c;
        }

e seu programa pode ficar ainda um pouco mais simples. E não precisa incluir stdlib e nem das chaves no printf no loop.

Podem considerar algo assim

#include <stdio.h>
int main(void)
{
    int N   = 0;  // o numero, entre 0 e 200
    int res = scanf("%3u", &N);
    while (res == 1)
    {
        int caso   = 0;
        int numero = 1 + (1 + N) * N / 2;
        printf(
            "Caso %d: %d numero%s\n0", ++caso, numero,
            (numero > 1 ? "s" : ""));
        for (int termo = 1; termo <= N; termo += 1)
            for (int rep = 1; rep <= termo; rep += 1)
              printf(" %d", termo);
        printf("\n\n");
        res = scanf("%3u", &N);  // le outro
    };  // while
    return 0;
}

ligeiramente mais simples. E economiza uns ciclos.

devair1010 · 7 de outubro de 2021

@kampa896 parece que essa função recursiva que você usou , seja a causa da perda de tempo no limite , do uri online judge , melhor deixar tudo dentro da função main , e essa Questão 2028 , com esse código aqui bem parecido com o que o @arfneto postou foi accepted

#include <stdio.h>
int main()
{
    int w,k,b,x=0;
    while(scanf("%d",&w) != EOF)
    {
        int z = 1;
        x++;
        z += ((w*(w + 1)) / 2);
        if(w == 0)
            printf("Caso %d: %d numero\n",x,z);
        else
            printf("Caso %d: %d numeros\n",x,z);
        printf("0");
        for(k=1;k<=w;k++)
        {
            for(b=1;b<=k;b++)
                printf(" %d",k);
        }
        printf("\n\n");
    }
    return 0;
}

arfneto · 7 de outubro de 2021

não sei se minha resposta seria "aceita" mas esse programa aceito pode melhorar bem

É claro que acaba sendo semelhante ou mesmo igualzinho, porque é um programa muito simples e isso acaba convergindo.

Mas pode ser interessante falar das diferenças

A fórmula da soma da PA é conhecida desde o ensino médio, mas isso aqui

        int z = 1;
        x++;
        z += ((w*(w + 1)) / 2);

é bobagem. Qual o propósito de, dentro do loop, declarar a variável valendo 1 e duas linhas abaixo somar uma expressão? E para que os parenteses externos? online judge não é o comitê de revisão da empresa, nem mantem empregos.

No geral prefira o que qualquer profissional usaria:

        int numero = 1 + (1 + N) * N / 2;

Por outro lado isso

       if(w == 0)
            printf("Caso %d: %d numero\n",x,z);
        else
            printf("Caso %d: %d numeros\n",x,z);

é o mesmo que

        printf(
            "Caso %d: %d numero%s\n0", ++caso, numero,
            (numero > 1 ? "s" : ""));

a expansão da expressão dentro do printf() vai gerar praticamente o mesmo código

E

os nomes das variáveis fazem diferença
todas as variáveis com nomes de uma letra não é assim fácil de ler
não é esperto declarar todas variáveis na mesma linha
NUNCA teste o retorno de scanf() comparando com EOF. Compare com o número de especificadores usados, no caso 1. A menos que vá testar também os outros valores. Porque? Simples: se scanf() não ler nada vai retornar zero. Se tiver 4 especificadores pode retornar 0 1 2 ou 3. Ou EOF. Se testar apenas EOF já deu pra ver que está errado. Ou não?
main() deve ser main(void). Mais expressivo.
as chaves no primeiro for são desnecessárias, mas se tem nesse deveria ter no outro. Ou tem nos dois ou em nenhum
aquele printf() solitário com o zero é difícil de justificar. Chamar a função de novo sempre para imprimir uma única letra?
dentre todos os operadores de incremento o menos recomendável é o único usado no programa. Prefira x+=1 ou x = x + 1, depois ++x, e no fim da lista x++.
@kampa896ao postar uma questão de um serviço conhecido poste o link e o número da questão, como @devair1010achou e listou (mas sem o link).

kampa896 · 7 de outubro de 2021

Gostaria de agradecer a todos. Realmente, o uso da função recursiva excedeu o tempo de resposta do programa. Obrigado @JorgeGus, @arfneto e @devair1010.

Eu não postei a fonte do problema com receio de não cumprir alguma regra do site por citar outros serviços, mas farei da próxima vez.

Vocês são top.

devair1010 · 8 de outubro de 2021

@kampa896 ok , e olha o link da Questão aqui :

https://www.urionlinejudge.com.br/judge/pt/problems/view/2028

e da minha solução aqui :

https://www.urionlinejudge.com.br/judge/pt/runs/code/8907166

kampa896 · 8 de outubro de 2021

@devair1010 obrigado, meu amigo!

devair1010 · 9 de outubro de 2021

Em 07/10/2021 às 11:55, arfneto disse:

não sei se minha resposta seria "aceita"

pois é . . . ! , e eu enviei esse seu código para o uri e , não , ele não foi aceito , e é lógico que ele está bom e funciona certo , iguais ao meu e ao do @kampa896 @JorgeGus , mas não basta funcionar certo , precisa ser do jeito que eles querem , por exemplo : no final pular uma linha , e etc . . .

arfneto · 9 de outubro de 2021

7 horas atrás, devair1010 disse:

ois é . . . ! , e eu enviei esse seu código para o uri e , não , ele não foi aceito , e é lógico que ele está bom e funciona certo , iguais ao meu e ao do @kampa896 @JorgeGus , mas não basta funcionar certo , precisa ser do jeito que eles querem , por exemplo : no final pular uma linha , e etc . . .

Se fosse aceito seria por acaso porque não li o enunciado e nem me importei com qualquer critério, @devair1010 Evito muito entrar nesses sites de programação competitiva. Minha grande curiosidade com esse Online Judge por exemplo era saber o que era o U o R e o I Universidade Regional Integrada. Parei aí.

Em relação aos códigos alternativos sei que esse que eu mostrei está certo em relação ao que está descrito no tópico, e é mais eficiente e legível que os outros dois que a gente viu (no tópico), pelas razões que expliquei