Problema na otimização do programa [RESOLVIDO]

rodpher
(usa Ubuntu)

Enviado em 05/04/2012 - 19:20h

Oi pessoal! Estou começando agora aqui no viva o linux e espero que vocês possam me ajudar.

Eis a situação: estava tentando resolver o problema 100 da UVa Online Judge, a Conjectura de Collatz.
Ela afirma: imagine um número natural qualquer maior que 1. Se ele for par, divide-se por 2. Se for ímpar, multiplica-se por 3 e adiciona-se 1.
A conjectura diz que para todos os números, esse ciclo de operações sempre termina em 1.
EX: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
30, 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

Sabendo disso, segue o problema da UVa:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&p...

Meu código (abaixo) funciona perfeitamente para os inputs do site:

#include <stdio.h>

int c=0;

int f(int x)

{

if(x==1){

c++;

return 1;

}if(x%2==0){

c++;

return f(x/2);

}if(x%2!=0){

c++;

return f(3*x+1);

}

}

int main()

{

int b, e, x, g=0;

while(1){

scanf("%d%d", &b, &e);

if(b<0 || b>1000000 || e<0 || e>1000000) break;

if(b<=e){

for(x=b;x<=e;x++){

f(x);

if(c>g){

g=c;

}

c=0;

}

printf("%d %d %d\n", b, e, g);

g=0;

}if(b>e){

for(x=e;x<=b;x++){

f(x);

if(c>g){

g=c;

}

c=0;

}

printf("%d %d %d\n", b, e, g);

g=0;

}

}

return 0;

}

 

Porém, quando eu submeto recebo a resposta de que o tempo limite foi atingido e que meu algoritmo não é eficiente.
Como posso otimizar isso? Já pensei em algumas possibilidades, mas nenhuma concreta.
Por favor, me ajudem!

Obrigado.

brunorf
(usa Arch Linux)

Enviado em 05/04/2012 - 20:24h

Olá!
Também participo (algumas vezes) do UVa.
Bom, mas olhando para o seu código, notei algumas coisas fundamentais, que são:
-> Seu algoritmo não tem fim, ou seja, sempre vai estourar o tempo limite (esse é provavelmente o real problema).
-> Sua função f(x) é recursiva. Embora esse não seja o problema do seu código, pode se tornar em outros. Evite as funções recursivas quando possível.

Fiz algumas alterações no seu código, e o resultado final está abaixo:

#include <stdio.h>

 

 

int f(int x)

{

   int c = 1;

    

   while (x != 1)

   {

      x = x%2 ? 3*x+1 : x/2;

      c++;

   }

    

   return c;

}

 

int main()

{

    int i,j,k;

    int maior, ret;

    while (scanf("%d %d", &i, &j) != EOF)

    {

      maior = 0;

      if (j>i)

      {

		  for (k=i; k<=j; k++)

		  {

			 ret = f(k);

			 if ( ret > maior )

			 {

				maior = ret;

			 }

		  }

      }

      else

      {

		  for (k=j; k<=i; k++)

		  {

			 ret = f(k);

			 if ( ret > maior )

			 {

				maior = ret;

			 }

		  }

	  }

      printf("%d %d %d\n", i, j, maior);

   }

    return 0;

}

 

rodpher
(usa Ubuntu)

Enviado em 05/04/2012 - 22:49h

Wow! Não tinha pensado nessa abordagem..aliás foi a primeira vez que eu vi uma aplicação útil do operador ternário.
Bem, o código continua não sendo aceito pela UVa, só que dessa vez não é devido ao estouro do tempo limite. Eles simplesmente falam que o código falhou ):
Vou tentar implementá-lo aqui e, caso eu consiga que a UVa o aceite, posto o código final.

Mas, eu tenho uma pergunta: como assim, meu algoritmo 'não tem fim'?
Eu sei que eu usei uma função recursiva, mas ela tem um momento de parada, quando x=1.
Partindo da informação do próprio problema que a conjectura é válida para todos os números até 1 milhão, minha função nunca cairia num loop infinito. Ela sempre terminaria em 1, se 0 < x < 1.000.000

Bem, obrigado por essa nova visão...eu só conseguia pensar em funções recursivas pra esses problemas.

brunorf
(usa Arch Linux)

Enviado em 06/04/2012 - 09:11h

Eu me referia à função main, no laço principal, onde se lê:

while(1)

{

    scanf("%d%d", &b, &e);

    if (b < 0 || b > 1000000 || e < 0 || e > 1000000) break;

...

}

 

Note que substituí por:

while (scanf("%d %d", &i, &j) != EOF)

{

...

}

 

Na verdade, foi engano meu. Eu não havia visto o break que você colocou no primeiro if. Mas aí ainda tem um problema, visto que sua função main só termina se for entrado um valor "inválido". Mas isso não foi dito na descrição do problema. Então é legal você fazer uma verificação como a que eu coloquei, em que o laço principal termina quando a entrada de dados terminar, ou seja, quando o scanf não ler mais valores.

Tem certeza que não funcionou? Submeti essa solução para o site 2 vezes hoje, e nas duas a solução foi aceita, com tempo de ~0,6 segundos de execução.


E em relação a isso:

As soluções recursivas são úteis, pois para alguns problemas ela é trivial/natural. Por exemplo, tente implementar o quick-sort. Com uma solução recursiva, ele é bem mais fácil de se resolver. Porém, as soluções recursivas são mais custosas, exigem mais do hardware, tornando a solução mais lenta. Então, num lugar como o UVa, elas não são muito interessantes.
Uma alternativa é: primeiro resolva o problema de forma recursiva, quando for necessário. Depois, com calma, tente implementar a versão iterativa.

Lembre-se de que "SEMPRE existe uma versão iterativa para um algoritmo recursivo"


Abraços!

rodpher
(usa Ubuntu)

Enviado em 06/04/2012 - 13:56h

OI!
Realmente, sua solução iterativa é bem mais eficiente que a minha recursividade.


Anotado.

Agora, com relação a:

Na verdade, foi dito sim. Indo a
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&p...
tem uma parte que diz: "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."

Na minha opinião, isso significa que todos os inteiros devem estar entre 0 e 1 milhão. Se esse limite for desrespeitado, o programa termina.

Além disso, fiz alguns testes com o seu código aqui e percebi coisas estranhas:
0) Como você fez pra que os valores maiores ou iguais a 1 milhão não fossem processados?
1) Seu programa nunca vai retornar 0 para nenhum valor digitado. Ou seja, para que você o encerre, você tem que fechá-lo. Isso não é estranho?
Esclareça, por favor.

haha, na verdade o código funcionou sim. Acho que ontem minha net tava um lixo e eu não consegui uploadar direito. Sorry.

Abraços e feliz páscoa.

PS: Só agora percebi que você se livrou daquela variável global no começo. nice going!

rodpher
(usa Ubuntu)

Enviado em 06/04/2012 - 17:20h

Ah sim... faz sentido!
De fato, é melhor fazer o programa receber os números do arquivo txt, afinal todos os testes desse site são feitos assim (suponho)

Apenas um comentário:

E se a entrada fosse 990.000 995.000?
Seria melhor usar um unsigned int. Tem o mesmo tamanho que a int e o dobro da "capacidade" de números positivos.
Ainda assim, não daria conta nem de 10% de todos os casos..acho que vai de 0 a uns 65.000.
O ideal mesmo seria um long int, mas iria ter 8 bytes.

Já que vc conhece a UVa, recomendo um outro site da mesma linha:
http://projecteuler.net/
As questões dele são muito legais...e difíceis também.

vlw pela ajuda.

brunorf
(usa Arch Linux)

Enviado em 06/04/2012 - 18:47h

Não se preocupe, o int "da conta" sim. Ele tem 4 bytes, ou seja, consegue armazenar 4.294.967.296 valores diferentes. Para um signed int, 2.147.483.648 para cada sinal.

Flw, e vlw pela dica!

rodpher
(usa Ubuntu)

Enviado em 06/04/2012 - 19:18h

haha..nada.
Cara, td bem, mas o int abriga no máximo 65.535 valores positivos, caso seja unsigned int.
Se for um int ou signed int, vai "abrigar" de -32.768 até 32.767. Em todos esses casos, com 4 bytes.
Uma prova disso é o seu próprio programa.
Quando eu entrei com valores altos (acima de 100 mil), não houve saída, ou seja, a variável não "suportou" a minha entrada.

Eu sei que deu certo e tudo mais..., mas o ideal seria uma long int, que vai de -2.147.483.648 até +2.147.483.647. Porém, você ocuparia o dobro de memória, 8 bytes.
http://stackoverflow.com/questions/589575/size-of-int-long-etc

Flow...até mais!

brunorf
(usa Arch Linux)

Enviado em 06/04/2012 - 20:24h

Então, o tamanho da variável depende da arquitetura, da implementação do compilador, etc.
No caso de ter 4 bytes, o total de valores é 4294967296, pois 2^32 = 4294967296 (32 bits = 4 bytes)
Para se ter 65536 valores possíveis, o tamanho da variável tem que ser de 2 bytes, pois 2^16 = 65536 (16 bits = 2 bytes).

E, com uma variável de 8 bytes, da pra se armazenar 18.446.744.073.709.551.616 valores diferentes!

Caso queira verificar, compile e execute o seguinte código:

#include <stdio.h>

#include <limits.h>



int main()

{

        printf("Tamanho max. do int %d\n", INT_MAX);

        printf("Tamanho max. do long %ld\n", LONG_MAX);

}

 

Lembrando que ele vai imprimir os valores dos maiores inteiros positivos para int e long, pois são signeds

Flw, abraços!

rodpher
(usa Ubuntu)

Enviado em 06/04/2012 - 22:56h

hmm...é verdade.
O curioso é que nas apostilas que eu tenho aqui, inclusive numa da UFMG, vem dizendo que o int variava naquele intervalo que eu falei antes.
Outra parte curiosa é que o seu programa não processa os ciclos quando um dos números da entrada é maior que 200 mil.
Será que é algo relativo ao compilador ou coisa assim?
Eu só testei no code::blocks, mas posso fazer no gcc depois.

Mais um comentário: eu modifiquei meu código, acrescentando somente o:

        while(scanf("%d%d", &b, &e)!=EOF){

           if(b<0 || b>1000000 || e<0 || e>1000000) break;

           

            /* Resto do código */  

E, dessa vez, fui aceito! \o/
Minha solução foi 0.11s mais lenta que a sua.

Flow.

brunorf
(usa Arch Linux)

Enviado em 07/04/2012 - 09:24h

Que bom que deu certo!

Bom, agora é competir!!!! Hahahaha