terça-feira, 3 de julho de 2012

Conjectura de Collatz





A conjectura de Collatz é devida ao matemático alemão Lothar Collatz. A conjectura estabelece uma seqüência de números, ou trajetória, que a partir de um número natural inicial obedece aos seguintes critérios: Pegue qualquer número natural n . Se n é par, divida-o por 2 para obter n  / 2, se n for ímpar multiplicá-lo por 3 e adicionar 1 para obter 3 n  + 1. Repita o processo (que tem sido chamado de "Half Ou Triplo Plus One", ou HOTPO  ) por tempo indeterminado. A conjectura é que não importa o número que você começar, você sempre vai eventualmente chegar a 1. A propriedade também tem sido chamado de unidade .
Outras informações:
http://en.wikipedia.org/wiki/Collatz_conjecture

Considere o seguinte algoritmo:
      
Consider the following algorithm:

1. input n

2. print n

3. if n = 1 then STOP

         4. if n is odd then n = 3n + 1

         5. else n = n / 2

6. GOTO 2
 

    Dado o número 22 como entrada, a seguinte sequência de números é impressa até chegar na condição de parada do algoritmo 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

      O problema 3n+1 pede para você calcular o tamanho da maior sequência gerada por um número em um dado intervalo.  


       A solução direta para esse problema seria assim:
#include <stdio.h>

typedef long long int lli; 

lli cycle(lli n){
 lli cont;
 cont = 1;
 while(n!=1){
  if(n%2==0) n = n/2;
  else n = 3*n+1; 
  cont++;
 }
 return cont;
}
int main(){ 
 lli max;
 lli n,m,a,b,i,cont;
 
 while( scanf("%lld %lld",&n,&m) > 0 ){
  a = n < m ? n: m;
  b = n > m ? n: m;
  max = 0;
  for(i=a;i<=b;i++){
   cont = cycle(i);
   if(cont > max) max = cont;
  }
  printf("%lld %lld %lld\n",n,m,max);
  
 }
 return 0;
}
 
 

2012-07-03 16:23:28
The 3n plus 1 problemaccepted
  
0.29 1.6M C


Uma maneira de otimizar esse código é aproveitar a sobreposição de subproblemas desse nesse problema utilizando a memorização. Com ela podemos evitar retrabalhos desnecessários.
#include <stdio.h>

typedef long long int lli; 

lli  mem[1000001];

lli cycle(lli n){
  lli t=1;
  lli temp = n;
  
  while(n!=1LL){
    if(n%2==0) n = n/2;
    else n = 3*n+1;
    if(n<=1000000 && mem[n]!=0){
      if(temp <= 1000000){
        mem[temp] = mem[n] + t;
        return mem[temp];
      }else{
        return mem[n]+t;
      }    
    } 
    t++;
  }
  
  if(temp <=1000000) mem[temp] = t;
  return t;
}

int main(){ 
 lli max;
 lli n,m,a,b,i,cont;
 
 while( scanf("%lld %lld",&n,&m) > 0 ){
  a = n < m ? n: m;
  b = n > m ? n: m;
  max = 0;
  for(i=a;i<=b;i++){
   cont = cycle(i);
   if(cont > max) max = cont;
  }
  printf("%lld %lld %lld\n",n,m,max);
  
 }
 return 0;
}



2012-07-03 16:25:58
The 3n plus 1 problemaccepted
  
0.03 9.3M C
Outros links interessantes:
http://www.marcioalthmann.net/2011/06/conjectura-de-collatz/
http://timeroot.zxq.net/collatz.html

Se você gostou dessa postagem, deixe um comentário e curta a nossa página no facebook!


5 comentários:

Rogério Carvalho disse...

mt bom wladimir

Nilo disse...

Esse problema foi atualizado no site Wladimir. O enunciado agora afirma que nenhuma operação precisará de mais que 32 bits.

skox disse...

Saudações pessoal ...

Bom blog este hein e ainda mais este post em particular.

Seguinte: sabiam que em 2011 um pesquisador alemão chamado Gehard Opfer publicou uma possível prova deste problema algorítmico tão famoso ?

Enfim, ainda não saiu o veredicto da comunidade acadêmica internacional, mas de qualquer forma é um início, certo ?!?!

Então, desde já grato por tudo e até qualquer dia por aew ...

Tchau e fui

Unknown disse...
Este comentário foi removido pelo autor.
Aleatorys disse...

Estive brincando com a conjectura, se tiver curiosidade de ver está aqui:
http://aleatorys.blogspot.com.br/2016/07/estive-brincando-com-conjectura-de.html?spref=fb