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:

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
 * http://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;
	}

}

• 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:

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
 * http://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));
	}
}

É 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!

Filed in: UVa Online Judge | Tags: 3n + 1, algoritmos, Conjectura de Collatz, Java, The 3n + 1 problem, UVa Online Judge