UVa: Começando com Problemas de Torneio de Programação - Problema 3n + 1
Tempos atrás perguntei no twitter se o pessoal estaria interessado em artigos/tutoriais sobre problemas torneio de programação. Mas não no sentido de dicas para torneios, e sim focando nos algoritmos.
Já publiquei aqui no blog uma página com alguns problemas do UVa Online Judge que resolvi em Java. E esse problemas são ótimos para melhorar a lógica de programação, além da oportunidade de aprender mais algoritmos. E isso é super importante para a nossa carreira, pois não fazemos aplicações que requerem apenas trabalho braçal, mas sim intelectual.
O UVa Online Judge é um dos juízes online mais utilizados, e tem dezenas de problemas para serem resolvidos, desde problemas fáceis à problemas difíceis.
Alguns algoritmos que são usados para resolver esses problemas: adhoc (simulação), ordenação e busca, grafos, teoria matemática, etc. Esses algoritmos também são legais para ter uma idéia de como podem ser usados num contexto mais ou menos real, já que na faculdade a gente aprende a fazer algoritmo de grafos, mas geralmente não estão contextualizados.
Aqui no blog, vou focar em Java. A linguagem mais apropriada para torneios é C, C++, mas aqui faço por hobby.
Vamos então começar com o problema mais clássico, que é o primeiro a ser resolvido que é o número 100: 3n + 1.
Link do problema no UVa aqui.
Este problema também é conhecido como Conjectura de Collatz e nunca foi resolvido.
O problema consiste no 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.
O problema no Uva pede para contar o número de m-ciclos em um determinado intervalo de inteiros n, m.
Vamos então ao código:
[code lang="java" firstline="1" toolbar="true" collapse="false" wraplines="false"]
package com.loiane.uva;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* Problem 100 - The 3n + 1 problem
*
* Problem Link:
* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36
*
* Run time: 0.208s
*
* @author Loiane Groner
* https://loiane.com
* http://loianegroner.com
*/
public class Main {
static int[] cache = new int[1000001];
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String s;
long i, j;
String[] tokens;
final String regexWhitespace = "\\s+";
final String whiteSpace = " ";
while ((s = bf.readLine()) != null){
s = s.trim().replaceAll(regexWhitespace, whiteSpace);
tokens = s.trim().split(whiteSpace);
i = Long.parseLong(tokens[0]);
j = Long.parseLong(tokens[1]);
System.out.println(i + whiteSpace + j + whiteSpace + countCycle(i,j));
}
}
static int countCycle (long n, long m){
long i, j;
int max = 0;
int aux;
if (n > m){
i = m;
j = n;
} else{
i = n;
j = m;
}
for (long k=i; k<=j; k++){
aux = collatz(k);
if (max < aux){
max = aux;
}
}
return max;
}
static int collatz(long n){
long index = n;
if (cache[(int) n] != 0){
return cache[(int) n];
}
int count = 1;
while (n > 1){
if ((n % 2) == 0){
n /= 2;
} else{
n = (n*3)+1;
}
count++;
}
cache[(int) index] = count;
return count;
}
}
[/code]
- O problema consiste na leitura de dois números inteiros: i e j por linha. Não temos um número exato de linhas, por isso lemos até acabar, ou seja, a entrada for nula.
- Uma dica para leitura de números: BufferedReader + Long.parseLong() é mais rápido do que Scanner.
- Fazemos trim e eliminamos todos os espaços da linha pois não sabemos se pode vir algum "lixo".
- No método countCycle verificamos qual número é maior (i ou j) para fazermos o passe no loop (pode vir com a ordem trocada, não sabemos).
- O método collatz faz o cálculo que queremos.
- Usamos um cache de tamanho 1.000.000, pois isso vai nos ajudar a ganhar tempo. Por exemplo, suponha que tenha uma entrada 1 100, então vamos calcular esse período e guardar no cache. Depois temos uma entrada 1 200, ou seja, podemos usar o que já calculamos antes e calcular apenas o período novo (101 a 200).
- O limite de run time desse problema é de 3s. O algoritmo acima foi executado em 0.208 (o que é um tempo bom para Java).
- Outra dica: toda classe submetida para o UVa em Java deve ter o nome Main, isso é padrão. Se tentar submeter com outro nome, não vai funcionar. O arquivo também não pode conter nenhum comentário. Também não podem pertencer à nenhuma pacote, tem que ser default.
Testando o input e output:
[code lang="java" firstline="1" toolbar="true" collapse="false" wraplines="false"]
package com.loiane.uva;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
/**
* Test Case
* Problem 100 - The 3n + 1 problem
*
* @author Loiane Groner
* https://loiane.com
* http://loianegroner.com
*/
public class TestProblem100 {
@Test
public void testProblem100(){
assertEquals(20, Main.countCycle(1, 10));
assertEquals(125, Main.countCycle(100, 200));
assertEquals(89, Main.countCycle(201, 210));
assertEquals(174, Main.countCycle(900, 1000));
}
}
[/code]
É isso pessoal! Conto com o feedback de vocês para saber se querem que continue com essa série.
Em cada problema podemos mostrar um algoritmo novo! Esses algoritmos também são ótimos para treinar TDD. :)
Bons códigos!