Esse é um dos problemas mais simples que tem no UVa mas ao mesmo tempo é muito interessante. O problema 3n + 1, também chamado de Conjectura de Collatz, é um problema da matemática que nunca foi resolvido.
Basicamente é o seguinte:
- Se o número é par, então divida por dois.
- Se o número é ímpar, então multiplique por três e some por um.
Agora que temos a função definida, vamos realizar essa operação repetidamente, começando com um inteiro positivo e depois usando o resultado em cada passo:
O interessante é que essa seqüência parece sempre resultar em 
.
Programando
O desafio enunciado no UVa Online Judge pede para se contar o maior número de m-cíclos em um determinado intervalo de inteiros n, m.
Como eu gosto de coisas simples, fiz um algoritmo em C bem simples. Não recomendo algoritmo complexos.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include <stdio.h> int collatz(int n) { int i = 1; while(n > 1) { if((n % 2) != 0) n = (3*n) + 1; else n = n/2; ++i; } return i; } int main (int argc, char const *argv[]) { int i, j; while(scanf("%d %d", &i, &j) == 2) { int i2, j2, k; int max = 0; if (j < i) { i2 = j; j2 = i; } else { i2 = i; j2 = j; } for (k = i2; k <= j2; ++k) { int atual = collatz(k); if (max < atual) { max = atual; } } printf("%d %d %d\n", i, j, max); } return 0; } |
ou pelo pastebin
Testando as seguintes entradas
1 10
100 200
201 210
900 1000
1 999999
1000 900
temos
1 10 20
100 200 125
201 210 89
900 1000 174
1 999999 476
1000 900 174
Parece tudo certo! 
Agora fica de exercício descobrir a complexidade desse algoritmo. 
Pelo que entendi, o código retorna o maior número de comparações "par ou ímpar" realizado em cada um dos algarismos entre o intervalo entrado. Correto?
Oi Wilson, eu arrumei o post para ficar mais claro o que foi proposto.
Obrigado
Parabéns...Ótima resolução...
A resolução é boa, mas não passa no online judge do UVa, a resolução do problema chega a ser trivial, mas como não é conhecido o numero de ciclos e a entrada é arbitrariamente grande, essa resolução irá exceder o tempo limite porém o caminho está certo, abs!!!
Felipe,
Estava eu sábado, aqui em casa e montei uma resolucão para o problema utilizando python. Fui comparar as respostas e vi que apresentou resultados diferentes para o par 1 999999. Encontrei o resultado 1 999999 525 como solucão. Baixei o fonte da sua resolucão, compilei e executei e o resultado foi o mesmo apresentado aqui 1 999999 476 . Debugando um pouco descobri que ha um erro nesta sua solucão. Os tipos da funcão collatz não podem ser int e sim long int . Dá uma olhada ai e vê se eu estou certo. Abracos.