Felipe Tonello

looong #fail no GCC

2010-07-29T20:35:37Z

O uso do long long como tipo de dado foi introduzido no padrão ISO C99. Isso acabou gerando uma revolta na comunidade acadêmica que achava o cúmulo ter de usar long long ao invéz de um nome específico, argumentando “qual será a próxima? long long long, long long long long … “.

Bom, o que parece é que o pessoal do GCC também não foi muito com a cara desse long long não.

long long long #fail no gcc

#FAIL para a ISO C99 ou pro GCC? Fica a dúvida.

Problema 3n + 1 no UVa

2010-06-09T18:08:39Z

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.

#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.

Novamente nos embarcados

2010-06-07T20:02:12Z

Como me mudei para Itajubá – MG para estudar Matemática (B.Sc.) na UNIFEI comecei a procurar empregos aqui na região. Enfim consegui um na própria universidade.

Agora estou trabalhando no LAT-UNIFEI, Laboratório de Alta Tensão da Universidade Federal de Itajubá.

Novamente estou envolvido no mundo dos embarcados. Aqui estamos criando um dispositivo que detecta erros em transmissão de energia. E não é para menos que sem a matemática tudo isso seria impossível. Fazemos forte uso de Análise de curvas e inteligência artificial.

Em breve postarei coisas interessantes sobre computação e matemática.

6º Encontro da comunidade de C e C++ Brasil

2010-03-02T03:10:21Z

Pessoal, dia 6 de Março de 2010 haverá o 6º encontro da comunidade brasileira de C e C++ em São Paulo.

Eu tive o privilégio de ser convidado para palestrar sobre o RobotQt. O título da palestra é: Simulador de robótica com Qt Framework.

Não perca esse evento. Faça a inscrição aqui!

ValeTI – Portal de empregos de TI feito em django

2010-01-09T14:11:19Z

Olá pessoal,

Depois de um bom tempo sem postar estou de volta para anunciar um portal que fiz. O ValeTI. É basicamente um portal de anúncios de emprego de TI na região do Vale do Paraíba.

Para desenvolve-lo eu segui basicamente a idéia de desenvolvimento. Ser simples, claro e genérico. Por isso fiz bom uso de Python e Django.

Fiquei impressionado com o Django. É realmente uma ferramenta impressionante. Super fácil de usar, completa e muito genérica.

Taí a dica. Agora nesse ano de 2010 voltarei com meus posts de artigos e tutoriais. O ano de 2009 foi muito corrido e não deu para fazer nada praticamente devido ao vestibular.

$60,00 dollares de desconto no DreamHost

2009-11-18T12:33:34Z

Atualizei agora pouco um promo code para o DreamHost.

Se você estiver procurando o melhor host que existe para hospedar seu site ou blog, descubra como ganhar esse desconto agora!

Fazendo isso, você estará contribuindo para que seja pago meu plano de hospedagem. Muito obrigado!

Se tiver alguma dúvida ou sugestão, fique à vontade para comentar.

Atualização do plugin Category Show

2009-10-23T15:12:13Z

Quanto tempo que não posto! Apesar de ter muitas idéias em mente, estive privado de postar esse ano pelo fato de estar estudando para o vestibular.

Mas enfim, estou com um tempinho hoje e resolvi atualizar o plugin Category Show para o WordPress devido a grande quantidade de feedback.

Nessa nova versão, a 0.3, vou adicionar opção de geração de tags em uma página de opções. E também a possibilidade de ordenar a lista.

É isso aí pessoal, abraço!

Analisando Número de Fibonacci e Recursividade

2009-01-30T15:38:37Z

O número de Fibonacci é bem conhecido no mundo da computação. Ele é representado por uma função recursiva:

Calculando

Tendo isso em mente é bem fácil criar um algoritmo que calcule o número de Fibonacci, certo?
Na internet normalmente encontramos um algoritmo usando um método de recursão simples. Algo parecido com:

Felipe: Esse artigo usa apenas exemplos em C++

fibo1.cpp

#include <iostream>
#include <cstdlib>
 
int F(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    return F(n - 1) + F(n - 2);
}
 
int main(int argc, char *argv[])
{
    int n = atoi(argv[1]);
    std::cout << F(n) << std::endl;
    return 0;
}

código no pastebin

Compilando:

g++ -o fibo1 fibo1.cpp

Rodando:

./fibo1 8

Deu 21, certo? Isso mesmo.

Analisando a Função

Mas digo para você: Não use esse programa! É totalmente ineficiente. O número de chamadas para calcular é exatamente . A função calcula recursivamente o mesmo número quantas vezes a chamar. Como podemos ver, a taxa de crescimento do número de Fibonacci tende a Proporção áurea:

Lembrando que a razão áurea é definida por:

Sim, fibo1.cpp é uma função exponencial com Big Theta Notation, em função do tempo, de:

O tempo de execução para computar é vezes mais demorado que para calcular . Por exemplo, já que e percebemos que nosso computador leva um segundo para calcular , então levará mais de um minuto para calcular e mais de uma hora para calcular .

Podemos verificar isso calculando e

pet@felipe-opensuse:~/Projetos/C++/algoritmos> time ./fibo1 36
14930352

real 0m1.077s
user 0m1.040s
sys 0m0.008s
pet@felipe-opensuse:~/Projetos/C++/algoritmos> time ./fibo1 45
1134903170

real 0m54.927s
user 0m54.547s
sys 0m0.092s

Em contraste, usando o método de programação dinâmica temos um tempo proporcional a N.

Programação dinâmica

Esse método consiste em guardar os valores dos números já calculados em um array. Fazendo isso, apenas checamos se o array já foi memorizado, e então retornamos o número, caso contrário calculamos recursivamente e assim por diante.
Lembrando que para um int de 32 bits, será o maior numero a ser calculado.

fibo2.cpp

#include <iostream>
#include <cstdlib>
 
namespace Fibonacci {
    int *memory;
    int F(int n)
    {
        // int inicializa como 0
        if (memory[n] != 0) return memory[n];
        int aux = n;
        if (n < 0) return 0;
        if (n > 1) aux = F(n-1) + F(n-2);
        return memory[n] = aux;
    }
}
 
int main(int argc, char *argv[])
{
    int n = atoi(argv[1]);
    Fibonacci::memory = new int[n+1];
    std::cout << Fibonacci::F(n) << std::endl;
    delete [] Fibonacci::memory;
    return 0;
}

código no pastebin

Compilando:

g++ -o fibo2 fibo2.cpp

Rodando:

./fibo2 8

Deu 21, de novo? =)

Aplicamos aqui uma técnica chamada bottom-up dynamic programming. Se aplica em uma função recursiva que podemos salvar tempo por armazenar valores anteriores que serão usados depois. Essa técnica tem sido usada para uma gama grande de algoritmos e aplicações. E essa simples mudança fez com que nosso algoritmo passasse de exponencial para linear.

Agora temos uma função, em relação ao tempo, proporcional ao N.

Comparando

Fazendo vários testes, podemos chegar em uma tabela de resultados, em função do tempo:

arquivo
fibo1.cpp	0m0.009s	0m1.156s	0m54.927s	1m29.403s
fibo2.cpp	0m0.007s	0m0.007s	0m0.006s	0m0.007s

fibo2.cpp é constante? Sim! Para N relativamente pequeno fibo2.cpp calcula em tempo constante.

Será interessante ver até quanto esse algoritmo agüenta(ta errado né? hehe ¬¬) fazer em tempo constante. Alguém se habilita?

ack, um grep melhorado

2009-01-25T18:10:00Z

Se você é fan do grep(especialmente com o -drecurse), mas sempre vendo o .svn ou outro diretório irritante, você precisa do ack.

Descobri esse programinha num blog do KDE e gostei muito!

Algumas coisas legais:

output bonitinho(colorido)
highlight
boa organização
fácil configuração
e até mesmo documentação

Digitar menos, o que você quer mais?

Exemplo:

Josephus Problem, resolvendo-o de maneira simples

2009-01-09T18:31:05Z

Josephus Problem é um problema bem legal que estudei no livro Concrete Mathematics.

Josephus foi um historiador judeu do primeiro século. A lenda conta que ele e 40 de seus homens estavam presos em uma caverna pelos Romanos. Eles decidiram suicidar-se à ser capturados. Formaram um circulo e começaram a se matar, da 3ª à 3ªa pessoa em ordem da fila. Como Josephus não queria morrer, ele foi capaz de escolher o melhor lugar, afim de sobreviver, e juntar-se os Romanos que o capturaram.

O Problema

Na prática o problema teria N pessoas em um círculo, iria ser percorrido M – 1 pessoas e o M iria ser morto, assim por diante, até sobrar uma única pessoa.

A Solução

Podemos representar a solução por uma função recursiva, para N par e M = 2:

e para N ímpar e M = 2, temos:

Não vou postar a solução genérica aqui pois exige uma grande explicação e esse não é o objetivo do post. Você pode ver na wikipedia ou então comprar o livro, caso queria saber mais.

O interessante é que o algoritmo para solução genérica é bem simples em C++. Usando listas ligadas(linked lists) é simples, fácil de entender e super rápido a execução do programa.

Josephus.cpp

#include <iostream>
#include <cstdlib>
 
struct Pessoa {
	int num;
	Pessoa *prox;
	Pessoa(int x, Pessoa *p) {
		num = x;
		prox = p;
	}
};
 
int main(int argc, char *argv[]) {
	//'a' recebe primeira pessoa criada
	//e 'a' é linkado para si mesmo
	//depois 'b' é criado apontado para 'a'
	int N = atoi(argv[1]), M = atoi(argv[2]);
	Pessoa *a = new Pessoa(1, 0);
	a->prox = a;
	Pessoa *b = a;
 
	// Aloca na memória todas as pessoas
	// e 'b' recebe a última(enésima pessoa)
	// pois a contagem começa pela primeira('a')
	for (int i = 2; i <= N; ++i)
		b = (b->prox = new Pessoa(i, a));
 
	// Loop enquanto 'b' não estiver apontado
	// o próximo para ele mesmo
	while (b != b->prox) {
		// 'b' recebe a emésima pessoa
		for (int i = 1; i < M; ++i)
			b = b->prox;
		a = b->prox;
		b->prox = a->prox;
		delete a; // 'a' é morto =/
	}
 
	// O sobrevivente _o/
	std::cout << b->num << std::endl;
}

Ou então se preferir um link para o pastebin.

Analisando o Resultado

após compilar

g++ -o Josephus Josephus.cpp

rode o programa com N = 10 e M = 2

./Josephus 10 2

O valor deu 5? Verifique com a função. Bateu os valores?
Agora vá testando para 1 <= N <= 16 e M = 2.

for n in `seq 16`; do echo -n “$n: “; ./Josephus $n 2; done

Saída do loop:

1: 1
2: 1
3: 3
4: 1
5: 3
6: 5
7: 7
8: 1
9: 3
10: 5
11: 7
12: 9
13: 11
14: 13
15: 15
16: 1

Perceberam um certo padrão entre as respostas? A função genérica usa justamente esse padrão binário para solução.

Ultimamente eu estou mais dedicado ao estudo de algoritmos, C++, C e Python(é claro). Depois pretendo postar uma analise desse algoritmo passo a passo.