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 problem

accepted

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 problem

accepted

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!